{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T07:11:40Z","timestamp":1766733100679},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>High-throughput methods for detecting protein-protein interactions enable us to obtain large interaction networks, and also allow us to computationally identify the associations of proteins as protein complexes. Although there are methods to extract protein complexes as sets of proteins from interaction networks, the extracted complexes may include false positives because they do not account for the structural limitations of the proteins and thus do not check that the proteins in the extracted complex can simultaneously bind to each other. In addition, there have been few searches for deeper insights into the protein complexes, such as of the topology of the protein-protein interactions or into the domain-domain interactions that mediate the protein interactions.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Here, we introduce a combinatorial approach for prediction of protein complexes focusing not only on determining member proteins in complexes but also on the DDI\/PPI organization of the complexes. Our method analyzes complex candidates predicted by the existing methods. It searches for optimal combinations of domain-domain interactions in the candidates based on an assumption that the proteins in a candidate can form a true protein complex if each of the domains is used by a single protein interaction. This optimization problem was mathematically formulated and solved using binary integer linear programming. By using publicly available sets of yeast protein-protein interactions and domain-domain interactions, we succeeded in extracting protein complex candidates with an accuracy that is twice the average accuracy of the existing methods, MCL, MCODE, or clustering coefficient. Although the configuring parameters for each algorithm resulted in slightly improved precisions, our method always showed better precision for most values of the parameters.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Our combinatorial approach can provide better accuracy for prediction of protein complexes and also enables to identify both direct PPIs and DDIs that mediate them in complexes.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-11-350","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T06:14:13Z","timestamp":1277792053000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["Protein complex prediction via verifying and reconstructing the topology of domain-domain interactions"],"prefix":"10.1186","volume":"11","author":[{"given":"Yosuke","family":"Ozawa","sequence":"first","affiliation":[]},{"given":"Rintaro","family":"Saito","sequence":"additional","affiliation":[]},{"given":"Shigeo","family":"Fujimori","sequence":"additional","affiliation":[]},{"given":"Hisashi","family":"Kashima","sequence":"additional","affiliation":[]},{"given":"Masamichi","family":"Ishizaka","sequence":"additional","affiliation":[]},{"given":"Hiroshi","family":"Yanagawa","sequence":"additional","affiliation":[]},{"given":"Etsuko","family":"Miyamoto-Sato","sequence":"additional","affiliation":[]},{"given":"Masaru","family":"Tomita","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,6,28]]},"reference":[{"key":"3807_CR1","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/35001009","volume":"403","author":"P Uetz","year":"2000","unstructured":"Uetz P, Giot L, Cagney G, Mansfield TA, Judson RS, Knight JR, Lockshon D, Narayan V, Srinivasan M, Pochart P, others: A comprehensive analysis of protein--protein interactions in Saccharomyces cerevisiae. Nature 2000, 403: 623\u2013627. 10.1038\/35001009","journal-title":"Nature"},{"key":"3807_CR2","doi-asserted-by":"publisher","first-page":"4569","DOI":"10.1073\/pnas.061034498","volume":"98","author":"T Ito","year":"2001","unstructured":"Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y: A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc Natl Acad Sci USA 2001, 98: 4569. 10.1073\/pnas.061034498","journal-title":"Proc Natl Acad Sci USA"},{"key":"3807_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1038\/415141a","volume":"415","author":"AC Gavin","year":"2002","unstructured":"Gavin AC, B\u00f6sche M, Krause R, Grandi P, Marzioch M, Bauer A, Schultz J, Rick JM, Michon AM, Cruciat CM, others: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 2002, 415: 141\u2013147. 10.1038\/415141a","journal-title":"Nature"},{"key":"3807_CR4","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1038\/415180a","volume":"415","author":"Y Ho","year":"2002","unstructured":"Ho Y, Gruhler A, Heilbut A, Bader GD, Moore L, Adams SL, Millar A, Taylor P, Bennett K, Boutilier K, Yang L, Wolting C, Donaldson I, Schandorff S, Shewnarane J, Vo M, Taggart J, Goudreault M, Muskat B, Alfarano C, Dewar D, Lin Z, Michalickova K, Willems AR, Sassi H, Nielsen PA, Rasmussen KJ, Andersen JR, Johansen LE, Hansen LH, Jespersen H, Podtelejnikov A, Nielsen E, Crawford J, Poulsen V, Sorensen BD, Matthiesen J, Hendrickson RC, Gleeson F, Pawson T, Moran MF, Durocher D, Mann M, Hogue CW, Figeys D, Tyers M: Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature 2002, 415: 180\u2013183. 10.1038\/415180a","journal-title":"Nature"},{"key":"3807_CR5","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1038\/nature04532","volume":"440","author":"AC Gavin","year":"2006","unstructured":"Gavin AC, Aloy P, Grandi P, Krause R, Boesche M, Marzioch M, Rau C, Jensen LJ, Bastuck S, Dumpelfeld B, Edelmann A, Heurtier MA, Hoffman V, Hoefert C, Klein K, Hudak M, Michon AM, Schelder M, Schirle M, Remor M, Rudi T, Hooper S, Bauer A, Bouwmeester T, Casari G, Drewes G, Neubauer G, Rick JM, Kuster B, Bork P, Russell RB, Superti-Furga G: Proteome survey reveals modularity of the yeast cell machinery. Nature 2006, 440: 631\u2013636. 10.1038\/nature04532","journal-title":"Nature"},{"key":"3807_CR6","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1038\/nature04670","volume":"440","author":"NJ Krogan","year":"2006","unstructured":"Krogan NJ, Cagney G, Yu H, Zhong G, Guo X, Ignatchenko A, Li J, Pu S, Datta N, Tikuisis AP, Punna T, Peregrin-Alvarez JM, Shales M, Zhang X, Davey M, Robinson MD, Paccanaro A, Bray JE, Sheung A, Beattie B, Richards DP, Canadien V, Lalev A, Mena F, Wong P, Starostine A, Canete MM, Vlasblom J, Wu S, Orsi C, Collins SR, Chandran S, Haw R, Rilstone JJ, Gandi K, Thompson NJ, Musso G, St Onge P, Ghanny S, Lam MH, Butland G, Altaf-Ul AM, Kanaya S, Shilatifard A, O'Shea E, Weissman JS, Ingles CJ, Hughes TR, Parkinson J, Gerstein M, Wodak SJ, Emili A, Greenblatt JF: Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature 2006, 440: 637\u2013643. 10.1038\/nature04670","journal-title":"Nature"},{"key":"3807_CR7","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1038\/nrm1859","volume":"7","author":"P Aloy","year":"2006","unstructured":"Aloy P, Russell RB: Structural systems biology: modelling protein interactions. Nature Reviews Molecular Cell Biology 2006, 7: 188\u2013197. 10.1038\/nrm1859","journal-title":"Nature Reviews Molecular Cell Biology"},{"key":"3807_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"GD Bader","year":"2003","unstructured":"Bader GD, Hogue CW: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 2003, 4: 2. 10.1186\/1471-2105-4-2","journal-title":"BMC Bioinformatics"},{"key":"3807_CR9","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj N, Wigle DA, Jurisica I: Functional topology in a network of protein interactions. Bioinformatics 2004, 20: 340\u2013348. 10.1093\/bioinformatics\/btg415","journal-title":"Bioinformatics"},{"key":"3807_CR10","volume-title":"PhD thesis","author":"Sv Dongen","year":"2000","unstructured":"Dongen Sv: Graph Clustering by Flow Simulation. PhD thesis. University of Utrecht, Centre for Mathematics and Computer Science; 2000."},{"key":"3807_CR11","doi-asserted-by":"publisher","first-page":"12123","DOI":"10.1073\/pnas.2032324100","volume":"100","author":"V Spirin","year":"2003","unstructured":"Spirin V, Mirny LA: Protein complexes and functional modules in molecular networks. Proc Natl Acad Sci USA 2003, 100: 12123\u201312128. 10.1073\/pnas.2032324100","journal-title":"Proc Natl Acad Sci USA"},{"key":"3807_CR12","doi-asserted-by":"publisher","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","volume":"20","author":"AD King","year":"2004","unstructured":"King AD, Przulj N, Jurisica I: Protein complex prediction via cost-based clustering. Bioinformatics 2004, 20: 3013\u20133020. 10.1093\/bioinformatics\/bth351","journal-title":"Bioinformatics"},{"issue":"3","key":"3807_CR13","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1142\/S0219720008003497","volume":"6","author":"HN Chua","year":"2008","unstructured":"Chua HN, Ning K, Sung WK, Leong HW, Wong L: Using indirect protein-protein interactions for protein complex prediction. Journal of Bioinformatics and Computational Biology 2008, 6(3):435\u2013466. 10.1142\/S0219720008003497","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"3807_CR14","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1186\/1471-2105-7-488","volume":"7","author":"S Brohee","year":"2006","unstructured":"Brohee S, van Helden J: Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 2006, 7: 488. 10.1186\/1471-2105-7-488","journal-title":"BMC Bioinformatics"},{"key":"3807_CR15","doi-asserted-by":"publisher","first-page":"2026","DOI":"10.1126\/science.1092645","volume":"303","author":"P Aloy","year":"2004","unstructured":"Aloy P, Bottcher B, Ceulemans H, Leutwein C, Mellwig C, Fischer S, Gavin AC, Bork P, Superti-Furga G, Serrano L, Russell RB: Structure-based assembly of protein complexes in yeast. Science 2004, 303: 2026\u20132029. 10.1126\/science.1092645","journal-title":"Science"},{"key":"3807_CR16","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-540-71681-5_3","volume":"4453","author":"A Bernard","year":"2007","unstructured":"Bernard A, Vaughn DS, Hartemink AJ: Reconstructing the topology of protein complexes. Lecture Notes in Computer Science 2007, 4453: 32. full_text","journal-title":"Lecture Notes in Computer Science"},{"issue":"16","key":"3807_CR17","doi-asserted-by":"publisher","first-page":"2140","DOI":"10.1093\/bioinformatics\/btp353","volume":"25","author":"CC Friedel","year":"2009","unstructured":"Friedel CC, Zimmer R: Identifying the topology of protein complexes from affinity purification assays. Bioinformatics 2009, 25(16):2140\u20132146. 10.1093\/bioinformatics\/btp353","journal-title":"Bioinformatics"},{"key":"3807_CR18","doi-asserted-by":"publisher","first-page":"1938","DOI":"10.1126\/science.1136174","volume":"314","author":"PM Kim","year":"2006","unstructured":"Kim PM, Lu LJ, Xia Y, Gerstein MB: Relating three-dimensional structures to protein networks provides evolutionary insights. Science 2006, 314: 1938\u20131941. 10.1126\/science.1136174","journal-title":"Science"},{"key":"3807_CR19","doi-asserted-by":"publisher","first-page":"14718","DOI":"10.1073\/pnas.0603352103","volume":"103","author":"E Sprinzak","year":"2006","unstructured":"Sprinzak E, Altuvia Y, Margalit H: Characterization and prediction of protein-protein interactions within and between complexes. Proc Natl Acad Sci USA 2006, 103: 14718\u201314723. 10.1073\/pnas.0603352103","journal-title":"Proc Natl Acad Sci USA"},{"key":"3807_CR20","doi-asserted-by":"publisher","first-page":"D535","DOI":"10.1093\/nar\/gkj109","volume":"34","author":"C Stark","year":"2003","unstructured":"Stark C, Breitkreutz BJ, Reguly T, Boucher L, Breitkreutz A, Tyers M: BioGRID: a general repository for interaction datasets. Nucleic Acids Res 2003, 34: D535-D539. 10.1093\/nar\/gkj109","journal-title":"Nucleic Acids Res"},{"key":"3807_CR21","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1093\/bioinformatics\/bti011","volume":"21","author":"RD Finn","year":"2005","unstructured":"Finn RD, Marshall M, Bateman A: iPfam: visualization of protein-protein interactions in PDB at domain and amino acid resolutions. Bioinformatics 2005, 21: 410\u2013412. 10.1093\/bioinformatics\/bti011","journal-title":"Bioinformatics"},{"key":"3807_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1093\/nar\/gkg079","volume":"31","author":"SK Ng","year":"2003","unstructured":"Ng SK, Zhang Z, Tan SH, Lin K: InterDom: a database of putative interacting protein domains for validating predicted protein interactions and complexes. Nucleic Acids Res 2003, 31: 251. 10.1093\/nar\/gkg079","journal-title":"Nucleic Acids Res"},{"key":"3807_CR23","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1093\/nar\/30.5.1163","volume":"30","author":"R Saito","year":"2002","unstructured":"Saito R, Suzuki H, Hayashizaki Y: Interaction generality a measurement to assess the reliability of a protein-protein interaction. Nucleic acids research 2002, 30: 1163. 10.1093\/nar\/30.5.1163","journal-title":"Nucleic acids research"},{"key":"3807_CR24","doi-asserted-by":"publisher","first-page":"3643","DOI":"10.1091\/mbc.10.11.3643","volume":"10","author":"BG Yeung","year":"1999","unstructured":"Yeung BG, Phan HL, Payne GS: Adaptor complex-independent clathrin function in yeast. Molecular biology of the cell 1999, 10: 3643.","journal-title":"Molecular biology of the cell"},{"key":"3807_CR25","doi-asserted-by":"crossref","first-page":"1951","DOI":"10.1002\/j.1460-2075.1984.tb02075.x","volume":"3","author":"BM Pearse","year":"1984","unstructured":"Pearse BM, Robinson MS: Purification and properties of 100-kd proteins from coated vesicles and their reconstitution with clathrin. EMBO J 1984, 3: 1951\u20131957.","journal-title":"EMBO J"},{"key":"3807_CR26","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1146\/annurev.cellbio.13.1.779","volume":"13","author":"TH Stevens","year":"1997","unstructured":"Stevens TH, Forgac M: Structure, function and regulation of the vacuolar (H+)-ATPase. Annual review of cell and developmental biology 1997, 13: 779\u2013808. 10.1146\/annurev.cellbio.13.1.779","journal-title":"Annual review of cell and developmental biology"},{"key":"3807_CR27","doi-asserted-by":"publisher","first-page":"12951","DOI":"10.1074\/jbc.274.19.12951","volume":"274","author":"M Forgac","year":"1999","unstructured":"Forgac M: Structure and properties of the vacuolar (H+)-ATPases. Journal of Biological Chemistry 1999, 274: 12951\u201312954. 10.1074\/jbc.274.19.12951","journal-title":"Journal of Biological Chemistry"},{"key":"3807_CR28","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1111\/j.1540-5915.1977.tb01074.x","volume":"8","author":"F Glover","year":"1977","unstructured":"Glover F: Heuristics for integer programming using surrogate constraints. Decision Sciences 1977, 8: 156\u2013166. 10.1111\/j.1540-5915.1977.tb01074.x","journal-title":"Decision Sciences"},{"key":"3807_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1023\/A:1018904229454","volume":"86","author":"R Rodosek","year":"1999","unstructured":"Rodosek R, Wallace MG, Hajian MT: A new approach to integrating mixed integer programming and constraint logic programming. Annals of Operations Research 1999, 86: 63\u201387. 10.1023\/A:1018904229454","journal-title":"Annals of Operations Research"},{"key":"3807_CR30","doi-asserted-by":"publisher","first-page":"R104","DOI":"10.1186\/gb-2006-7-11-r104","volume":"7","author":"K Guimar\u00e3es","year":"2006","unstructured":"Guimar\u00e3es K, Jothi R, Zotenko E, Przytycka T: Predicting domain-domain interactions using a parsimony approach. Genome Biology 2006, 7: R104. 10.1186\/gb-2006-7-11-r104","journal-title":"Genome Biology"},{"key":"3807_CR31","doi-asserted-by":"publisher","first-page":"1540","DOI":"10.1101\/gr.153002","volume":"12","author":"M Deng","year":"2002","unstructured":"Deng M, Mehta S, Sun F, Chen T: Inferring domain-domain interactions from protein-protein interactions. Genome Res 2002, 12: 1540\u20131548. 10.1101\/gr.153002","journal-title":"Genome Res"},{"key":"3807_CR32","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1186\/1471-2105-7-269","volume":"7","author":"H Lee","year":"2006","unstructured":"Lee H, Deng M, Sun F, Chen T: An integrated approach to the prediction of domain-domain interactions. BMC Bioinformatics 2006, 7: 269. 10.1186\/1471-2105-7-269","journal-title":"BMC Bioinformatics"},{"key":"3807_CR33","doi-asserted-by":"publisher","first-page":"i35","DOI":"10.1093\/bioinformatics\/btn290","volume":"24","author":"SE Schelhorn","year":"2008","unstructured":"Schelhorn SE, Lengauer T, Albrecht M: An integrative approach for predicting interactions of protein regions. Bioinformatics 2008, 24: i35. 10.1093\/bioinformatics\/btn290","journal-title":"Bioinformatics"},{"key":"3807_CR34","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1038\/nbt924","volume":"22","author":"JS Bader","year":"2003","unstructured":"Bader JS, Chaudhuri A, Rothberg JM, Chant J: Gaining confidence in high-throughput protein interaction networks. Nature biotechnology 2003, 22: 78\u201385. 10.1038\/nbt924","journal-title":"Nature biotechnology"},{"key":"3807_CR35","doi-asserted-by":"publisher","first-page":"1623","DOI":"10.1093\/bioinformatics\/btl145","volume":"22","author":"HN Chua","year":"2006","unstructured":"Chua HN, Sung WK, Wong L: Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions. Bioinformatics 2006, 22: 1623\u20131630. 10.1093\/bioinformatics\/btl145","journal-title":"Bioinformatics"},{"key":"3807_CR36","doi-asserted-by":"publisher","first-page":"S11","DOI":"10.1186\/1471-2105-10-S6-S11","volume":"10","author":"C Moschopoulos","year":"2009","unstructured":"Moschopoulos C, Pavlopoulos G, Schneider R, Likothanassis S, Kossida S: GIBA: a clustering tool for detecting protein complexes. BMC bioinformatics 2009, 10: S11. 10.1186\/1471-2105-10-S6-S11","journal-title":"BMC bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-350.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T05:18:09Z","timestamp":1630473489000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-350"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,28]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["3807"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-350","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,28]]},"assertion":[{"value":"9 October 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"350"}}