{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T07:57:14Z","timestamp":1778227034817,"version":"3.51.4"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Protein complexes integrate multiple gene products to coordinate many biological functions. Given a graph representing pairwise protein interaction data one can search for subgraphs representing protein complexes. Previous methods for performing such search relied on the assumption that complexes form a clique in that graph. While this assumption is true for some complexes, it does not hold for many others. New algorithms are required in order to recover complexes with other types of topological structure.<\/jats:p>\n               <jats:p>Results: We present an algorithm for inferring protein complexes from weighted interaction graphs. By using graph topological patterns and biological properties as features, we model each complex subgraph by a probabilistic Bayesian network (BN). We use a training set of known complexes to learn the parameters of this BN model. The log-likelihood ratio derived from the BN is then used to score subgraphs in the protein interaction graph and identify new complexes. We applied our method to protein interaction data in yeast. As we show our algorithm achieved a considerable improvement over clique based algorithms in terms of its ability to recover known complexes. We discuss some of the new complexes predicted by our algorithm and determine that they likely represent true complexes.<\/jats:p>\n               <jats:p>Availability: Matlab implementation is available on the supporting website: www.cs.cmu.edu\/~qyj\/SuperComplex<\/jats:p>\n               <jats:p>Contact: \u00a0zivbj@cs.cmu.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn164","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i250-i268","source":"Crossref","is-referenced-by-count":106,"title":["Protein complex identification by supervised graph local clustering"],"prefix":"10.1093","volume":"24","author":[{"given":"Yanjun","family":"Qi","sequence":"first","affiliation":[{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernanda","family":"Balem","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Judith","family":"Klein-Seetharaman","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"},{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziv","family":"Bar-Joseph","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 and 2Department of Structural Biology, University of Pittsburgh School of Medicine, Pittsburgh, PA 15261, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210354200400_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":"2023020210354200400_B2","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1038\/nbt1002-991","article-title":"Analyzing yeast protein-protein interaction data obtained from different sources","volume":"20","author":"Bader","year":"2003","journal-title":"Nat. Biotechnol."},{"key":"2023020210354200400_B3","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":"2023020210354200400_B4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1038\/nrg1272","article-title":"Network biology: understanding the cell's functional organization,","volume":"5","author":"Barabasi","year":"2004","journal-title":"Nat Rev Genet."},{"key":"2023020210354200400_B5","first-page":"4","article-title":"Graph kernels for disease outcome prediction from protein-protein interaction networks,","volume":"12","author":"Borgwardt","year":"2007","journal-title":"Pacific Symposium on Biocomputing"},{"key":"2023020210354200400_B6","article-title":"Tools for Large Graph Mining","volume-title":"Ph.d. thesis","author":"Chakrabarti","year":"2005"},{"key":"2023020210354200400_B7","first-page":"231","article-title":"Identifying protein complexes in high-throughput protein interaction screens using an infinite latent feature model,","volume":"11","author":"Chu","year":"2006","journal-title":"Pacific Symposium on Biocomputing"},{"key":"2023020210354200400_B8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1038\/387s067","article-title":"Genetic and physical maps of Saccharomyces cerevisiae","volume":"387","author":"Cherry","year":"1997","journal-title":"Nature"},{"key":"2023020210354200400_B9","article-title":"Introduction to algorithms (Second Edition)","volume-title":"McGraw-Hill","author":"Cormen","year":"2001"},{"key":"2023020210354200400_B10","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":"2023020210354200400_B11","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":"2023020210354200400_B12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1038\/415180a","article-title":"Systematic identification of protein complexes inSaccharomyces cerevisiaeby mass spectrometry","volume":"415","author":"Ho","year":"2002","journal-title":"Nature"},{"key":"2023020210354200400_B13","doi-asserted-by":"crossref","first-page":"S233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","article-title":"Discovering regulatory and signalling circuits in molecular interaction networks","volume":"18","author":"Ideker","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020210354200400_B14","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":"10","author":"Ito","year":"2001","journal-title":"Proc. Natl Acad. Sci."},{"key":"2023020210354200400_B15","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1126\/science.1087361","article-title":"A Bayesian networks approach for predicting protein-protein interactions from genomic data","volume":"302","author":"Jansen","year":"2003","journal-title":"Science"},{"key":"2023020210354200400_B16","article-title":"Learning to classify text using support vector machines","volume-title":"PhD Thesis","author":"Joachims","year":"2001"},{"key":"2023020210354200400_B17","volume-title":"Information Retrieval Experimental","author":"Jones","year":"1981"},{"key":"2023020210354200400_B18","first-page":"1938","article-title":"Relating three-dimensional structures to protein networks provides evolutionary insights","volume":"314","author":"Kim","year":"2006"},{"key":"2023020210354200400_B19","doi-asserted-by":"crossref","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","article-title":"Protein complex prediction via cost-based clustering","volume":"20","author":"King","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020210354200400_B20","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in yeast Saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023020210354200400_B21","article-title":"Foundations of Statistical Natural Language Processing","author":"Manning","year":"1999"},{"key":"2023020210354200400_B22","doi-asserted-by":"crossref","first-page":"D41","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":"2023020210354200400_B23","doi-asserted-by":"crossref","first-page":"861","DOI":"10.2174\/0929867003374534","article-title":"Towards 3D structures of G protein-coupled receptors: a multidisciplinary approach","volume":"7","author":"Muller","year":"2000","journal-title":"Curr. Med. Chem"},{"key":"2023020210354200400_B24","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1002\/prot.10505","article-title":"Detection of functional modules from protein interaction networks","volume":"54","author":"Pereira-Leal","year":"2004","journal-title":"Proteins"},{"key":"2023020210354200400_B25","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Przulj","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210354200400_B26","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1002\/prot.20865","article-title":"Evaluation of different biological data and computational classification methods for use in protein interaction prediction","volume":"63","author":"Qi","year":"2006","journal-title":"Proteins"},{"key":"2023020210354200400_B27","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/jbiol36","article-title":"Comprehensive curation and analysis of global interaction networks in Saccharomyces cerevisiae","volume":"5","author":"Reguly","year":"2006","journal-title":"J. Biol"},{"key":"2023020210354200400_B28","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1073\/pnas.0237338100","article-title":"Modular organization of cellular networks","volume":"100","author":"Rives","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020210354200400_B29","article-title":"A workshop on exponential random graph (p*) models for social networks","author":"Robins","year":"2005"},{"key":"2023020210354200400_B30","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1038\/nature04209","article-title":"Towards a proteome-scale map of the human protein-protein interaction network","volume":"437","author":"Rual","year":"2005","journal-title":"Nature"},{"key":"2023020210354200400_B31","doi-asserted-by":"crossref","first-page":"3548","DOI":"10.1093\/bioinformatics\/bti567","article-title":"Local modeling of global interactome networks","volume":"21","author":"Scholtens","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210354200400_B32","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1089\/cmb.2005.12.835","article-title":"Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data","volume":"12","author":"Sharan","year":"2005","journal-title":"J. Comput. Biol"},{"key":"2023020210354200400_B33","doi-asserted-by":"crossref","first-page":"12123","DOI":"10.1073\/pnas.2032324100","article-title":"Protein complexes and functional modules in molecular networks","volume":"100","author":"Spirin","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020210354200400_B34","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1016\/j.cell.2005.08.029","article-title":"A human protein-protein interaction network: a resource for annotating the proteome","volume":"122","author":"Stelzl","year":"2005","journal-title":"Cell"},{"key":"2023020210354200400_B35","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":"2000","journal-title":"Nature"},{"key":"2023020210354200400_B36","article-title":"Properties of nonuniform random graph models","volume-title":"Research Report. Helsinki University of Technology, Laboratory for Theoretical Computer Science","author":"Virtanen","year":"2003"},{"key":"2023020210354200400_B37","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":"2023020210354200400_B38","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/0092-8674(89)90249-3","article-title":"The STE4 and STE18 genes of yeast encode potential beta and gamma subunits of the mating factor receptor-coupled G protein","volume":"56","author":"Whiteway","year":"1989","journal-title":"Cell"},{"key":"2023020210354200400_B39","article-title":"Data Mining: Practical machine learning tools with Java implementations","author":"Witten","year":"2000"},{"key":"2023020210354200400_B40","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/nar\/30.1.303","article-title":"DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions","volume":"30","author":"Xenarios","year":"2002","journal-title":"Nucleic Acids Res"},{"key":"2023020210354200400_B41","article-title":"gSpan: Graph-based substructure pattern mining","volume-title":"Technical Report UIUCDCS-R-2002-2296","author":"Yan","year":"2002"},{"key":"2023020210354200400_B42","doi-asserted-by":"crossref","first-page":"5934","DOI":"10.1073\/pnas.0306752101","article-title":"Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction","volume":"101","author":"Yeger-Lotem","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020210354200400_B43","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1471-2105-6-8","article-title":"Structural comparison of metabolic networks in selected single cell organisms","volume":"6","author":"Zhu","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023020210354200400_B44","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1748-7188-1-7","article-title":"Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations","volume":"1","author":"Zotenko","year":"2006","journal-title":"Algorithms Mol. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i250\/49051192\/bioinformatics_24_13_i250.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i250\/49051192\/bioinformatics_24_13_i250.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:13:20Z","timestamp":1675340000000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i250\/232278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":44,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn164","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}