A Low-polynomial Algorithm for Assembling Clusters of Orthologous Groups from Intergenomic Symmetric Best Matches

Overview

Journal Bioinformatics

Publisher Oxford University Press

Specialty Biology

Date 2010 May 5

PMID 20439257

Citations 137

Authors

David M Kristensen

Lavanya Kannan

Michael K Coleman

Yuri I Wolf

Alexander Sorokin

Eugene V Koonin

Arcady Mushegian

Affiliations

Soon will be listed here.

Abstract

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.

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(g(3)) (where g = number of genomes), and construction time scales with the iteration through each pair, i.e. O(g(6)). 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(g(3)log 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.

Availability And Implementation: C++ source code freely available for download at ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/.

Supplementary Information: Supplementary materials are available at Bioinformatics online.

Citing Articles

Microbial Rumen proteome analysis suggests Firmicutes and Bacteroidetes as key producers of lignocellulolytic enzymes and carbohydrate-binding modules.

da Silva Pereira M, Alcantara L, Martins de Freitas L, de Oliveira Ferreira A, Lopes Leal P Braz J Microbiol. 2025; .

PMID: 39932663 DOI: 10.1007/s42770-025-01627-8.

A sweeping view of avian mycoplasmas biology drawn from comparative genomic analyses.

Yacoub E, Baby V, Sirand-Pugnet P, Arfi Y, Mardassi H, Blanchard A BMC Genomics. 2025; 26(1):24.

PMID: 39789465 PMC: 11720521. DOI: 10.1186/s12864-024-11201-5.

Pangenome-Wide Association Study in the Family Reveals Key Evolutionary Aspects of Their Relationship with Their Hosts.

Salgado-Morales R, Barba-Xochipa K, Martinez-Ocampo F, Dantan-Gonzalez E, Hernandez-Mendoza A, Quiterio-Trenado M Int J Mol Sci. 2024; 25(23).

PMID: 39684382 PMC: 11641800. DOI: 10.3390/ijms252312671.

Description of two novel species isolated from human nasal passages and skin.

Popowitch E, Tran T, Escapa I, Bhatt E, Sozat A, Ahmed N bioRxiv. 2024; .

PMID: 39605597 PMC: 11601546. DOI: 10.1101/2024.11.21.624533.

Metabolic capabilities are highly conserved among human nasal-associated species in pangenomic analyses.

Tran T, F Escapa I, Roberts A, Gao W, Obawemimo A, Segre J mSystems. 2024; 9(12):e0113224.

PMID: 39508593 PMC: 11651106. DOI: 10.1128/msystems.01132-24.

References

Remm M, Storm C, Sonnhammer E . Automatic clustering of orthologs and in-paralogs from pairwise species comparisons. J Mol Biol. 2001; 314(5):1041-52. DOI: 10.1006/jmbi.2000.5197. View

Koonin E . Orthologs, paralogs, and evolutionary genomics. Annu Rev Genet. 2005; 39:309-38. DOI: 10.1146/annurev.genet.39.073003.114725. View

Forest F . Calibrating the Tree of Life: fossils, molecules and evolutionary timescales. Ann Bot. 2009; 104(5):789-94. PMC: 2749537. DOI: 10.1093/aob/mcp192. View

Jensen L, Julien P, Kuhn M, von Mering C, Muller J, Doerks T . eggNOG: automated construction and annotation of orthologous groups of genes. Nucleic Acids Res. 2007; 36(Database issue):D250-4. PMC: 2238944. DOI: 10.1093/nar/gkm796. View

Vilella A, Severin J, Ureta-Vidal A, Heng L, Durbin R, Birney E . EnsemblCompara GeneTrees: Complete, duplication-aware phylogenetic trees in vertebrates. Genome Res. 2008; 19(2):327-35. PMC: 2652215. DOI: 10.1101/gr.073585.107. View

Brenner S . Errors in genome annotation. Trends Genet. 1999; 15(4):132-3. DOI: 10.1016/s0168-9525(99)01706-0. View

Todd A, Orengo C, Thornton J . Evolution of function in protein superfamilies, from a structural perspective. J Mol Biol. 2001; 307(4):1113-43. DOI: 10.1006/jmbi.2001.4513. View

Fu Z, Chen X, Vacic V, Nan P, Zhong Y, Jiang T . MSOAR: a high-throughput ortholog assignment system based on genome rearrangement. J Comput Biol. 2007; 14(9):1160-75. DOI: 10.1089/cmb.2007.0048. View

Kristensen D, Mushegian A, Dolja V, Koonin E . New dimensions of the virus world discovered through metagenomics. Trends Microbiol. 2009; 18(1):11-9. PMC: 3293453. DOI: 10.1016/j.tim.2009.11.003. View

10.

Liu J, Glazko G, Mushegian A . Protein repertoire of double-stranded DNA bacteriophages. Virus Res. 2006; 117(1):68-80. DOI: 10.1016/j.virusres.2006.01.015. View

11.

OBrien K, Remm M, Sonnhammer E . Inparanoid: a comprehensive database of eukaryotic orthologs. Nucleic Acids Res. 2004; 33(Database issue):D476-80. PMC: 540061. DOI: 10.1093/nar/gki107. View

12.

Pollack J, Williams M, BANZON J, Jones M, Harvey L, Tully J . Comparative metabolism of Mesoplasma, Entomoplasma, Mycoplasma, and Acholeplasma. Int J Syst Bacteriol. 1996; 46(4):885-90. DOI: 10.1099/00207713-46-4-885. View

13.

Enright A, Van Dongen S, Ouzounis C . An efficient algorithm for large-scale detection of protein families. Nucleic Acids Res. 2002; 30(7):1575-84. PMC: 101833. DOI: 10.1093/nar/30.7.1575. View

14.

Dufayard J, Duret L, Penel S, Gouy M, Rechenmann F, Perriere G . Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases. Bioinformatics. 2005; 21(11):2596-603. DOI: 10.1093/bioinformatics/bti325. View

15.

Storm C, Sonnhammer E . Automated ortholog inference from phylogenetic trees and calculation of orthology reliability. Bioinformatics. 2002; 18(1):92-9. DOI: 10.1093/bioinformatics/18.1.92. View

16.

Zmasek C, Eddy S . RIO: analyzing proteomes by automated phylogenomics using resampled inference of orthologs. BMC Bioinformatics. 2002; 3:14. PMC: 116988. DOI: 10.1186/1471-2105-3-14. View

17.

Altenhoff A, Dessimoz C . Phylogenetic and functional assessment of orthologs inference projects and methods. PLoS Comput Biol. 2009; 5(1):e1000262. PMC: 2612752. DOI: 10.1371/journal.pcbi.1000262. View

18.

Wapinski I, Pfeffer A, Friedman N, Regev A . Automatic genome-wide reconstruction of phylogenetic gene trees. Bioinformatics. 2007; 23(13):i549-58. DOI: 10.1093/bioinformatics/btm193. View

19.

Koski L, Golding G . The closest BLAST hit is often not the nearest neighbor. J Mol Evol. 2001; 52(6):540-2. DOI: 10.1007/s002390010184. View

20.

Chen F, Mackey A, Vermunt J, Roos D . Assessing performance of orthology detection strategies applied to eukaryotic genomes. PLoS One. 2007; 2(4):e383. PMC: 1849888. DOI: 10.1371/journal.pone.0000383. View