{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T15:59:04Z","timestamp":1781020744630,"version":"3.54.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2345,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Identifying orthologous genes in multiple genomes is a fundamental task in comparative genomics. Construction of intergenomic symmetrical best matches (SymBets) and joining them into clusters is a popular method of ortholog definition, embodied in several software programs. Despite their wide use, the computational complexity of these programs has not been thoroughly examined.<\/jats:p>\n               <jats:p>Results: In this work, we show that in the standard approach of iteration through all triangles of SymBets, the memory scales with at least the number of these triangles, O(g3) (where g = number of genomes), and construction time scales with the iteration through each pair, i.e. O(g6). We propose the EdgeSearch algorithm that iterates over edges in the SymBet graph rather than triangles of SymBets, and as a result has a worst-case complexity of only O(g3log g). Several optimizations reduce the run-time even further in realistically sparse graphs. In two real-world datasets of genomes from bacteriophages (POGs) and Mollicutes (MOGs), an implementation of the EdgeSearch algorithm runs about an order of magnitude faster than the original algorithm and scales much better with increasing number of genomes, with only minor differences in the final results, and up to 60 times faster than the popular OrthoMCL program with a 90% overlap between the identified groups of orthologs.<\/jats:p>\n               <jats:p>Availability and implementation: C++ source code freely available for download at ftp.ncbi.nih.gov\/pub\/wolf\/COGs\/COGsoft\/<\/jats:p>\n               <jats:p>Contact: \u00a0dmk@stowers.org<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary materials are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq229","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T00:13:31Z","timestamp":1272932011000},"page":"1481-1487","source":"Crossref","is-referenced-by-count":208,"title":["A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches"],"prefix":"10.1093","volume":"26","author":[{"given":"David M.","family":"Kristensen","sequence":"first","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lavanya","family":"Kannan","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael K.","family":"Coleman","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri I.","family":"Wolf","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Sorokin","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eugene V.","family":"Koonin","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arcady","family":"Mushegian","sequence":"additional","affiliation":[{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"},{"name":"1 Department of Binformatics, Stowers Institute for Medical Research, Kansas City, MO 64110, 2 National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894 and 3 Department of Microbiology, Molecular Genetics, and Immunology, University of Kansas Medical Center, Kansas City, KS 66160, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2010,5,2]]},"reference":[{"key":"2023012508040920500_B1","doi-asserted-by":"crossref","first-page":"e9","DOI":"10.1093\/bioinformatics\/btl213","article-title":"Automatic clustering of orthologs and inparalogs shared by multiple proteomes","volume":"22","author":"Alexeyenko","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012508040920500_B2","doi-asserted-by":"crossref","first-page":"e1000262","DOI":"10.1371\/journal.pcbi.1000262","article-title":"Phylogenetic and functional assessment of orthologs inference projects and methods","volume":"5","author":"Altenhoff","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012508040920500_B3","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/S0168-9525(99)01706-0","article-title":"Errors in genome annotation","volume":"15","author":"Brenner","year":"1999","journal-title":"Trends Genet."},{"key":"2023012508040920500_B4","doi-asserted-by":"crossref","first-page":"e383","DOI":"10.1371\/journal.pone.0000383","article-title":"Assessing performance of orthology detection strategies applied to eukaryotic genomes","volume":"2","author":"Chen","year":"2007","journal-title":"PLoS One"},{"key":"2023012508040920500_B5","doi-asserted-by":"crossref","first-page":"2044","DOI":"10.1093\/bioinformatics\/btl286","article-title":"Roundup: a multi-genome repository of orthologs and evolutionary distances","volume":"22","author":"Deluca","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012508040920500_B6","doi-asserted-by":"crossref","first-page":"2596","DOI":"10.1093\/bioinformatics\/bti325","article-title":"Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases","volume":"21","author":"Dufayard","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012508040920500_B7","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":"2023012508040920500_B8","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1016\/j.jctb.2008.02.008","article-title":"Nowhere-zero 3-flows in triangularly connected graphs","volume":"98","author":"Fan","year":"2008","journal-title":"J. Comb. Theory Ser B"},{"key":"2023012508040920500_B9","volume-title":"Inferring Phylogenies.","author":"Felsenstein","year":"2004"},{"key":"2023012508040920500_B10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.2307\/2412448","article-title":"Distinguishing homologous from analogous proteins","volume":"19","author":"Fitch","year":"1970","journal-title":"Syst. Zool."},{"key":"2023012508040920500_B11","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","article-title":"Homology a personal view on some of the problems","volume":"16","author":"Fitch","year":"2000","journal-title":"Trends Genet."},{"key":"2023012508040920500_B12","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1093\/aob\/mcp192","article-title":"Calibrating the Tree of Life: fossils, molecules and evolutionary timescales","volume":"104","author":"Forest","year":"2009","journal-title":"Ann. Bot."},{"key":"2023012508040920500_B13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1142\/9781860948732_0022","article-title":"Clustering of main orthologs for multiple genomes","volume":"6","author":"Fu","year":"2007","journal-title":"Comput. Syst. Bioinformatics Conf."},{"key":"2023012508040920500_B14","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.1089\/cmb.2007.0048","article-title":"MSOAR: a high-throughput ortholog assignment system based on genome rearrangement","volume":"14","author":"Fu","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023012508040920500_B15","doi-asserted-by":"crossref","first-page":"D250","DOI":"10.1093\/nar\/gkm796","article-title":"eggNOG: automated construction and annotation of orthologous groups of genes","volume":"36","author":"Jensen","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012508040920500_B16","doi-asserted-by":"crossref","DOI":"10.1186\/gb-2002-3-2-research0008","article-title":"Selection in the evolution of gene duplications","volume":"3","author":"Kondrashov","year":"2002","journal-title":"Genome Biol."},{"key":"2023012508040920500_B17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1146\/annurev.genet.39.073003.114725","article-title":"Orthologs, paralogs, and evolutionary genomics","volume":"39","author":"Koonin","year":"2005","journal-title":"Annu. Rev. Genet."},{"key":"2023012508040920500_B18","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1007\/s002390010184","article-title":"The closest BLAST hit is often not the nearest neighbor","volume":"52","author":"Koski","year":"2001","journal-title":"J. Mol. Evol."},{"key":"2023012508040920500_B19","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.tim.2009.11.003","article-title":"New dimensions of the virus world discovered through metagenomics","volume":"18","author":"Kristensen","year":"2009","journal-title":"Trends Microbiol."},{"key":"2023012508040920500_B20","doi-asserted-by":"crossref","first-page":"2178","DOI":"10.1101\/gr.1224503","article-title":"OrthoMCL: identification of ortholog groups for eukaryotic genomes","volume":"13","author":"Li","year":"2003","journal-title":"Genome Res."},{"key":"2023012508040920500_B21","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.virusres.2006.01.015","article-title":"Protein repertoire of double-stranded DNA bacteriophages","volume":"117","author":"Liu","year":"2006","journal-title":"Virus Res."},{"key":"2023012508040920500_B22","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.1126\/science.290.5494.1151","article-title":"The evolutionary fate and consequences of duplicate genes","volume":"290","author":"Lynch","year":"2000","journal-title":"Science"},{"key":"2023012508040920500_B23","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1093\/genetics\/154.1.459","article-title":"The probability of duplicate gene preservation by subfunctionalization","volume":"154","author":"Lynch","year":"2000","journal-title":"Genetics"},{"key":"2023012508040920500_B24","doi-asserted-by":"crossref","first-page":"D476","DOI":"10.1093\/nar\/gki107","article-title":"Inparanoid: a comprehensive database of eukaryotic orthologs","volume":"33","author":"O'Brien","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012508040920500_B25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-86659-3","volume-title":"Evolution by Gene Duplication.","author":"Ohno","year":"1970"},{"key":"2023012508040920500_B26","doi-asserted-by":"crossref","first-page":"12950","DOI":"10.1073\/pnas.0804392105","article-title":"Differential loss of embryonic globin genes during the radiation of placental mammals","volume":"105","author":"Opazo","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508040920500_B27","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1099\/00207713-46-4-885","article-title":"Comparative metabolism of Mesoplasma, Entomoplasma, Mycoplasma, and Acholeplasma","volume":"46","author":"Pollack","year":"1996","journal-title":"Int. J. Syst. Bacteriol."},{"key":"2023012508040920500_B28","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1006\/jmbi.2000.5197","article-title":"Automatic clustering of orthologs and in-paralogs from pairwise species comparisons","volume":"314","author":"Remm","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023012508040920500_B29","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/S0022-2836(02)00016-5","article-title":"Enzyme function less conserved than anticipated","volume":"318","author":"Rost","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023012508040920500_B30","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1186\/1471-2105-9-518","article-title":"Algorithm of OMA for large-scale orthology inference","volume":"9","author":"Roth","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012508040920500_B31","doi-asserted-by":"crossref","first-page":"D5","DOI":"10.1093\/nar\/gkp967","article-title":"Database resources of the National Center for Biotechnology Information","volume":"38","author":"Sayers","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012508040920500_B32","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1093\/bioinformatics\/18.1.92","article-title":"Automated ortholog inference from phylogenetic trees and calculation of orthology reliability","volume":"18","author":"Storm","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012508040920500_B33","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023012508040920500_B34","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1093\/nar\/28.1.33","article-title":"The COG database: a tool for genome-scale analysis of protein functions and evolution","volume":"28","author":"Tatusov","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023012508040920500_B35","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1006\/jmbi.2001.4513","article-title":"Evolution of function in protein superfamilies, from a structural perspective","volume":"307","author":"Todd","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023012508040920500_B36","article-title":"Graph clustering by flow simulation","volume-title":"PhD Thesis","author":"Van Dongen","year":"2000"},{"key":"2023012508040920500_B37","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/TCBB.2007.1004","article-title":"Ortholog clustering on a multipartite graph","volume":"4","author":"Vashist","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012508040920500_B38","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1101\/gr.073585.107","article-title":"EnsemblCompara GeneTrees: complete, duplication-aware phylogenetic trees in vertebrates","volume":"19","author":"Vilella","year":"2009","journal-title":"Genome Res."},{"key":"2023012508040920500_B39","doi-asserted-by":"crossref","first-page":"i549","DOI":"10.1093\/bioinformatics\/btm193","article-title":"Automatic genome-wide reconstruction of phylogenetic gene trees","volume":"23","author":"Wapinski","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012508040920500_B40","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/j.sbi.2005.04.003","article-title":"Predicting protein function from sequence and structural data","volume":"15","author":"Watson","year":"2005","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012508040920500_B41","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1186\/1471-2105-3-14","article-title":"RIO: analyzing proteomes by automated phylogenomics using resampled inference of orthologs","volume":"3","author":"Zmasek","year":"2002","journal-title":"BMC Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/1481\/48858473\/bioinformatics_26_12_1481.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/1481\/48858473\/bioinformatics_26_12_1481.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:08:00Z","timestamp":1674634080000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/1481\/287219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,2]]},"references-count":41,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq229","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,5,2]]}}}