{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:26:06Z","timestamp":1768317966644,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"S10","license":[{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":17,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Genomics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n<jats:title>Background<\/jats:title>\n<jats:p>The current computational methods on identifying conserved protein complexes across multiple Protein-Protein Interaction (PPI) networks suffer from the lack of explicit modeling of the desired topological properties within conserved protein complexes as well as their scalability.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Results<\/jats:title>\n<jats:p>To overcome those issues, we propose a scalable algorithm\u2014ClusterM\u2014for identifying conserved protein complexes across multiple PPI networks through the integration of network topology and protein sequence similarity information. ClusterM overcomes the computational barrier that existed in previous methods, where the complexity escalates exponentially when handling an increasing number of PPI networks; and it is able to detect conserved protein complexes with both topological separability and cohesive protein sequence conservation. On two independent compendiums of PPI networks from <jats:italic>Saccharomyces cerevisiae<\/jats:italic> (<jats:italic>Sce<\/jats:italic>, yeast), <jats:italic>Drosophila melanogaster<\/jats:italic> (<jats:italic>Dme<\/jats:italic>, fruit fly), <jats:italic>Caenorhabditis elegans<\/jats:italic> (<jats:italic>Cel<\/jats:italic>, worm), and <jats:italic>Homo sapiens<\/jats:italic> (<jats:italic>Hsa<\/jats:italic>, human), we demonstrate that ClusterM outperforms other state-of-the-art algorithms by a significant margin and is able to identify <jats:italic>de novo<\/jats:italic> conserved protein complexes across four species that are missed by existing algorithms.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Conclusions<\/jats:title>\n<jats:p>ClusterM can better capture the desired topological property of a typical conserved protein complex, which is densely connected within the complex while being well-separated from the rest of the networks. Furthermore, our experiments have shown that ClusterM is highly scalable and efficient when analyzing multiple PPI networks.<\/jats:p>\n<\/jats:sec>","DOI":"10.1186\/s12864-020-07010-1","type":"journal-article","created":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T18:03:41Z","timestamp":1605722621000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["ClusterM: a scalable algorithm for computational prediction of conserved protein complexes across multiple protein interaction networks"],"prefix":"10.1186","volume":"21","author":[{"given":"Yijie","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyundoo","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Byung-Jun","family":"Yoon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoning","family":"Qian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,18]]},"reference":[{"issue":"8","key":"7010_CR1","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(8):4569\u201374.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"10","key":"7010_CR2","doi-asserted-by":"publisher","first-page":"1576","DOI":"10.1002\/pmic.201100523","volume":"12","author":"D WH","year":"2012","unstructured":"WH D, M M, AC G. Affinity-purification coupled to mass spectrometry: basic principles and strategies. Proteomics. 2012; 12(10):1576\u201390.","journal-title":"Proteomics"},{"key":"7010_CR3","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1093\/nar\/gkh086","volume":"32","author":"L Salwinski","year":"2004","unstructured":"Salwinski L, Miller C, Smith A, Pettit F, JU JB, Eisenberg D. The Database of Interacting Proteins: 2004 update. Nucleic Acids Res. 2004; 32:449\u201351.","journal-title":"Nucleic Acids Res"},{"issue":"D1","key":"7010_CR4","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1093\/nar\/gkr1088","volume":"40","author":"S Kerrien","year":"2012","unstructured":"Kerrien S, Aranda B, Breuza L, et al.The intact molecular interaction database in 2012. Nucleic Acids Res. 2012; 40(D1):841\u20136.","journal-title":"Nucleic Acids Res"},{"key":"7010_CR5","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1093\/nar\/gkj109","volume":"34","author":"C Stark","year":"2006","unstructured":"Stark C, Breitkreutz B, Reguly T, Boucher L, Breitkreutz A, Tyers M. BioGRID: A general repository for interaction datasets. Nucleic Acids Res. 2006; 34:535\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"7010_CR6","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1038\/nmeth.1938","volume":"9","author":"T Nepusz","year":"2012","unstructured":"Nepusz T, Yu H, Paccanaro A. Detecting overlapping protein complexes in protein-protein interaction networks. Nat Methods. 2012; 9(5):471\u2013472.","journal-title":"Nat Methods"},{"key":"7010_CR7","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1093\/bioinformatics\/btp203","volume":"25","author":"C Liao","year":"2009","unstructured":"Liao C, Lu K, Baym M, Singh R, Berger B. IsoRankN: Spectral methods for global alignment of multiple protein networks. Bioinformatics. 2009; 25:253\u20138.","journal-title":"Bioinformatics"},{"issue":"7","key":"7010_CR8","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","volume":"29","author":"AE Aladag","year":"2013","unstructured":"Aladag AE, Erten C. Spinal: scalable protein interaction network alignment. Bioinformatics. 2013; 29(7):917\u201324.","journal-title":"Bioinformatics"},{"key":"7010_CR9","doi-asserted-by":"crossref","unstructured":"Hasan MM, Kahveci T. Indexing a protein-protein interaction network expedites network alignment. BMC Bioinformatics. 2015;16:326.","DOI":"10.1186\/s12859-015-0756-0"},{"issue":"35","key":"7010_CR10","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","volume":"105","author":"R Singh","year":"2008","unstructured":"Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc Natl Acad Sci USA. 2008; 105(35):12763\u20138.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"12","key":"7010_CR11","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1093\/bioinformatics\/btv063","volume":"31","author":"C Clark","year":"2015","unstructured":"Clark C, Kalita J. A multiobjective memetic algorithm for ppi network alignment. Bioinformatics. 2015; 31(12):1988\u201398.","journal-title":"Bioinformatics"},{"key":"7010_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1186\/1752-0509-9-S1-S7","volume":"9 Suppl 1","author":"H Jeong","year":"2015","unstructured":"Jeong H, Yoon B-J. Accurate multiple network alignment through context-sensitive random walk. BMC Syst Biol. 2015; 9 Suppl 1:7.","journal-title":"BMC Syst Biol"},{"key":"7010_CR13","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1073\/pnas.0409522102","volume":"102","author":"R Sharan","year":"2005","unstructured":"Sharan R, Suthram S, Kelley RM, et al.Conserved patterns of protein interaction in multiple species. Proc Natl Acac Sci USA. 2005; 102:1974\u20139.","journal-title":"Proc Natl Acac Sci USA"},{"key":"7010_CR14","volume-title":"RECOMB 2005","author":"M Koyuturk","year":"2005","unstructured":"Koyuturk M, Grama A, Szpankowski W. Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution. In: RECOMB 2005. Berlin, Heidelberg: Springer: 2005. p. 48\u201365."},{"issue":"8","key":"7010_CR15","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1089\/cmb.2009.0136","volume":"16","author":"M Kalaev","year":"2009","unstructured":"Kalaev M, Bafna V, Sharan R. Fast and accurate alignment of multiple protein networks. J Comput Biol. 2009; 16(8):989\u201399.","journal-title":"J Comput Biol"},{"issue":"1","key":"7010_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/MSP.2011.942819","volume":"29","author":"B-J Yoon","year":"2012","unstructured":"Yoon B-J, Qian X, Sahraeian SME. Comparative analysis of biological networks: hidden markov model and markov chain-based approach. IEEE Signal Proc Mag. 2012; 29(1):22\u201334.","journal-title":"IEEE Signal Proc Mag"},{"issue":"6","key":"7010_CR17","doi-asserted-by":"publisher","first-page":"38107","DOI":"10.1371\/journal.pone.0038107","volume":"7","author":"G Ciriello","year":"2012","unstructured":"Ciriello G, Mina M, Guzzi PH, Cannataro M, Guerra C. Alignnemo: A local network alignment method to integrate homology and topology. PLoS ONE. 2012; 7(6):38107.","journal-title":"PLoS ONE"},{"issue":"2","key":"7010_CR18","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1093\/bioinformatics\/btl295","volume":"23","author":"E Hirsh","year":"2007","unstructured":"Hirsh E, Sharan R. Identification of conserved protein complexes based on a model of protein network evolution. Bioinformatics. 2007; 23(2):170\u20136.","journal-title":"Bioinformatics"},{"key":"7010_CR19","doi-asserted-by":"crossref","unstructured":"Berg J. Structure and evolution of protein interaction networks: a statistical model for link dynamics and gene duplications. BMC Evol Biol. 2004; 4(51). https:\/\/doi.org\/10.1186\/1471-2148-4-51.","DOI":"10.1186\/1471-2148-4-51"},{"issue":"1-2","key":"7010_CR20","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1089\/10665270050081478","volume":"7","author":"Z Zhang","year":"2000","unstructured":"Zhang Z, Schwartz S, Wagner L, Miller W. A greedy algorithm for aligning dna sequences. J Comput Biol. 2000; 7(1-2):203\u201314.","journal-title":"J Comput Biol"},{"key":"7010_CR21","doi-asserted-by":"crossref","unstructured":"Mina M, Guzzi PH. Alignmcl: Comparative analysis of protein interaction networks through markov clustering. In: Bioinformatics and Biomedicine Workshops (BIBMW), 2012 IEEE International Conference On. IEEE: 2012. p. 174\u201381. https:\/\/doi.org\/10.1109\/BIBMW.2012.6470300.","DOI":"10.1109\/BIBMW.2012.6470300"},{"issue":"6","key":"7010_CR22","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1073\/pnas.0409522102","volume":"102","author":"R Sharan","year":"2005","unstructured":"Sharan R, Suthram S, Kelley R, Kuhn T, McCuine S, Uetz P, Sittler T, Karp R, Ideker T. Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci USA. 2005; 102(6):1974\u20139.","journal-title":"Proc Natl Acad Sci USA"},{"key":"7010_CR23","doi-asserted-by":"crossref","unstructured":"Kalaev M, Bafna V, Sharan R. Fast and accurate alignment of multiple protein networks. In: Proc of the 10th Annu Int Conf Res Comput Mol Bio (RECOMB 2008): 2008. https:\/\/doi.org\/10.1007\/978-3-540-78839-3_21.","DOI":"10.1007\/978-3-540-78839-3_21"},{"issue":"3","key":"7010_CR24","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1093\/nar\/gkn1005","volume":"37","author":"S Pu","year":"2009","unstructured":"Pu S, Wong J, Turner B, et al.Up-to-date catalogues of yeast protein complexes. Nucleic Acids Res. 2009; 37(3):825\u201331.","journal-title":"Nucleic Acids Res"},{"key":"7010_CR25","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1093\/nar\/gkm936","volume":"36","author":"A Ruepp","year":"2008","unstructured":"Ruepp A, Brauner B, Dunger-Kaltenbach I, et al.Corum: The comprehensive resource of mammalian protein complexes. Nucleic Acids Res. 2008; 36:646\u201350.","journal-title":"Nucleic Acids Res"},{"key":"7010_CR26","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1126\/science.1065103","volume":"296","author":"S Maslov","year":"2002","unstructured":"Maslov S, Sneppen K. Specificity and stability in topology of protein networks. Science. 2002; 296:910\u20133.","journal-title":"Science"},{"issue":"D1","key":"7010_CR27","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1093\/nar\/gku1003","volume":"43","author":"D Szklarczyk","year":"2014","unstructured":"Szklarczyk D, Franceschini A, Wyder S, Forslund K, Heller D, Huerta-Cepas J, Simonovic M, Roth A, Santos A, Tsafou KP, et al.String v10: protein\u2013protein interaction networks, integrated over the tree of life. Nucleic Acids Res. 2014; 43(D1):447\u201352.","journal-title":"Nucleic Acids Res"},{"issue":"7","key":"7010_CR28","doi-asserted-by":"publisher","first-page":"67995","DOI":"10.1371\/journal.pone.0067995","volume":"8","author":"SME Sahraeian","year":"2013","unstructured":"Sahraeian SME, Yoon B-J. Smetana: Accurate and scalable algorithm for probabilistic alignment of large-scale biological networks. PLoS ONE. 2013; 8(7):67995.","journal-title":"PLoS ONE"},{"key":"7010_CR29","doi-asserted-by":"crossref","unstructured":"Andersen R, Chung F, Lang K. Local Graph Partitioning Using PageRank Vectors. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906): 2006. p. 475\u201386. https:\/\/doi.org\/10.1109\/FOCS.2006.44.","DOI":"10.1109\/FOCS.2006.44"},{"issue":"2","key":"7010_CR30","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s10878-010-9351-5","volume":"23","author":"N Fan","year":"2010","unstructured":"Fan N, Pardalos P. Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs. J Comb Optim. 2010; 23(2):224\u201351.","journal-title":"J Comb Optim"},{"issue":"suppl 1","key":"7010_CR31","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1186\/1752-0509-8-S1-S9","volume":"8","author":"Y Wang","year":"2014","unstructured":"Wang Y, Qian X. Joint clustering of protein interaction networks through markov random walk. BMC Syst Biol. 2014; 8(suppl 1):9.","journal-title":"BMC Syst Biol"},{"issue":"1","key":"7010_CR32","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil DG, Perl Y. Clustering and domination in perfect graphs. Discret Appl Math. 1984; 9(1):27\u201339.","journal-title":"Discret Appl Math"},{"issue":"1","key":"7010_CR33","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1038\/75556","volume":"25","author":"M Ashburner","year":"2000","unstructured":"Ashburner M, Ball C, Blake J, et al.Gene ontology: Tool for the unification of biology. the gene ontology consortium. Nat Genet. 2000; 25(1):25\u20139.","journal-title":"Nat Genet"},{"issue":"18","key":"7010_CR34","doi-asserted-by":"publisher","first-page":"1473","DOI":"10.1093\/bioinformatics\/bts370","volume":"28","author":"Y-K Shih","year":"2012","unstructured":"Shih Y-K, Parthasarathy S. Identifying functional modules in interaction networks through overlapping markov clustering. Bioinformatics. 2012; 28(18):1473\u20139.","journal-title":"Bioinformatics"}],"container-title":["BMC Genomics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12864-020-07010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12864-020-07010-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12864-020-07010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T18:05:36Z","timestamp":1605722736000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcgenomics.biomedcentral.com\/articles\/10.1186\/s12864-020-07010-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":34,"journal-issue":{"issue":"S10","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["7010"],"URL":"https:\/\/doi.org\/10.1186\/s12864-020-07010-1","relation":{},"ISSN":["1471-2164"],"issn-type":[{"value":"1471-2164","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11]]},"assertion":[{"value":"18 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"All the authors approve the publication of the presented work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"615"}}