{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:22:38Z","timestamp":1764688958789},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Identifying functional modules in protein\u2013protein interaction (PPI) networks may shed light on cellular functional organization and thereafter underlying cellular mechanisms. Many existing module identification algorithms aim to detect densely connected groups of proteins as potential modules. However, based on this simple topological criterion of \u2018higher than expected connectivity\u2019, those algorithms may miss biologically meaningful modules of functional significance, in which proteins have similar interaction patterns to other proteins in networks but may not be densely connected to each other. A few blockmodel module identification algorithms have been proposed to address the problem but the lack of global optimum guarantee and the prohibitive computational complexity have been the bottleneck of their applications in real-world large-scale PPI networks.<\/jats:p>\n               <jats:p>Results: In this article, we propose a novel optimization formulation LCP2 (low two-hop conductance sets) using the concept of Markov random walk on graphs, which enables simultaneous identification of both dense and sparse modules based on protein interaction patterns in given networks through searching for LCP2 by random walk. A spectral approximate algorithm SLCP2 is derived to identify non-overlapping functional modules. Based on a bottom-up greedy strategy, we further extend LCP2 to a new algorithm (greedy algorithm for LCP2) GLCP2 to identify overlapping functional modules. We compare SLCP2 and GLCP2 with a range of state-of-the-art algorithms on synthetic networks and real-world PPI networks. The performance evaluation based on several criteria with respect to protein complex prediction, high level Gene Ontology term prediction and especially sparse module detection, has demonstrated that our algorithms based on searching for LCP2 outperform all other compared algorithms.<\/jats:p>\n               <jats:p>Availability and implementation: All data and code are available at http:\/\/www.cse.usf.edu\/\u223cxqian\/fmi\/slcp2hop\/.<\/jats:p>\n               <jats:p>Contact: \u00a0yijie@mail.usf.edu or xqian@ece.tamu.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt569","type":"journal-article","created":{"date-parts":[[2013,10,2]],"date-time":"2013-10-02T00:44:01Z","timestamp":1380674641000},"page":"81-93","source":"Crossref","is-referenced-by-count":41,"title":["Functional module identification in protein interaction networks by interaction patterns"],"prefix":"10.1093","volume":"30","author":[{"given":"Yijie","family":"Wang","sequence":"first","affiliation":[{"name":"1 Department of Computer Science and Engineering, University of South Florida, Tampa, FL 33620, USA and 2Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA"}]},{"given":"Xiaoning","family":"Qian","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and Engineering, University of South Florida, Tampa, FL 33620, USA and 2Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA"},{"name":"1 Department of Computer Science and Engineering, University of South Florida, Tampa, FL 33620, USA and 2Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA"}]}],"member":"286","published-online":{"date-parts":[[2013,10,1]]},"reference":[{"key":"2023012710383699600_btt569-B1","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1038\/nature09182","article-title":"Link communities reveal multiscale complexity in networks","volume":"466","author":"Ahn","year":"2010","journal-title":"Nature"},{"key":"2023012710383699600_btt569-B2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology. the gene ontology consortium","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023012710383699600_btt569-B3","article-title":"Parallel clustering algorithms with application to climatology","volume-title":"Technical report","author":"Bisgin","year":"2008"},{"key":"2023012710383699600_btt569-B4","doi-asserted-by":"crossref","first-page":"D637","DOI":"10.1093\/nar\/gkm1001","article-title":"The BioGRID Interaction Database: 2008 update","volume":"36","author":"Breitkreutz","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B5","doi-asserted-by":"crossref","first-page":"4164","DOI":"10.1073\/pnas.0308531101","article-title":"Metagenes and molecular pattern discovery using matrix factorization","volume":"101","author":"Brunet","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012710383699600_btt569-B6","doi-asserted-by":"crossref","first-page":"258701","DOI":"10.1103\/PhysRevLett.100.258701","article-title":"A bayesian approach to network modularity","volume":"100","author":"Hofman","year":"2008","journal-title":"Phys. Rev. Lett."},{"key":"2023012710383699600_btt569-B7","doi-asserted-by":"crossref","first-page":"D577","DOI":"10.1093\/nar\/gkm909","article-title":"Gene ontology annotations at SGD: new data sources and annotation methods","volume":"36","author":"Hong","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B8","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1752-0509-6-S2-S7","article-title":"PCDq: human protein complex database with quality index which summarizes different levels of evidences of protein complexes predicted from H-invitational protein-protein interactions integrative dataset","volume":"6","author":"Kikugawa","year":"2012","journal-title":"BMC Syst. Biol."},{"key":"2023012710383699600_btt569-B9","article-title":"Conductance and rapidly mixing markov chains","volume-title":"Technical report","author":"King","year":"2003"},{"key":"2023012710383699600_btt569-B10","doi-asserted-by":"crossref","first-page":"033015","DOI":"10.1088\/1367-2630\/11\/3\/033015","article-title":"Detecting the overlapping and hierarchical community structure in complex networks","volume":"11","author":"Lancichinetti","year":"2009","journal-title":"New J. Phys."},{"key":"2023012710383699600_btt569-B11","doi-asserted-by":"crossref","first-page":"S3","DOI":"10.1186\/1471-2164-11-S1-S3","article-title":"Computational approaches for detecting protein complexes from protein interaction networks: a survey","volume":"11","author":"Li","year":"2010","journal-title":"BMC Genomics"},{"key":"2023012710383699600_btt569-B12","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1126\/science.1065103","article-title":"Specificity and stability in topology of protein networks","volume":"296","author":"Maslov","year":"2002","journal-title":"Science"},{"key":"2023012710383699600_btt569-B13","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":"2023012710383699600_btt569-B14","doi-asserted-by":"crossref","first-page":"2012","DOI":"10.1093\/bioinformatics\/btl338","article-title":"A lock-and-key model for protein-protein interactions","volume":"22","author":"Morrison","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012710383699600_btt569-B15","first-page":"419","article-title":"Graph summarization with bounded error","volume-title":"Processing of the 33rd International Conference on Management of Data (ACM SIGMOD Conference)","author":"Navlakha","year":"2008"},{"key":"2023012710383699600_btt569-B16","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1089\/cmb.2008.11TT","article-title":"Revealing biological modules via graph summarization","volume":"16","author":"Navlakha","year":"2009","journal-title":"J. Comp. Biol."},{"key":"2023012710383699600_btt569-B17","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1038\/nmeth.1938","article-title":"Detecting overlapping protein complexes in protein-protein interaction networks","volume":"9","author":"Nepusz","year":"2012","journal-title":"Nat. Methods"},{"key":"2023012710383699600_btt569-B18","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2023012710383699600_btt569-B19","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2023012710383699600_btt569-B20","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1128\/mr.59.1.94-123.1995","article-title":"Protein-protein interactions: methods for detection and analysis","volume":"59","author":"Phizicky","year":"1995","journal-title":"Microbiol. Rev."},{"key":"2023012710383699600_btt569-B21","doi-asserted-by":"crossref","first-page":"e1000659","DOI":"10.1371\/journal.pcbi.1000659","article-title":"Protein interaction networks: more than mere modules","volume":"6","author":"Pinkert","year":"2010","journal-title":"PLoS Comput. Biol."},{"key":"2023012710383699600_btt569-B22","first-page":"165","article-title":"Fibroblast growth factors, their receptors and signaling","volume":"7","author":"Powers","year":"2002","journal-title":"Endocr. Relat.Cancer"},{"key":"2023012710383699600_btt569-B23","doi-asserted-by":"crossref","first-page":"D767","DOI":"10.1093\/nar\/gkn892","article-title":"Human Protein Reference Database\u20142009 update","volume":"37","author":"Prasad","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1759-4499-2-2","article-title":"Construction and analysis of protein\u2013protein interaction networks","volume":"2","author":"Raman","year":"2010","journal-title":"Autom. Exp."},{"key":"2023012710383699600_btt569-B25","volume-title":"Structure in Complex Networks","author":"Reichardt","year":"2009"},{"key":"2023012710383699600_btt569-B26","doi-asserted-by":"crossref","first-page":"e1000807","DOI":"10.1371\/journal.pcbi.1000807","article-title":"Protein\u2013protein interactions essentials: Key concepts to building and analyzing interactome networks","volume":"6","author":"Rivas","year":"2010","journal-title":"PLoS Comput. Biol."},{"key":"2023012710383699600_btt569-B27","doi-asserted-by":"crossref","first-page":"e1000108","DOI":"10.1371\/journal.pcbi.1000108","article-title":"Unraveling protein networks with power graph analysis","volume":"4","author":"Royer","year":"2008","journal-title":"PLoS Comput. Biol."},{"key":"2023012710383699600_btt569-B28","doi-asserted-by":"crossref","first-page":"D646","DOI":"10.1093\/nar\/gkm936","article-title":"Corum: the comprehensive resource of mammalian protein complexes","volume":"36","author":"Ruepp","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B29","doi-asserted-by":"crossref","first-page":"D449","DOI":"10.1093\/nar\/gkh086","article-title":"The Database of Interacting Proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B30","doi-asserted-by":"crossref","DOI":"10.1145\/1557019.1557101","article-title":"Scalable graph clustering using stochastic flows: Applications to community discovery","volume-title":"15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201909)","author":"Satuluri","year":"2009"},{"key":"2023012710383699600_btt569-B31","doi-asserted-by":"crossref","DOI":"10.1145\/1951365.1951407","article-title":"Symmetrizations for clustering directed graphs","volume-title":"14th International Conference on Extending Database Technology (EDBT11)","author":"Satuluri","year":"2011"},{"key":"2023012710383699600_btt569-B32","article-title":"Markov clustering of protein interaction networks","volume-title":"ACM Conference on Bioinformatics, Computational Biology and Biomedicine 2010","author":"Satuluri","year":"2010"},{"key":"2023012710383699600_btt569-B33","doi-asserted-by":"crossref","first-page":"i473","DOI":"10.1093\/bioinformatics\/bts370","article-title":"Identifying functional modules in interaction networks through overlapping markov clustering","volume":"28","author":"Shih","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012710383699600_btt569-B34","doi-asserted-by":"crossref","first-page":"D535","DOI":"10.1093\/nar\/gkj109","article-title":"BioGRID: a general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012710383699600_btt569-B35","article-title":"A cluster algorithm for graphs","volume-title":"Technical Report INS-R0010","author":"van Dongen","year":"2000"},{"key":"2023012710383699600_btt569-B36","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1186\/1471-2105-10-297","article-title":"Finding local communities in protein networks","volume":"10","author":"Voevodski","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012710383699600_btt569-B37","doi-asserted-by":"crossref","DOI":"10.1145\/2382936.2382952","article-title":"Functional module identification by block modeling using simulated annealing with path relinking","volume-title":"ACM Conference on Bioinformatics, Computational Biology and Biomedicine 2012","author":"Wang","year":"2012"},{"key":"2023012710383699600_btt569-B38","doi-asserted-by":"crossref","first-page":"S23","DOI":"10.1186\/1471-2105-14-S2-S23","article-title":"A novel subgradient-based optimization algorithm for block model functional module identification","volume":"14","author":"Wang","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023012710383699600_btt569-B39","article-title":"On semidefinite relaxation for normalized k-cut and connections to spectral clustering","volume-title":"Technical report UCB\/CSD-03-1265","author":"Xing","year":"2003"},{"key":"2023012710383699600_btt569-B40","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1126\/science.275.5303.1129","article-title":"Prevention of apoptosis by Bcl-2: release of cytochrome c from mitochondria blocked","volume":"275","author":"Yang","year":"1997","journal-title":"Science"},{"key":"2023012710383699600_btt569-B41","first-page":"1057","article-title":"Spectral relaxation for k-means clustering","volume-title":"Advances in Neural Information Processing Systems","author":"Zha","year":"2001"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/1\/81\/48913722\/bioinformatics_30_1_81.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/1\/81\/48913722\/bioinformatics_30_1_81.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T10:42:53Z","timestamp":1674816173000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/1\/81\/235709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt569","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,1,1]]},"published":{"date-parts":[[2013,10,1]]}}}