{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:32:28Z","timestamp":1768318348622,"version":"3.49.0"},"reference-count":54,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2790,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Modern systems biology aims at understanding how the different molecular components of a biological cell interact. Often, cellular functions are performed by complexes consisting of many different proteins. The composition of these complexes may change according to the cellular environment, and one protein may be involved in several different processes. The automatic discovery of functional complexes from protein interaction data is challenging. While previous approaches use approximations to extract dense modules, our approach exactly solves the problem of dense module enumeration. Furthermore, constraints from additional information sources such as gene expression and phenotype data can be integrated, so we can systematically mine for dense modules with interesting profiles.<\/jats:p>\n               <jats:p>Results: Given a weighted protein interaction network, our method discovers all protein sets that satisfy a user-defined minimum density threshold. We employ a reverse search strategy, which allows us to exploit the density criterion in an efficient way. Our experiments show that the novel approach is feasible and produces biologically meaningful results. In comparative validation studies using yeast data, the method achieved the best overall prediction performance with respect to confirmed complexes. Moreover, by enhancing the yeast network with phenotypic and phylogenetic profiles and the human network with tissue-specific expression data, we identified condition-dependent complex variants.<\/jats:p>\n               <jats:p>Availability: A C++ implementation of the algorithm is available at http:\/\/www.kyb.tuebingen.mpg.de\/~georgii\/dme.html.<\/jats:p>\n               <jats:p>Contact: \u00a0koji.tsuda@tuebingen.mpg.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp080","type":"journal-article","created":{"date-parts":[[2009,2,13]],"date-time":"2009-02-13T01:13:32Z","timestamp":1234487612000},"page":"933-940","source":"Crossref","is-referenced-by-count":72,"title":["Enumeration of condition-dependent dense modules in protein interaction networks"],"prefix":"10.1093","volume":"25","author":[{"given":"Elisabeth","family":"Georgii","sequence":"first","affiliation":[{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"},{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabine","family":"Dietmann","sequence":"additional","affiliation":[{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Pagel","sequence":"additional","affiliation":[{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Koji","family":"Tsuda","sequence":"additional","affiliation":[{"name":"1 Max Planck Institute for Biological Cybernetics, T\u00fcbingen, 2Friedrich Miescher Laboratory of the Max Planck Society, T\u00fcbingen, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Center Munich, Neuherberg, Germany and 4National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,2,11]]},"reference":[{"key":"2023013110164735500_B1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","article-title":"Reverse search for enumeration","volume":"65","author":"Avis","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"2023013110164735500_B2","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":"2023013110164735500_B3","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1093\/nar\/gkg056","article-title":"BIND: the Biomolecular Interaction Network Database","volume":"31","author":"Bader","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B4","doi-asserted-by":"crossref","first-page":"R22","DOI":"10.1186\/gb-2003-4-3-r22","article-title":"Osprey: a network visualization system","volume":"4","author":"Breitkreutz","year":"2003","journal-title":"Genome Biol."},{"key":"2023013110164735500_B5","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1016\/S0960-9822(00)80020-2","article-title":"Identification of a family of human f-box proteins","volume":"9","author":"Cenciarelli","year":"1999","journal-title":"Curr. Biol."},{"issue":"Suppl.1","key":"2023013110164735500_B6","doi-asserted-by":"crossref","first-page":"D572","DOI":"10.1093\/nar\/gkl950","article-title":"MINT: the Molecular INTeraction database","volume":"35","author":"Chatr-aryamontri","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B7","doi-asserted-by":"crossref","first-page":"5824","DOI":"10.1093\/emboj\/19.21.5824","article-title":"A protein complex containing tho2, hpr1, mft1 and a novel protein, thp2, connects transcription elongation with mitotic recombination in saccharomyces cerevisiae","volume":"19","author":"Chavez","year":"2000","journal-title":"EMBO J."},{"key":"2023013110164735500_B8","doi-asserted-by":"crossref","first-page":"2283","DOI":"10.1093\/bioinformatics\/btl370","article-title":"Detecting functional modules in the yeast protein-protein interaction network","volume":"22","author":"Chen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013110164735500_B9","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1038\/msb4100180","article-title":"Network-based classification of breast cancer metastasis","volume":"3","author":"Chuang","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023013110164735500_B10","doi-asserted-by":"crossref","first-page":"2005 0001","DOI":"10.1038\/msb4100004","article-title":"A global view of pleiotropy and phenotypically derived gene function in yeast","volume":"1","author":"Dudley","year":"2005","journal-title":"Mol. Syst. Biol."},{"key":"2023013110164735500_B11","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1042\/BJ20051213","article-title":"Purification and characterization of the three snf1-activating kinases of saccharomyces cerevisiae","volume":"393","author":"Elbing","year":"2006","journal-title":"Biochem J."},{"key":"2023013110164735500_B12","doi-asserted-by":"crossref","first-page":"e117","DOI":"10.1093\/bioinformatics\/btl260","article-title":"Dense subgraph computation via stochastic search: application to detect transcriptional modules","volume":"22","author":"Everett","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013110164735500_B13","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1088\/1367-2630\/9\/6\/180","article-title":"Weighted network modules","volume":"9","author":"Farkas","year":"2007","journal-title":"New J. Phys."},{"key":"2023013110164735500_B14","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":"2023013110164735500_B15","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"},{"issue":"Suppl. 1","key":"2023013110164735500_B16","first-page":"D364","article-title":"CYGD: the Comprehensive Yeast Genome Database","volume":"33","author":"Guldener","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B17","doi-asserted-by":"crossref","first-page":"D436","DOI":"10.1093\/nar\/gkj003","article-title":"Mpact: the mips protein interaction resource on yeast","volume":"34","author":"Guldener","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B18","volume-title":"Data Mining: Concepts and Techniques","author":"Han","year":"2006","edition":"2"},{"issue":"Suppl. 1","key":"2023013110164735500_B19","doi-asserted-by":"crossref","first-page":"S145","DOI":"10.1093\/bioinformatics\/18.suppl_1.S145","article-title":"Co-clustering of biological networks and gene expression data","volume":"18","author":"Hanisch","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013110164735500_B20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/11605126_4","article-title":"A method for pinpoint clustering of web pages with pseudo-clique search","volume-title":"Federation over the Web","author":"Haraguchi","year":"2006"},{"issue":"Suppl. 1","key":"2023013110164735500_B21","doi-asserted-by":"crossref","first-page":"D452","DOI":"10.1093\/nar\/gkh052","article-title":"IntAct: an open source molecular interaction database","volume":"32","author":"Hermjakob","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B22","doi-asserted-by":"crossref","first-page":"i222","DOI":"10.1093\/bioinformatics\/btm222","article-title":"Systematic discovery of functional modules and context-specific functional annotation of human genome","volume":"23","author":"Huang","year":"2007","journal-title":"Bioinformatics"},{"issue":"Suppl. 1","key":"2023013110164735500_B23","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":"2023013110164735500_B24","volume-title":"Immunobiology: Immune System in Health and Disease","author":"Janeway","year":"2005"},{"key":"2023013110164735500_B25","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":"2023013110164735500_B26","doi-asserted-by":"crossref","DOI":"10.1186\/gb-2000-1-5-reviews3002","article-title":"The f-box protein family","volume":"1","author":"Kipreos","year":"2000","journal-title":"Genome Biol."},{"key":"2023013110164735500_B27","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1126\/science.1065203","article-title":"Phosphorylation-dependent ubiquitination of cyclin E by the SCFFbw7 Ubiquitin ligase","volume":"294","author":"Koepp","year":"2001","journal-title":"Science"},{"key":"2023013110164735500_B28","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1089\/cmb.2007.R014","article-title":"Assessing significance of connectivity and conservation in protein interaction networks","volume":"14","author":"Koyuturk","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023013110164735500_B29","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":"2023013110164735500_B30","doi-asserted-by":"crossref","first-page":"1447","DOI":"10.1242\/jcs.114.8.1447","article-title":"Initiating DNA synthesis: from recruiting to activating the mcm complex","volume":"114","author":"Lei","year":"2001","journal-title":"J. Cell Sci."},{"key":"2023013110164735500_B31","doi-asserted-by":"crossref","first-page":"4956","DOI":"10.1093\/nar\/28.24.4956","article-title":"A role for MHR1, a gene required for mitochondrial genetic recombination, in the repair of damage spontaneously introduced in yeast mtDNA","volume":"28","author":"Ling","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B32","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl Acad. Sci. USA"},{"issue":"Suppl. 1","key":"2023013110164735500_B33","first-page":"D476","article-title":"Inparanoid: a comprehensive database of eukaryotic orthologs","volume":"33","author":"O'Brien","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B34","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1038\/22350","article-title":"The chromatin-specific transcription elongation factor fact comprises human spt16 and ssrp1 proteins","volume":"400","author":"Orphanides","year":"1999","journal-title":"Nature"},{"key":"2023013110164735500_B35","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":"2023013110164735500_B36","first-page":"353","article-title":"Mining cross-graph quasi-cliques in gene expression and protein interaction data","volume-title":"ICDE '05: Proceedings of the 21st International Conference on Data Engineering (ICDE'05)","author":"Pei","year":"2005"},{"issue":"Suppl. 1","key":"2023013110164735500_B37","doi-asserted-by":"crossref","first-page":"D497","DOI":"10.1093\/nar\/gkh070","article-title":"Human protein reference database as a discovery resource for proteomics","volume":"32","author":"Peri","year":"2004","journal-title":"Nucleic Acids Res."},{"issue":"Suppl. 1","key":"2023013110164735500_B38","first-page":"D646","article-title":"CORUM: the comprehensive resource of mammalian protein complexes","volume":"36","author":"Ruepp","year":"2008","journal-title":"Nucleic Acids Res."},{"issue":"Suppl. 1","key":"2023013110164735500_B39","doi-asserted-by":"crossref","first-page":"i264","DOI":"10.1093\/bioinformatics\/btg1037","article-title":"Discovering molecular pathways from protein interaction and gene expression data","volume":"19","author":"Segal","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013110164735500_B40","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1186\/1471-2105-6-232","article-title":"Expander - an integrative program suite for microarray data analysis","volume":"6","author":"Shamir","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023013110164735500_B41","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023013110164735500_B42","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":"2023013110164735500_B43","doi-asserted-by":"crossref","first-page":"6062","DOI":"10.1073\/pnas.0400782101","article-title":"A gene atlas of the mouse and human protein-encoding transcriptomes","volume":"101","author":"Su","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013110164735500_B44","doi-asserted-by":"crossref","first-page":"2981","DOI":"10.1073\/pnas.0308661100","article-title":"Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data","volume":"101","author":"Tanay","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013110164735500_B45","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1752-0509-1-8","article-title":"Identification of functional modules using network topology and high-throughput data","volume":"1","author":"Ulitsky","year":"2007","journal-title":"BMC Syst. Biol."},{"key":"2023013110164735500_B46","first-page":"402","article-title":"An efficient algorithm for enumerating pseudo cliques","author":"Uno","year":"2007","journal-title":"Proceedings of ISAAC 2007"},{"key":"2023013110164735500_B47","article-title":"Graph Clustering by Flow Simulation","volume-title":"PhD. Thesis","author":"van Dongen","year":"2000"},{"key":"2023013110164735500_B48","doi-asserted-by":"crossref","first-page":"6672","DOI":"10.1093\/emboj\/18.23.6672","article-title":"Gal83 mediates the interaction of the snf1 kinase complex with the transcription activator sip4","volume":"18","author":"Vincent","year":"1999","journal-title":"EMBO J."},{"key":"2023013110164735500_B49","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1083\/jcb.151.3.551","article-title":"New component of the vacuolar class C-Vps complex couples nucleotide exchange on the Ypt7 GTPase to SNARE-dependent docking and fusion","volume":"151","author":"Wurmser","year":"2000","journal-title":"J. Cell Biol."},{"key":"2023013110164735500_B50","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1093\/nar\/28.1.289","article-title":"Dip: the database of interacting proteins","volume":"28","author":"Xenarios","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023013110164735500_B51","doi-asserted-by":"crossref","first-page":"i577","DOI":"10.1093\/bioinformatics\/btm227","article-title":"A graph-based approach to systematically reconstruct human transcriptional regulatory modules","volume":"23","author":"Yan","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013110164735500_B52","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1145\/1150402.1150506","article-title":"Coherent closed quasi-clique discovery from large dense graph databases","volume-title":"KDD '06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Zeng","year":"2006"},{"key":"2023013110164735500_B53","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1145\/1066157.1066236","article-title":"Tricluster: an effective algorithm for mining coherent clusters in 3d microarray data","volume-title":"SIGMOD '05: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data","author":"Zhao","year":"2005"},{"key":"2023013110164735500_B54","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1016\/S1097-2765(02)00784-0","article-title":"Cand1 binds to unneddylated cul1 and regulates the formation of scf ubiquitin e3 ligase complex","volume":"10","author":"Zheng","year":"2002","journal-title":"Mol. Cell."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/7\/933\/48983782\/bioinformatics_25_7_933.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/7\/933\/48983782\/bioinformatics_25_7_933.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T20:22:15Z","timestamp":1675196535000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/7\/933\/210757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,11]]},"references-count":54,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2009,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp080","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,4,1]]},"published":{"date-parts":[[2009,2,11]]}}}