{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:28:17Z","timestamp":1791916097887,"version":"4.3.4"},"reference-count":79,"publisher":"Oxford University Press (OUP)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Motivation: Protein\u2013protein interaction (PPI) networks are powerful models to represent the pairwise protein interactions of the organisms. Clustering PPI networks can be useful for isolating groups of interacting proteins that participate in the same biological processes or that perform together specific biological functions. Evolutionary orthologies can be inferred this way, as well as functions and properties of yet uncharacterized proteins.<\/jats:p>\n                  <jats:p>Results: We present an overview of the main state-of-the-art clustering methods that have been applied to PPI networks over the past decade. We distinguish five specific categories of approaches, describe and compare their main features and then focus on one of them, i.e. population-based stochastic search. We provide an experimental evaluation, based on some validation measures widely used in the literature, of techniques in this class, that are as yet less explored than the others. In particular, we study how the capability of Genetic Algorithms (GAs) to extract clusters in PPI networks varies when different topology-based fitness functions are used, and we compare GAs with the main techniques in the other categories. The experimental campaign shows that predictions returned by GAs are often more accurate than those produced by the contestant methods. Interesting issues still remain open about possible generalizations of GAs allowing for cluster overlapping.<\/jats:p>\n                  <jats:p>Availability and implementation: We point out which methods and tools described here are publicly available.<\/jats:p>\n                  <jats:p>Contact: \u00a0simona.rombo@math.unipa.it<\/jats:p>\n                  <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu034","type":"journal-article","created":{"date-parts":[[2014,1,23]],"date-time":"2014-01-23T20:25:22Z","timestamp":1390508722000},"page":"1343-1352","source":"Crossref","is-referenced-by-count":109,"title":["Algorithms and tools for protein\u2013protein interaction networks clustering, with a special focus on population-based stochastic methods"],"prefix":"10.1093","volume":"30","author":[{"given":"Clara","family":"Pizzuti","sequence":"first","affiliation":[{"name":"1 Institute for High Performance Computing and Networking (ICAR), National Research Council of Italy (CNR), Via P. Bucci 41C, 87036 Rende (CS) and 2Department of Mathematics and Computer Science, University of Palermo, Via Archirafi 34, 90123 Palermo (PA), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simona E.","family":"Rombo","sequence":"additional","affiliation":[{"name":"1 Institute for High Performance Computing and Networking (ICAR), National Research Council of Italy (CNR), Via P. Bucci 41C, 87036 Rende (CS) and 2Department of Mathematics and Computer Science, University of Palermo, Via Archirafi 34, 90123 Palermo (PA), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,1,22]]},"reference":[{"key":"2023041302470012600_","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":"2023041302470012600_","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":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/bib\/bbl022","article-title":"Graph-based methods for analyzing networks in cell biology","volume":"7","author":"Aittokallio","year":"2006","journal-title":"Brief. Bioinform."},{"key":"2023041302470012600_","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":"2023041302470012600_","first-page":"25","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Asburner","year":"2000","journal-title":"the gene ontology consortium. Nat. Genet."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/2160718.2160738","article-title":"Comparative analysis of protein networks: hard problems, practical solutions","volume":"55","author":"Atias","year":"2012","journal-title":"Commun. ACM"},{"key":"2023041302470012600_","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-protein interaction networks","volume":"4","author":"Bader","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1093\/bioinformatics\/btr621","article-title":"Multifunctional proteins revealed by overlapping clustering in protein interaction network","volume":"28","author":"Becker","year":"2012","journal-title":"Bioinformatics"},{"key":"2023041302470012600_","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":"Broh\u00e8e","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1186\/1471-2105-8-265","article-title":"Semantic integration to identify overlapping functional modules in protein interaction networks","volume":"8","author":"Cho","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1103\/PhysRevLett.94.160202","article-title":"Clique percolation in random networks","volume":"94","author":"Derenyi","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1093\/nar\/30.7.1575","article-title":"An efficient algorithm for large-scale detection of protein families","volume":"30","author":"Enright","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"016105:1","DOI":"10.1103\/PhysRevE.80.016105","article-title":"Line graphs, link partitions, and overlapping communities","volume":"80","author":"Evans","year":"2009","journal-title":"Phys. Rev. E"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1140\/epjb\/e2010-00261-8","article-title":"Line graphs of weighted networks for overlapping communities","volume":"77","author":"Evans","year":"2010","journal-title":"Eur. Phys. J. B"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1002\/prot.20799","article-title":"Edge-count probabilities for the identification of local protein communities and their organization","volume":"62","author":"Farutin","year":"2006","journal-title":"Proteins"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1109\/TCBB.2011.29","article-title":"Asymmetric comparison and querying of biological networks","volume":"8","author":"Ferraro","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023041302470012600_","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. Rep."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution limit in community detection","volume":"104","author":"Fortunato","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041302470012600_","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":"2023041302470012600_","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":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041302470012600_","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg","year":"1989"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1006\/geno.2000.6187","article-title":"An algorithm for clustering cdna fingerprints","volume":"66","author":"Hartuv","year":"2000","journal-title":"Genomics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"C47","DOI":"10.1038\/35011540","article-title":"Clustering algorithm based graph connectivity","volume":"402","author":"Hartwell","year":"1999","journal-title":"Nature"},{"key":"2023041302470012600_","volume-title":"Adaptation in Natural and Artificial Systems","author":"Holland","year":"1975"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/1748-7188-1-24","article-title":"A novel functional module detection algorithm for protein-protein interaction networks","volume":"1","author":"Hwang","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023041302470012600_","volume-title":"Algorithms for Clustering Data","author":"Jain","year":"1988"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"S18","DOI":"10.1186\/1471-2105-13-S10-S18","article-title":"A methodology for detecting the orthology signal in a PPI network at a functional complex level","volume":"13","author":"Jancura","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023041302470012600_","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":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"e12528","DOI":"10.1371\/journal.pone.0012528","article-title":"Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics","volume":"5","author":"Kovacs","year":"2010","journal-title":"PLoS One"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/1471-2105-12-24","article-title":"Graphcruch 2: Software tool for network modeling, alignment and clustering","volume":"12","author":"Kuchaiev","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","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":"2023041302470012600_","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 network: a survey","volume":"11","author":"Li","year":"2010","journal-title":"BMC Genomics"},{"key":"2023041302470012600_","first-page":"260","article-title":"Interaction graph mining for protein complexes using local clique merging","volume":"16","author":"Li","year":"2005","journal-title":"Genome Inform."},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","article-title":"Clustering methods in protein-protein interaction network","volume-title":"Knowledge Discovery in Bioinformatics: Techniques, Methods and Application","author":"Lin","year":"2006"},{"key":"2023041302470012600_","first-page":"858","article-title":"Clustering protein interaction data through chaotic genetic algorithm","volume-title":"Proceedings 6th International Conference, SEAL 2006, Hefei, China, October 15-18, 2006","author":"Liu","year":"2006"},{"key":"2023041302470012600_","first-page":"353","article-title":"Random walks on graphs: a survey","volume-title":"Combinatorics, Paul Erdos is Eighty","author":"Lovasz","year":"1996"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1002\/prot.21071","article-title":"Combining functional and topological properties to identify core modules in protein interaction networks","volume":"64","author":"Lubovac","year":"2006","journal-title":"Proteins"},{"key":"2023041302470012600_","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"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/TCBB.2004.2","article-title":"Biclustering algorithms for biological data analysis: a survey","volume":"1","author":"Madeira","year":"2004","journal-title":"IEEE Trans. Comp. Biol. Bioinf."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1093\/nar\/28.1.37","article-title":"MIPS: a database for genomes and protein sequences","volume":"28","author":"Mewes","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1093\/nar\/gkj148","article-title":"MIPS: analysis and annotation of proteins from whole genomes in 2005","volume":"34","author":"Mewes","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4137\/CIN.S680","article-title":"Uncovering biological network function via graphlet degree signatures","volume":"6","author":"Milenkovic","year":"2008","journal-title":"Cancer Inform."},{"key":"2023041302470012600_","first-page":"026113","article-title":"Finding and evaluating community structure in networks","volume":"E69","author":"Newman","year":"2004","journal-title":"Phys. Rev."},{"key":"2023041302470012600_","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":"Pxalla","year":"2005","journal-title":"Nature"},{"key":"2023041302470012600_","article-title":"Searching for repetitions in biological networks: methods, resources and tools","author":"Panni","year":"2013","journal-title":"Brief. Bioinform"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/1756-0381-4-10","article-title":"Using graph theory to analyze biological networks","volume":"4","author":"Pavlopoulos","year":"2011","journal-title":"BioData Min."},{"key":"2023041302470012600_","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","year":"2004","journal-title":"Proteins"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1109\/TCBB.2011.158","article-title":"A coclustering approach for mining large protein-protein interaction networks","volume":"9","author":"Pizzuti","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","article-title":"Functional topology in a network of protein interactions","volume-title":"Knowledge Discovery in Proteomics","author":"Pr\u017eulj","year":"2005"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj","year":"2007","journal-title":"Bioinformatics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"2658","DOI":"10.1073\/pnas.0400054101","article-title":"Defining and identifying communities in networks","volume":"101","author":"Radicchi","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041302470012600_"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"016104","DOI":"10.1103\/PhysRevE.77.016104","article-title":"Identifying network communities with a high resolution","volume":"77","author":"Ruan","year":"2008","journal-title":"Phys. Rev. E"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"12579","DOI":"10.1073\/pnas.2132527100","article-title":"Predicting protein functions from redundancies in large-scale protein interaction networks","volume":"100","author":"Samantha","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Survey: graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"2498","DOI":"10.1101\/gr.1239303","article-title":"Cytoscape: a software environment for integrated models of biomolecular interaction networks","volume":"13","author":"Shannon","year":"2003","journal-title":"Genome Res."},{"key":"2023041302470012600_","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":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1093\/bioinformatics\/bts376","article-title":"Graphlet-based edge clustering reveals pathogen-interacting proteins","volume":"28","author":"Solava","year":"2012","journal-title":"Bioinformatics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"6283","DOI":"10.1093\/nar\/gkg838","article-title":"Functional modules by relating protein interaction networks and gene expression","volume":"31","author":"Tornw","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/040608635","article-title":"Graph clustering via a discrete uncoupling process","volume":"30","author":"Van Dongen","year":"2008","journal-title":"SIAM J. Math. Anal. Appl."},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of a large-scale data sets of protein-protein interactions","volume":"31","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023041302470012600_","first-page":"S10","article-title":"Recent advances in clustering methods for protein interaction networks","volume":"11 (Suppl. 3)","author":"Wang","year":"2010","journal-title":"BMC Genomics"},{"key":"2023041302470012600_","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1126\/science.1158684","article-title":"High-quality binary protein interaction map of the yeast interactome network","volume":"322","author":"Yu","year":"2008","journal-title":"Science"},{"key":"2023041302470012600_"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/10\/1343\/49860336\/bioinformatics_30_10_1343.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/10\/1343\/49860336\/bioinformatics_30_10_1343.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,9]],"date-time":"2023-07-09T20:36:01Z","timestamp":1688934961000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/10\/1343\/266738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,22]]},"references-count":79,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2014,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu034","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,5,15]]},"published":{"date-parts":[[2014,1,22]]}}}