{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T10:04:29Z","timestamp":1774865069445,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1490,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: In recent years, Markov clustering (MCL) has emerged as an effective algorithm for clustering biological networks\u2014for instance clustering protein\u2013protein interaction (PPI) networks to identify functional modules. However, a limitation of MCL and its variants (e.g. regularized MCL) is that it only supports hard clustering often leading to an impedance mismatch given that there is often a significant overlap of proteins across functional modules.<\/jats:p>\n               <jats:p>Results: In this article, we seek to redress this limitation. We propose a soft variation of Regularized MCL (R-MCL) based on the idea of iteratively (re-)executing R-MCL while ensuring that multiple executions do not always converge to the same clustering result thus allowing for highly overlapped clusters. The resulting algorithm, denoted soft regularized Markov clustering, is shown to outperform a range of extant state-of-the-art approaches in terms of accuracy of identifying functional modules on three real PPI networks.<\/jats:p>\n               <jats:p>Availability: All data and codes are freely available upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0srini@cse.ohio-state.edu<\/jats:p>\n               <jats:p>Supplementary Information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts370","type":"journal-article","created":{"date-parts":[[2012,9,7]],"date-time":"2012-09-07T20:35:22Z","timestamp":1347050122000},"page":"i473-i479","source":"Crossref","is-referenced-by-count":97,"title":["Identifying functional modules in interaction networks through overlapping Markov clustering"],"prefix":"10.1093","volume":"28","author":[{"given":"Yu-Keng","family":"Shih","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, the Ohio State University, Columbus 43210-1277, OH USA."}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, the Ohio State University, Columbus 43210-1277, OH USA."}]}],"member":"286","published-online":{"date-parts":[[2012,9,3]]},"reference":[{"key":"2023012513013979600_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":"2023012513013979600_B2","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":"2023012513013979600_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":"2023012513013979600_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":"2023012513013979600_B5","doi-asserted-by":"crossref","first-page":"i29","DOI":"10.1093\/bioinformatics\/btm212","article-title":"An ensemble framework for clustering protein\u2013protein interaction networks","volume":"23","author":"Asur","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012513013979600_B6","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":"2023012513013979600_B7","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1186\/1471-2105-7-488","article-title":"Evaluation of clustering algorithms for protein\u2013protein interaction networks","volume":"7","author":"Brohee","year":"2006","journal-title":"BMC Bioinformatics"},{"issue":"Suppl 1","key":"2023012513013979600_B8","doi-asserted-by":"crossref","first-page":"S25","DOI":"10.1186\/1471-2105-11-S1-S25","article-title":"A hub-attachment based method to detect functional modules from confidence-scored protein interactions and expression profiles","volume":"11","author":"Chin","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012513013979600_B9","article-title":"Graph clustering by flow simulation","author":"Dongen","year":"2000"},{"key":"2023012513013979600_B10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Reports"},{"key":"2023012513013979600_B11","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1089\/cmb.2009.0023","article-title":"Bootstrapping the interactome: unsupervised identification of protein complexes in yeast","volume":"16","author":"Friedel","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012513013979600_B12","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":"2023012513013979600_B13","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1093\/bioinformatics\/btp080","article-title":"Enumeration of condition-dependent dense modules in protein interaction networks","volume":"25","author":"Georgii","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012513013979600_B14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-642-01206-8_5","article-title":"Finding overlapping communities using disjoint community detection algorithms","volume-title":"Complex Networks","author":"Gregory","year":"2009"},{"key":"2023012513013979600_B15","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1093\/bioinformatics\/btq078","article-title":"Spici: a fast clustering algorithm for large biological networks","volume":"26","author":"Jiang","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012513013979600_B16","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1002\/pmic.200600448","article-title":"Wiphi: a weighted yeast interactome enriched for direct physical interactions","volume":"7","author":"Kiemer","year":"2007","journal-title":"Proteomics"},{"key":"2023012513013979600_B17","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":"2023012513013979600_B18","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":"2023012513013979600_B19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1089\/cmb.2008.01TT","article-title":"Predicting protein complexes from ppi data: a core-attachment approach","volume":"16","author":"Leung","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012513013979600_B20","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1186\/1752-0509-4-100","article-title":"The function of communities in protein interaction networks at multiple scales","volume":"4","author":"Lewis","year":"2010","journal-title":"BMC Syst. Biol."},{"key":"2023012513013979600_B21","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"},{"issue":"Suppl 1","key":"2023012513013979600_B22","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":"2023012513013979600_B23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1142\/9781860948732_0019","article-title":"Discovering protein complexes in dense reliable neighborhoods of protein interaction networks","volume":"Vol. 6","author":"Li","year":"2007","journal-title":"Computational Systems Bioinformatics Conference"},{"key":"2023012513013979600_B24","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1093\/bioinformatics\/btl562","article-title":"Modular organization of protein interaction networks","volume":"23","author":"Luo","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012513013979600_B25","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1186\/1471-2105-10-283","article-title":"RRW: repeated random walks on genome-scale protein networks for local cluster discovery","volume":"10","author":"Macropol","year":"2009","journal-title":"BMC bioinformatics"},{"issue":"Suppl 1","key":"2023012513013979600_B26","doi-asserted-by":"crossref","first-page":"S14","DOI":"10.1186\/1477-5956-9-S1-S14","article-title":"NWE: node-weighted expansion for protein complex prediction using random walk distances","volume":"9","author":"Maruyama","year":"2011","journal-title":"Proteome Sci."},{"key":"2023012513013979600_B27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/BIBE.2008.4696656","article-title":"An enhanced markov clustering method for detecting protein complexes","volume-title":"8th IEEE International Conference on BioInformatics and BioEngineering (BIBE 2008): 8\u201310 October","author":"Moschopoulos","year":"2008"},{"key":"2023012513013979600_B28","first-page":"161","article-title":"Inferring protein\u2013protein interactions using interaction network topologies","volume":"Vol.1","author":"Paccanaro","year":"2005","journal-title":"IJCNN"},{"key":"2023012513013979600_B29","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":"PereiraLeal","year":"2004","journal-title":"PROTEINS: Struct Funct Bioinform"},{"issue":"Suppl 1","key":"2023012513013979600_B30","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":"2023012513013979600_B31","first-page":"737","article-title":"Scalable graph clustering using stochastic flows: applications to community discovery","volume-title":"Proceedings of SIGKDD","author":"Satuluri","year":"2009"},{"key":"2023012513013979600_B32","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1145\/1854776.1854812","article-title":"Markov clustering of protein interaction networks with improved balance and scalability","volume-title":"Proceedings of the ACM Conference on Bioinformatics and Computational Biology","author":"Satuluri","year":"2010"},{"key":"2023012513013979600_B33","first-page":"159","article-title":"Refining markov clustering for protein complex prediction by incorporating core-attachment structure","volume":"23","author":"Srihari","year":"2009","journal-title":"Genome Inform. Series"},{"issue":"Suppl 1","key":"2023012513013979600_B34","doi-asserted-by":"crossref","first-page":"D698","DOI":"10.1093\/nar\/gkq1116","article-title":"The biogrid interaction database: 2011 update","volume":"39","author":"Stark","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012513013979600_B35","first-page":"371","article-title":"Improving functional modularity in protein\u2013protein interactions graphs using hub-induced subgraphs","volume-title":"PKDD","author":"Ucar","year":"2006"},{"key":"2023012513013979600_B36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1186\/1471-2105-10-99","article-title":"Markov clustering versus affinity propagation for the partitioning of protein interaction graphs","volume":"10","author":"Vlasblom","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012513013979600_B37","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1109\/TCBB.2010.75","article-title":"A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks","volume":"8","author":"Wang","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023012513013979600_B38","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1186\/1471-2105-10-169","article-title":"A core-attachment based method to detect protein complexes in ppi networks","volume":"10","author":"Wu","year":"2009","journal-title":"BMC Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i473\/48882638\/bioinformatics_28_18_i473.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i473\/48882638\/bioinformatics_28_18_i473.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T18:50:26Z","timestamp":1674672626000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/18\/i473\/243788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,3]]},"references-count":38,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2012,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts370","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,9,15]]},"published":{"date-parts":[[2012,9,3]]}}}