The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss
Open accessAbstract
Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction. Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods. Availability: Our programs can be freely downloaded from http://compbio.mit.edu/ranger-dtl/. Contact: mukul@csail.mit.edu; manoli@mit.edu Supplementary information: Supplementary data 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
Orthologs, Paralogs, and Evolutionary Genomics
Koonin, E. V. (2005) · Annual Review of Genetics · doi:10.1146/annurev.genet.39.073003.114725 · Cited by 1,323
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
Natural history and evolutionary principles of gene duplication in fungi
Wapinski, I., Pfeffer, A., Friedman, N., & Regev, A. (2007) · Nature · doi:10.1038/nature06107 · Cited by 614
Biased gene transfer in microbial evolution
Andam, C. P., & Gogarten, J. P. (2011) · Nature Reviews Microbiology · doi:10.1038/nrmicro2593 · Cited by 172
Cited by
Inferring Horizontal Gene Transfer
Ravenhall, M., Škunca, N., Lassalle, F., & Dessimoz, C. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004095 · Cited by 296
Genomes in turmoil: quantification of genome dynamics in prokaryote supergenomes
Puigbò, P., Lobkovsky, A. E., Kristensen, D. M., Wolf, Y. I., & Koonin, E. V. (2014) · BMC Biology · doi:10.1186/s12915-014-0066-4 · Cited by 232
Wu, Y.-C., Rasmussen, M. D., Bansal, M. S., & Kellis, M. (2014) · Genome Research · doi:10.1101/gr.161968.113 · Cited by 77
Self-citation
Metadata
- Authors
- Bansal, M. S., Alm, E. J., & Kellis, M.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2012-06-09
- Volume
- 28
- Issue
- 12
- Pages
- i283-i291
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2132318428
- Cited by
- 218
- References
- 4
- FWCI
- 6.39
- 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: Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. https://app.cochat.ai/papers/10.1093/bioinformatics/bts225
- The paper
- Bansal, M. S., Alm, E. J., & Kellis, M. (2012). Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics. https://doi.org/10.1093/bioinformatics/bts225
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.