{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T08:30:13Z","timestamp":1778056213823,"version":"3.51.4"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"15","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Protein complexes are important for understanding principles of cellular organization and function. High-throughput experimental techniques have produced a large amount of protein interactions, which makes it possible to predict protein complexes from protein\u2013protein interaction (PPI) networks. However, protein interaction data produced by high-throughput experiments are often associated with high false positive and false negative rates, which makes it difficult to predict complexes accurately.<\/jats:p>\n               <jats:p>Results: We use an iterative scoring method to assign weight to protein pairs, and the weight of a protein pair indicates the reliability of the interaction between the two proteins. We develop an algorithm called CMC (clustering-based on maximal cliques) to discover complexes from the weighted PPI network. CMC first generates all the maximal cliques from the PPI networks, and then removes or merges highly overlapped clusters based on their interconnectivity. We studied the performance of CMC and the impact of our iterative scoring method on CMC. Our results show that: (i) the iterative scoring method can improve the performance of CMC considerably; (ii) the iterative scoring method can effectively reduce the impact of random noise on the performance of CMC; (iii) the iterative scoring method can also improve the performance of other protein complex prediction methods and reduce the impact of random noise on their performance; and (iv) CMC is an effective approach to protein complex prediction from protein interaction network.<\/jats:p>\n               <jats:p>Contact: \u00a0liugm@comp.nus.edu.sg<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp311","type":"journal-article","created":{"date-parts":[[2009,5,13]],"date-time":"2009-05-13T01:39:59Z","timestamp":1242178799000},"page":"1891-1897","source":"Crossref","is-referenced-by-count":409,"title":["Complex discovery from weighted PPI networks"],"prefix":"10.1093","volume":"25","author":[{"given":"Guimei","family":"Liu","sequence":"first","affiliation":[{"name":"1 School of Computing, National University of Singapore, Singapore and 2 Institute for Infocomm Research, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Limsoon","family":"Wong","sequence":"additional","affiliation":[{"name":"1 School of Computing, National University of Singapore, Singapore and 2 Institute for Infocomm Research, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hon Nian","family":"Chua","sequence":"additional","affiliation":[{"name":"1 School of Computing, National University of Singapore, Singapore and 2 Institute for Infocomm Research, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,5,12]]},"reference":[{"key":"2023013112052795400_B1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1093\/bioinformatics\/btl039","article-title":"Cfinder:locating cliques and overlapping modules in biological networks","volume":"22","author":"Adamcsek","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112052795400_B2","doi-asserted-by":"crossref","first-page":"2026","DOI":"10.1126\/science.1092645","article-title":"Structure-based assembly of protein complexes in yeast","volume":"303","author":"Aloy","year":"2004","journal-title":"Science"},{"key":"2023013112052795400_B3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1186\/1471-2105-7-207","article-title":"Development and implementation of an algorithm for detection of protein complexes in large interaction networks","volume":"7","author":"Altaf-Ul-Amin","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023013112052795400_B4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023013112052795400_B5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-4-2","article-title":"An automated method for finding molecular complexes in large protein interaction networks","volume":"4","author":"Bader","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023013112052795400_B6","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1186\/1471-2105-7-488","article-title":"Evaluation of clustering algorithms for protein-protein interaction networks","volume":"7","author":"Brohee","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023013112052795400_B7","doi-asserted-by":"crossref","first-page":"R6","DOI":"10.1186\/gb-2003-5-1-r6","article-title":"Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network","volume":"5","author":"Brun","year":"2003","journal-title":"Genome Biol."},{"key":"2023013112052795400_B8","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.artmed.2005.02.004","article-title":"Discovering reliable protein interactions from high-throughput experimental data using network topology","volume":"35","author":"Chen","year":"2005","journal-title":"Artif. Intell. Med."},{"key":"2023013112052795400_B9","first-page":"284","article-title":"Increasing confidence of protein-protein interactomes","volume-title":"Proceedings of the 17th International Conference on Genome Informatics","author":"Chen","year":"2006"},{"key":"2023013112052795400_B10","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1093\/bioinformatics\/btl145","article-title":"Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions","volume":"22","author":"Chua","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112052795400_B11","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1142\/S0219720008003497","article-title":"Using indirect protein-protein interactions for protein complex predication","volume":"6","author":"Chua","year":"2008","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023013112052795400_B12","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1074\/mcp.M100037-MCP200","article-title":"Protein interactions: two methods for assessment of the reliability of high throughput observations","volume":"1","author":"Deane","year":"2002","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013112052795400_B13","first-page":"140","article-title":"Assessment of the reliability of protein-protein interactions and protein function prediction","volume-title":"Proceedings of Pacific Symposium on Biocomputing","author":"Deng","year":"2003"},{"key":"2023013112052795400_B14","first-page":"216","article-title":"Estimating and improving protein interaction error rates","volume-title":"Proceedings of IEEE Computational Systems Bioinformatics Conference","author":"D'haeseleer","year":"2004"},{"key":"2023013112052795400_B15","first-page":"3","article-title":"Bootstrapping the interactome: Unsupervised identification of protein complexes in yeast","volume-title":"Proceedings of the 12th Annual International Conference on Research in Computational Molecular Biology (RECOMB)","author":"Friedel","year":"2008"},{"key":"2023013112052795400_B16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1038\/415141a","article-title":"Functional organization of the yeast proteome by systematic analysis of protein complexes","volume":"415","author":"Gavin","year":"2002","journal-title":"Nature"},{"key":"2023013112052795400_B17","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/nature04532","article-title":"Proteome survey reveals modularity of the yeast cell machinery","volume":"440","author":"Gavin","year":"2006","journal-title":"Nature"},{"key":"2023013112052795400_B18","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1093\/bioinformatics\/btg469","article-title":"A statistical framework for combining and interpreting proteomic datasets","volume":"20","author":"Gilchrist","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013112052795400_B19","first-page":"4372","article-title":"Assessing experimentally derived interactions in a small world","volume":"100","author":"Goldberg","year":"2003","journal-title":"Appl. Math. Biochem."},{"key":"2023013112052795400_B20","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1038\/415180a","article-title":"Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry","volume":"415","author":"Ho","year":"2002","journal-title":"Nature"},{"key":"2023013112052795400_B21","doi-asserted-by":"crossref","first-page":"4569","DOI":"10.1073\/pnas.061034498","article-title":"A comprehensive two-hybrid analysis to explore the yeast protein interactome","volume":"98","author":"Ito","year":"2001","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112052795400_B22","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in the yeast Saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023013112052795400_B23","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1186\/1471-2105-9-398","article-title":"Modifying the DPclus algorithm for identifying protein complexes based on new topological structures","volume":"9","author":"Li","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013112052795400_B24","first-page":"138","article-title":"Assessing and predicting protein interactions using both local and global network topological metrics","volume-title":"Proceedings of the 19th International Conference on Genome Informatics.","author":"Liu","year":"2008"},{"issue":"Database issue","key":"2023013112052795400_B25","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1093\/nar\/gkh092","article-title":"MIPS: analysis and annotation of proteins from whole genomes","volume":"32","author":"Mewes","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023013112052795400_B26","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1038\/nature03607","article-title":"Uncovering the overlapping community structure of complex networks in nature and society","volume":"435","author":"Palla","year":"2005","journal-title":"Nature"},{"key":"2023013112052795400_B27","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1186\/1471-2105-6-100","article-title":"Filtering high-throughput protein-protein interaction data using a combination of genomic features","volume":"6","author":"Patil","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023013112052795400_B28","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","article-title":"Functional topology in a network of protein interactions","volume":"20","author":"Przulj","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013112052795400_B29","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1093\/bioinformatics\/btg070","article-title":"Construction of reliable protein-protein interaction networks with a new interaction generality measure","volume":"19","author":"Saito","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013112052795400_B30","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","article-title":"The worst-case time complexity for generating all maximal cliques and computational experiments","volume":"363","author":"Tomita","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2023013112052795400_B31","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/35001009","article-title":"A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae","volume":"403","author":"Uetz","year":"1999","journal-title":"Nature"},{"key":"2023013112052795400_B32","article-title":"Graph clustering by flow simulation","volume-title":"PhD Thesis","author":"van Dongen","year":"2000"},{"key":"2023013112052795400_B33","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein-protein interactions","volume":"417","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023013112052795400_B34","doi-asserted-by":"crossref","first-page":"12783","DOI":"10.1073\/pnas.192159399","article-title":"Transitive functional annotation by shortest-path analysis of gene expression data","volume":"99","author":"Zhou","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/15\/1891\/48994304\/bioinformatics_25_15_1891.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/15\/1891\/48994304\/bioinformatics_25_15_1891.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:21:24Z","timestamp":1675200084000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/15\/1891\/211634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,12]]},"references-count":34,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2009,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp311","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,8,1]]},"published":{"date-parts":[[2009,5,12]]}}}