{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T08:58:33Z","timestamp":1769849913793,"version":"3.49.0"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2412,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Clustering algorithms play an important role in the analysis of biological networks, and can be used to uncover functional modules and obtain hints about cellular organization. While most available clustering algorithms work well on biological networks of moderate size, such as the yeast protein physical interaction network, they either fail or are too slow in practice for larger networks, such as functional networks for higher eukaryotes. Since an increasing number of larger biological networks are being determined, the limitations of current clustering approaches curtail the types of biological network analyses that can be performed.<\/jats:p>\n               <jats:p>Results: We present a fast local network clustering algorithm SPICi. SPICi runs in time O(V log V+E) and space O(E), where V and E are the number of vertices and edges in the network, respectively. We evaluate SPICi's performance on several existing protein interaction networks of varying size, and compare SPICi to nine previous approaches for clustering biological networks. We show that SPICi is typically several orders of magnitude faster than previous approaches and is the only one that can successfully cluster all test networks within very short time. We demonstrate that SPICi has state-of-the-art performance with respect to the quality of the clusters it uncovers, as judged by its ability to recapitulate protein complexes and functional modules. Finally, we demonstrate the power of our fast network clustering algorithm by applying SPICi across hundreds of large context-specific human networks, and identifying modules specific for single conditions.<\/jats:p>\n               <jats:p>Availability: Source code is available under the GNU Public License at http:\/\/compbio.cs.princeton.edu\/spici<\/jats:p>\n               <jats:p>Contact: \u00a0mona@cs.princeton.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq078","type":"journal-article","created":{"date-parts":[[2010,2,26]],"date-time":"2010-02-26T01:13:25Z","timestamp":1267146805000},"page":"1105-1111","source":"Crossref","is-referenced-by-count":208,"title":["SPICi: a fast clustering algorithm for large biological networks"],"prefix":"10.1093","volume":"26","author":[{"given":"Peng","family":"Jiang","sequence":"first","affiliation":[{"name":"1 Lewis-Sigler Institute for Integrative Genomics and 2 Department of Computer Science, Princeton University, Princeton, NJ 08544, USA"},{"name":"1 Lewis-Sigler Institute for Integrative Genomics and 2 Department of Computer Science, Princeton University, Princeton, NJ 08544, USA"}]},{"given":"Mona","family":"Singh","sequence":"additional","affiliation":[{"name":"1 Lewis-Sigler Institute for Integrative Genomics and 2 Department of Computer Science, Princeton University, Princeton, NJ 08544, USA"},{"name":"1 Lewis-Sigler Institute for Integrative Genomics and 2 Department of Computer Science, Princeton University, Princeton, NJ 08544, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,2,24]]},"reference":[{"key":"2023012508075840800_B1","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":"2023012508075840800_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":"2023012508075840800_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":"2023012508075840800_B4","doi-asserted-by":"crossref","first-page":"3251","DOI":"10.1103\/PhysRevLett.76.3251","article-title":"Superparamagnetic clustering of data","volume":"76","author":"Blatt","year":"1996","journal-title":"Phys. Rev. Lett."},{"key":"2023012508075840800_B5","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":"2023012508075840800_B6","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\u00e9e","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012508075840800_B7","doi-asserted-by":"crossref","first-page":"R6","DOI":"10.1186\/gb-2003-5-1-r6","article-title":"Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network","volume":"5","author":"Brun","year":"2003","journal-title":"Genome Biol."},{"key":"2023012508075840800_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":"2023012508075840800_B9","first-page":"178","article-title":"Dense graphlet statistics of protein interaction and random networks","author":"Colak","year":"2009","journal-title":"Pacific Symposium on Biocomputing"},{"key":"2023012508075840800_B10","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":"2023012508075840800_B11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"2023012508075840800_B12","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":"2023012508075840800_B13","doi-asserted-by":"crossref","first-page":"D412","DOI":"10.1093\/nar\/gkn760","article-title":"STRING 8\u2013a global view on proteins and their functional interactions in 630 organisms","volume":"37","author":"Jensen","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012508075840800_B14","doi-asserted-by":"crossref","first-page":"6761","DOI":"10.1038\/35011540","article-title":"From molecular to modular cell biology","volume":"402","author":"Hartwell","year":"1999","journal-title":"Nature"},{"key":"2023012508075840800_B15","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1101\/gr.082214.108","article-title":"Exploring the human genome with functional maps","volume":"19","author":"Huttenhower","year":"2009","journal-title":"Genome Res."},{"key":"2023012508075840800_B16","volume-title":"Algorithms for Clustering Data","author":"Jain","year":"1988","edition":"2nd"},{"key":"2023012508075840800_B17","doi-asserted-by":"crossref","first-page":"W445","DOI":"10.1093\/nar\/gkh407","article-title":"ArrayProspector: a web resource of functional associations inferred from microarray expression data","volume":"32","author":"Jensen","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012508075840800_B18","doi-asserted-by":"crossref","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","article-title":"An efficient algorithm for large-scale detection of protein families","volume":"20","author":"King","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012508075840800_B19","first-page":"601","article-title":"Semantic similarity measures as tools for exploring the gene ontology","volume":"8","author":"Lord","year":"2003","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012508075840800_B20","doi-asserted-by":"crossref","first-page":"i41","DOI":"10.1093\/bioinformatics\/btn174","article-title":"Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space","volume":"24","author":"Loewenstein","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508075840800_B21","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":"2023012508075840800_B22","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. Comput. Biol."},{"key":"2023012508075840800_B23","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":"2023012508075840800_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":"2023012508075840800_B25","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1038\/nrg2363","article-title":"Use and misuse of the gene ontology annotations","volume":"9","author":"Rhee","year":"2008","journal-title":"Nat. Rev. Genet."},{"key":"2023012508075840800_B26","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":"2023012508075840800_B27","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":"Samanta","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508075840800_B28","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508075840800_B29","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1093\/bioinformatics\/btp551","article-title":"How and when should interactome-derived clusters be used to predict functional modules and protein function?","volume":"25","author":"Song","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508075840800_B30","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/8\/1105\/48856064\/bioinformatics_26_8_1105.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/8\/1105\/48856064\/bioinformatics_26_8_1105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:12:10Z","timestamp":1674634330000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/8\/1105\/205979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2,24]]},"references-count":30,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq078","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,4,15]]},"published":{"date-parts":[[2010,2,24]]}}}