{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:40:57Z","timestamp":1781854857067,"version":"3.54.5"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Detecting groups of functionally related proteins from their amino acid sequence alone has been a long-standing challenge in computational genome research. Several clustering approaches, following different strategies, have been published to attack this problem. Today, new sequencing technologies provide huge amounts of sequence data that has to be efficiently clustered with constant or increased accuracy, at increased speed.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We advocate that the model of <jats:italic>weighted cluster editing<\/jats:italic>, also known as <jats:italic>transitive graph projection<\/jats:italic> is well-suited to protein clustering. We present the FORCE heuristic that is based on transitive graph projection and clusters arbitrary sets of objects, given pairwise similarity measures. In particular, we apply FORCE to the problem of protein clustering and show that it outperforms the most popular existing clustering tools (Spectral clustering, TribeMCL, GeneRAGE, Hierarchical clustering, and Affinity Propagation). Furthermore, we show that FORCE is able to handle huge datasets by calculating clusters for all 192 187 prokaryotic protein sequences (66 organisms) obtained from the COG database. Finally, FORCE is integrated into the corynebacterial reference database CoryneRegNet.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>FORCE is an applicable alternative to existing clustering algorithms. Its theoretical foundation, weighted cluster editing, can outperform other clustering paradigms on protein homology clustering. FORCE is open source and implemented in Java. The software, including the source code, the clustering results for COG and CoryneRegNet, and all evaluation datasets are available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/gi.cebitec.uni-bielefeld.de\/comet\/force\/\" ext-link-type=\"uri\">http:\/\/gi.cebitec.uni-bielefeld.de\/comet\/force\/<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-8-396","type":"journal-article","created":{"date-parts":[[2007,10,17]],"date-time":"2007-10-17T18:13:47Z","timestamp":1192644827000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":54,"title":["Large scale clustering of protein sequences with FORCE -A layout based heuristic for weighted cluster editing"],"prefix":"10.1186","volume":"8","author":[{"given":"Tobias","family":"Wittkop","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Baumbach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francisco P","family":"Lobo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Rahmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,17]]},"reference":[{"issue":"17","key":"1768_CR1","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"SF Altschul","year":"1997","unstructured":"Altschul SF, Madden TL, Sch\u00e4ffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. 1997, 25 (17): 3389-3402.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"1768_CR2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1142\/9781860948732_0040","volume":"6","author":"S Rahmann","year":"2007","unstructured":"Rahmann S, Wittkop T, Baumbach J, Martin M, Tru\u00df A, B\u00f6cker S: Exact and Heuristic Algorithms for Weighted Cluster Editing. Comput Syst Bioinformatics Conf. 2007, 6 (1): 391-401.","journal-title":"Comput Syst Bioinformatics Conf"},{"issue":"9","key":"1768_CR3","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s00236-004-0144-0","volume":"40","author":"S Delvaux","year":"2004","unstructured":"Delvaux S, Horsten L: On best transitive approximations of simple graphs. Acta informatica. 2004, 40 (9): 637-655.","journal-title":"Acta informatica"},{"key":"1768_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir R, Sharan R, Tsur D: Cluster graph modification problems. Discrete Applied Mathematics. 2004, 144: 173-182.","journal-title":"Discrete Applied Mathematics"},{"issue":"Suppl 2","key":"1768_CR5","doi-asserted-by":"publisher","first-page":"S182","DOI":"10.1093\/bioinformatics\/18.suppl_2.S182","volume":"18","author":"P Pipenbacher","year":"2002","unstructured":"Pipenbacher P, Schliep A, Schneckener S, Schoenhuth A, Schomburg D, Schrader R: ProClust: improved clustering of protein sequences with an extended graph-based approach. Bioinformatics. 2002, 18 (Suppl 2): S182-S191.","journal-title":"Bioinformatics"},{"key":"1768_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/1471-2105-6-15","volume":"6","author":"A Krause","year":"2005","unstructured":"Krause A, Stoye J, Vingron M: Large scale hierarchical clustering of protein sequences. BMC Bioinformatics. 2005, 6: 15-","journal-title":"BMC Bioinformatics"},{"issue":"5","key":"1768_CR7","doi-asserted-by":"publisher","first-page":"1571","DOI":"10.1093\/nar\/gkj515","volume":"34","author":"A Paccanaro","year":"2006","unstructured":"Paccanaro A, Casbon JA, Saqi MA: Spectral clustering of protein sequences. Nucleic Acids Research. 2006, 34 (5): 1571-1580.","journal-title":"Nucleic Acids Research"},{"issue":"7","key":"1768_CR8","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1093\/nar\/30.7.1575","volume":"30","author":"AJ Enright","year":"2002","unstructured":"Enright AJ, Dongen SV, Ouzounis CA: An efficient algorithm for large-scale detection of protein families. Nucleic Acids Res. 2002, 30 (7): 1575-1584.","journal-title":"Nucleic Acids Res"},{"key":"1768_CR9","volume-title":"Cluster Analysis","author":"BS Everitt","year":"1993","unstructured":"Everitt BS: Cluster Analysis. 1993, Edward Arnold, London, 3","edition":"3"},{"issue":"5","key":"1768_CR10","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1093\/bioinformatics\/16.5.451","volume":"16","author":"AJ Enright","year":"2000","unstructured":"Enright AJ, Ouzounis CA: GeneRAGE: a robust algorithm for sequence clustering and domain detection. Bioinformatics. 2000, 16 (5): 451-457.","journal-title":"Bioinformatics"},{"issue":"5814","key":"1768_CR11","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1126\/science.1136800","volume":"315","author":"BJ Frey","year":"2007","unstructured":"Frey BJ, Dueck D: Clustering by Passing Messages Between Data Points. Science. 2007, 315 (5814): 972-976.","journal-title":"Science"},{"key":"1768_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1186\/1471-2105-4-41","volume":"4","author":"RL Tatusov","year":"2003","unstructured":"Tatusov RL, Fedorova ND, Jackson JD, Jacobs AR, Kiryutin B, Koonin EV, Krylov DM, Mazumder R, Mekhedov SL, Nikolskaya AN, Rao BS, Smirnov S, Sverdlov AV, Vasudevan S, Wolf YI, Yin JJ, Natale DA: The COG database: an updated version includes eukaryotes. BMC Bioinformatics. 2003, 4: 41-","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"1768_CR13","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1002\/spe.4380211102","volume":"21","author":"TMJ Fruchterman","year":"1991","unstructured":"Fruchterman TMJ, Reingold EM: Graph drawing by force-directed placement. Software \u2013 Practice and Experience. 1991, 21 (11): 1129-1164.","journal-title":"Software \u2013 Practice and Experience"},{"issue":"17","key":"1768_CR14","doi-asserted-by":"publisher","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","volume":"20","author":"AD King","year":"2004","unstructured":"King AD, Przulj N, Jurisica I: Protein complex prediction via cost-based clustering. Bioinformatics. 2004, 20 (17): 3013-3020.","journal-title":"Bioinformatics"},{"key":"1768_CR15","doi-asserted-by":"publisher","first-page":"D226","DOI":"10.1093\/nar\/gkh039","volume":"32","author":"A Andreeva","year":"2004","unstructured":"Andreeva A, Howorth D, Brenner SE, Hubbard TJ, Chothia C, Murzin AG: SCOP database in 2004: refinements integrate structure and sequence family data. Nucleic Acids Research. 2004, 32: D226-D229.","journal-title":"Nucleic Acids Research"},{"key":"1768_CR16","doi-asserted-by":"publisher","first-page":"D189","DOI":"10.1093\/nar\/gkh034","volume":"32","author":"JM Chandonia","year":"2004","unstructured":"Chandonia JM, Hon G, Walker NS, Conte LL, Koehl P, Levitt M, Brenner SE: The ASTRAL Compendium in 2004. Nucleic Acids research. 2004, 32: D189-D192.","journal-title":"Nucleic Acids research"},{"key":"1768_CR17","unstructured":"SCOP website. [http:\/\/scop.mrc-lmb.cam.ac.uk\/scop\/]"},{"key":"1768_CR18","unstructured":"ASTRAL website. [http:\/\/astral.berkeley.edu\/]"},{"key":"1768_CR19","unstructured":"COG website. [http:\/\/www.ncbi.nlm.nih.gov\/COG\/]"},{"key":"1768_CR20","unstructured":"COG sequences (FTP). [ftp:\/\/ftp.ncbi.nih.gov\/pub\/COG\/COG\/myva]"},{"key":"1768_CR21","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1186\/1471-2164-7-24","volume":"7","author":"J Baumbach","year":"2006","unstructured":"Baumbach J, Brinkrolf K, Czaja L, Rahmann S, Tauch A: CoryneRegNet: An ontology-based data warehouse of corynebacterial transcription factors and regulatory networks. BMC Genomics. 2006, 7: 24-","journal-title":"BMC Genomics"},{"issue":"2","key":"1768_CR22","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jbiotec.2006.12.012","volume":"129","author":"J Baumbach","year":"2007","unstructured":"Baumbach J, Wittkop T, Rademacher K, Rahmann S, Brinkrolf K, Tauch A: CoryneRegNet 3.0-An interactive systems biology platform for the analysis of gene regulatory networks in corynebacteria and Escherichia coli. J Biotechnol. 2007, 129 (2): 279-289.","journal-title":"J Biotechnol"},{"issue":"4","key":"1768_CR23","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00453-004-1090-5","volume":"39","author":"J Gramm","year":"2004","unstructured":"Gramm J, Guo J, H\u00fcffner F, Niedermeier R: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica. 2004, 39 (4): 321-347.","journal-title":"Algorithmica"},{"issue":"4","key":"1768_CR24","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm J, Guo J, H\u00fcffner F, Niedermeier R: Graph-modeled data clustering: Exact algorithm for clique generation. Theor Comput Syst. 2005, 38 (4): 373-392.","journal-title":"Theor Comput Syst"},{"key":"1768_CR25","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11847250_2","volume-title":"Proc of International Workshop on Parameterized and Exact Computation (IWPEC 2006)","author":"F Dehne","year":"2006","unstructured":"Dehne F, Langston MA, Luo X, Pitre S, Shaw P, Zhang Y: The Cluster Editing Problem: Implementations and Experiments. Proc of International Workshop on Parameterized and Exact Computation (IWPEC 2006). 2006, LNCS, Springer, 4169: 13-24."},{"key":"1768_CR26","unstructured":"CoryneRegNet website. [http:\/\/www.CoryneRegNet.DE]"},{"key":"1768_CR27","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1186\/1471-2105-7-389","volume":"7","author":"M Beckstette","year":"2006","unstructured":"Beckstette M, Homann R, Giegerich R, Kurtz S: Fast index based algorithms and software for matching position specific scoring matrices. BMC Bioinformatics. 2006, 7: 389-","journal-title":"BMC Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-396.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:50:42Z","timestamp":1630461042000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,17]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1768"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-396","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,17]]},"assertion":[{"value":"1 August 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"396"}}