The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches
Open accessAbstract
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(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. Availability and implementation: C++ source code freely available for download at ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/ Contact: dmk@stowers.org Supplementary information: Supplementary materials are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes
Li, L., Stoeckert, C. J., & Roos, D. S. (2003) · Genome Research · doi:10.1101/gr.1224503 · Cited by 5,707
The Evolutionary Fate and Consequences of Duplicate Genes
Lynch, M., & Conery, J. S. (2000) · Science · doi:10.1126/science.290.5494.1151 · Cited by 4,988
EnsemblCompara GeneTrees: Complete, duplication-aware phylogenetic trees in vertebrates
Vilella, A. J., Severin, J., Ureta-Vidal, A., Heng, L., Durbin, R., & Birney, E. (2009) · Genome Research · doi:10.1101/gr.073585.107 · Cited by 1,238
eggNOG: automated construction and annotation of orthologous groups of genes
Jensen, L. J., Julien, P., Kuhn, M., von Mering, C., Muller, J., Doerks, T., & Bork, P. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm796 · Cited by 547
Cited by
Complex archaea that bridge the gap between prokaryotes and eukaryotes
Spang, A., Saw, J. H., Jørgensen, S. L., Zaremba-Niedzwiedzka, K., Martijn, J., Lind, A. E., van Eijk, R., Schleper, C., Guy, L., & Ettema, T. J. G. (2015) · Nature · doi:10.1038/nature14447 · Cited by 1,324
Producing polished prokaryotic pangenomes with the Panaroo pipeline
Tonkin-Hill, G., MacAlasdair, N., Ruis, C., Weimann, A., Horesh, G., Lees, J. A., Gladstone, R. A., Lo, S., Beaudoin, C., Floto, R. A., et al. (2020) · Genome Biology · doi:10.1186/s13059-020-02090-4 · Cited by 1,320
Proteinortho: Detection of (Co-)orthologs in large-scale analysis
Lechner, M., Findeiß, S., Steiner, L., Marz, M., Stadler, P. F., & Prohaska, S. J. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-124 · Cited by 1,221
COG database update: focus on microbial diversity, model organisms, and widespread pathogens
Galperin, M. Y., Wolf, Y. I., Makarova, K. S., Vera Alvarez, R., Landsman, D., & Koonin, E. V. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkaa1018 · Cited by 932
Self-citationGET_HOMOLOGUES, a Versatile Software Package for Scalable and Robust Microbial Pangenome Analysis
Contreras-Moreira, B., & Vinuesa, P. (2013) · Applied and Environmental Microbiology · doi:10.1128/aem.02411-13 · Cited by 905
Metadata
- Authors
- Kristensen, D. M., Kannan, L., Coleman, M. K., Wolf, Y. I., Sorokin, A., Koonin, E. V., & Mushegian, A.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2010-05-02
- Volume
- 26
- Issue
- 12
- Pages
- 1481-1487
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2144377764
- Cited by
- 222
- References
- 4
- FWCI
- 2.13
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches. https://app.cochat.ai/papers/10.1093/bioinformatics/btq229
- The paper
- Kristensen, D. M., Kannan, L., Coleman, M. K., Wolf, Y. I., Sorokin, A., Koonin, E. V., & Mushegian, A. (2010). A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches. Bioinformatics. https://doi.org/10.1093/bioinformatics/btq229
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.