{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T13:45:10Z","timestamp":1778334310166,"version":"3.51.4"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Clustering protein sequence data into functionally specific families is a difficult but important problem in biological research. One useful approach for tackling this problem involves representing the sequence dataset as a protein similarity network, and afterwards clustering the network using advanced graph analysis techniques. Although a multitude of such network clustering algorithms have been developed over the past few years, comparing algorithms is often difficult because performance is affected by the specifics of network construction. We investigate an important aspect of network construction used in analyzing protein superfamilies and present a heuristic approach for improving the performance of several algorithms.<\/jats:p>\n               <jats:p>Results: We analyzed how the performance of network clustering algorithms relates to thresholding the network prior to clustering. Our results, over four different datasets, show how for each input dataset there exists an optimal threshold range over which an algorithm generates its most accurate clustering output. Our results further show how the optimal threshold range correlates with the shape of the edge weight distribution for the input similarity network. We used this correlation to develop an automated threshold selection heuristic in order to most optimally filter a similarity network prior to clustering. This heuristic allows researchers to process their protein datasets with runtime efficient network clustering algorithms without sacrificing the clustering accuracy of the final results.<\/jats:p>\n               <jats:p>Availability: Python code for implementing the automated threshold selection heuristic, together with the datasets used in our analysis, are available at http:\/\/www.rbvi.ucsf.edu\/Research\/cytoscape\/threshold_scripts.zip.<\/jats:p>\n               <jats:p>Contact: \u00a0tef@cgl.ucsf.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq655","type":"journal-article","created":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T01:14:43Z","timestamp":1291166083000},"page":"326-333","source":"Crossref","is-referenced-by-count":39,"title":["Improving the quality of protein similarity network clustering algorithms using the network edge weight distribution"],"prefix":"10.1093","volume":"27","author":[{"given":"Leonard","family":"Apeltsin","sequence":"first","affiliation":[{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John H.","family":"Morris","sequence":"additional","affiliation":[{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patricia C.","family":"Babbitt","sequence":"additional","affiliation":[{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"},{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas E.","family":"Ferrin","sequence":"additional","affiliation":[{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"},{"name":"1 Department of Pharmaceutical Chemistry and 2Department of Bioengineering and Therapeutic Sciences, University of California, San Francisco, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,11,29]]},"reference":[{"key":"2023012511545013100_B1","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023012511545013100_B2","doi-asserted-by":"crossref","first-page":"D115","DOI":"10.1093\/nar\/gkh131","article-title":"UniProt: the Universal Protein knowledgebase","volume":"32","author":"Apweiler","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012511545013100_B3","doi-asserted-by":"crossref","first-page":"e43","DOI":"10.1371\/journal.pone.0004345","article-title":"Using sequence similarity networks for visualization of relationships across diverse protein superfamilies","volume":"4","author":"Atkinson","year":"2009","journal-title":"PLoS ONE"},{"key":"2023012511545013100_B4","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":"2023012511545013100_B5","doi-asserted-by":"crossref","first-page":"R8","DOI":"10.1186\/gb-2006-7-1-r8","article-title":"A gold standard set of mechanistically diverse enzyme superfamilies","volume":"7","author":"Brown","year":"2006","journal-title":"Genome Biol."},{"key":"2023012511545013100_B6","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/1242572.1242590","article-title":"A new suffix tree similarity measure for document clustering","volume-title":"Proceedings of the 16th International Conference on World Wide Web","author":"Chim","year":"2007"},{"key":"2023012511545013100_B7","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1093\/bioinformatics\/17.9.853","article-title":"BioLayout\u2014an automatic graph layout algorithm for similarity visualization","volume":"17","author":"Enright","year":"2001","journal-title":"Bioinformatics"},{"key":"2023012511545013100_B8","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":"2023012511545013100_B9","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1126\/science.1136800","article-title":"Clustering by passing messages between data points","volume":"315","author":"Frey","year":"2007","journal-title":"Science"},{"key":"2023012511545013100_B10","first-page":"168","article-title":"Comparison of graph clustering approaches","volume-title":"Proceedings in IIT.SRC","author":"Frivolt","year":"2006"},{"key":"2023012511545013100_B11","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1002\/spe.4380211102","article-title":"Graph drawing by force directed placement","volume":"21","author":"Fruchterman","year":"1991","journal-title":"Softw. Exp. Pract."},{"key":"2023012511545013100_B12","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.abb.2004.07.034","article-title":"Divergent evolution in the enolase superfamily: the interplay of mechanism and specificity","volume":"433","author":"Gerlt","year":"2005","journal-title":"Arch. Biochem. Biophys."},{"key":"2023012511545013100_B13","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.jmb.2006.04.055","article-title":"Evolution of structure and function in the o-succinylbenzoate sythase\/N-acylamino acid racemase family of the enolase superfamily","volume":"360","author":"Glasner","year":"2006","journal-title":"J. Mol. Biol."},{"key":"2023012511545013100_B14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1186\/1471-2105-5-45","article-title":"A hybrid clustering approach to recognition of protein families in 114 microbial genomes","volume":"5","author":"Harlow","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023012511545013100_B15","doi-asserted-by":"crossref","first-page":"12332","DOI":"10.1073\/pnas.0505411102","article-title":"Framework for kernel regularization with application to protein clustering","volume":"10","author":"Lu","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012511545013100_B16","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/S0968-0004(02)02179-5","article-title":"Evolution of protein kinase signaling from yeast to man","volume":"27","author":"Manning","year":"2002","journal-title":"Trends Biochem. Sci."},{"key":"2023012511545013100_B17","doi-asserted-by":"crossref","first-page":"5119","DOI":"10.1111\/j.1742-4658.2005.04947.x","article-title":"Identifying remote protein homologs by network propagation","volume":"272","author":"Noble","year":"2005","journal-title":"FEBS J."},{"key":"2023012511545013100_B18","doi-asserted-by":"crossref","first-page":"1571","DOI":"10.1093\/nar\/gkj515","article-title":"Spectral clustering of protein sequences","volume":"34","author":"Paccanaro","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012511545013100_B19","doi-asserted-by":"crossref","first-page":"2545","DOI":"10.1021\/bi052101l","article-title":"Leveraging enzyme structure-function relationships for functional inference and experimental design: the Structure-Function Linkage Database","volume":"45","author":"Pegg","year":"2006","journal-title":"Biochemistry"},{"key":"2023012511545013100_B20","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1093\/bib\/2.1.19","article-title":"Issues in predicting protein function from sequence","volume":"2","author":"Ponting","year":"2001","journal-title":"Brief. Bioinformatics"},{"key":"2023012511545013100_B21","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1142\/9781860948732_0040","article-title":"Exact and heuristic algorithms for weighted cluster editing","volume":"6","author":"Rahmann","year":"2007","journal-title":"Comput. Syst. Bioinformatics Conf."},{"key":"2023012511545013100_B22","doi-asserted-by":"crossref","first-page":"e1000597","DOI":"10.1371\/journal.pcbi.1000597","article-title":"Biomedical text mining and its applications","volume":"5","author":"Rodriguez-Esteban","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012511545013100_B23","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comp. Sci. Review"},{"key":"2023012511545013100_B24","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1002\/pro.320","article-title":"Comparison of human solute carriers","volume":"19","author":"Schlessinger","year":"2010","journal-title":"Protein Sci."},{"key":"2023012511545013100_B25","doi-asserted-by":"crossref","first-page":"2405","DOI":"10.1128\/JB.183.8.2405-2410.2001","article-title":"Melamine deaminase and atrazine chlorohydrolase: 98 percent identical but functionally different","volume":"183","author":"Seffernick","year":"2001","journal-title":"J. Bacteriol."},{"key":"2023012511545013100_B26","doi-asserted-by":"crossref","first-page":"6383","DOI":"10.1021\/bi047326v","article-title":"Structural and catalytic diversity within the amidohydrolase superfamily","volume":"44","author":"Seibert","year":"2005","journal-title":"Biochemistry"},{"key":"2023012511545013100_B27","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":"2023012511545013100_B28","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":"2023012511545013100_B29","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1186\/1471-2105-8-396","article-title":"Large scale clustering of protein sequences with FORCE - a layout based heuristic for weighted cluster editing","volume":"8","author":"Wittkop","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012511545013100_B30","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1038\/nmeth0610-419","article-title":"Partitioning biological data with transitivity clustering","volume":"7","author":"Wittkop","year":"2010","journal-title":"Nat. Methods"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/3\/326\/48865245\/bioinformatics_27_3_326.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/3\/326\/48865245\/bioinformatics_27_3_326.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:05:50Z","timestamp":1674648350000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/3\/326\/319615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,29]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq655","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,1]]},"published":{"date-parts":[[2010,11,29]]}}}