The DOI matches its Crossref record; 62 of the 62 references it cites were found in a registry or an index.
Fast Dating Using Least-Squares Criteria and Algorithms
Open accessAbstract
Phylogenies provide a useful way to understand the evolutionary history of genetic samples, and data sets with more than a thousand taxa are becoming increasingly common, notably with viruses (e.g., human immunodeficiency virus (HIV)). Dating ancestral events is one of the first, essential goals with such data. However, current sophisticated probabilistic approaches struggle to handle data sets of this size. Here, we present very fast dating algorithms, based on a Gaussian model closely related to the Langley-Fitch molecular-clock model. We show that this model is robust to uncorrelated violations of the molecular clock. Our algorithms apply to serial data, where the tips of the tree have been sampled through times. They estimate the substitution rate and the dates of all ancestral nodes. When the input tree is unrooted, they can provide an estimate for the root position, thus representing a new, practical alternative to the standard rooting methods (e.g., midpoint). Our algorithms exploit the tree (recursive) structure of the problem at hand, and the close relationships between least-squares and linear algebra. We distinguish between an unconstrained setting and the case where the temporal precedence constraint (i.e., an ancestral node must be older that its daughter nodes) is accounted for. With rooted trees, the former is solved using linear algebra in linear computing time (i.e., proportional to the number of taxa), while the resolution of the latter, constrained setting, is based on an active-set method that runs in nearly linear time. With unrooted trees the computing time becomes (nearly) quadratic (i.e., proportional to the square of the number of taxa). In all cases, very large input trees (>10,000 taxa) can easily be processed and transformed into time-scaled trees. We compare these algorithms to standard methods (root-to-tip, r8s version of Langley-Fitch method, and BEAST). Using simulated data, we show that their estimation accuracy is similar to that of the most sophisticated methods, while their computing time is much faster. We apply these algorithms on a large data set comprising 1194 strains of Influenza virus from the pdm09 H1N1 Human pandemic. Again the results show that these algorithms provide a very fast alternative with results similar to those of other computer programs. These algorithms are implemented in the LSD software (least-squares dating), which can be downloaded from http://www.atgc-montpellier.fr/LSD/, along with all our data sets and detailed results. An Online Appendix, providing additional algorithm descriptions, tables, and figures can be found in the Supplementary Material available on Dryad at http://dx.doi.org/10.5061/dryad.968t3.
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
The neighbor-joining method: a new method for reconstructing phylogenetic trees.
(1987) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040454 · Cited by 59,715
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Guindon, S., Dufayard, J.-F., Lefort, V., Anisimova, M., Hordijk, W., & Gascuel, O. (2010) · Systematic Biology · doi:10.1093/sysbio/syq010 · Cited by 18,376
Self-citationPHYLIP-Phylogeny inference package (Version 3.2)
Felsenstein, J. (1989) · Cladistics · Cited by 17,682
A Simple, Fast, and Accurate Algorithm to Estimate Large Phylogenies by Maximum Likelihood
Guindon, S., & Gascuel, O. (2003) · Systematic Biology · doi:10.1080/10635150390235520 · Cited by 16,806
Self-citation(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
BEAST: Bayesian evolutionary analysis by sampling trees
Drummond, A. J., & Rambaut, A. (2007) · BMC Evolutionary Biology · doi:10.1186/1471-2148-7-214 · Cited by 12,919
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Bayesian Phylogenetics with BEAUti and the BEAST 1.7
Drummond, A. J., Suchard, M. A., Xie, D., & Rambaut, A. (2012) · Molecular Biology and Evolution · doi:10.1093/molbev/mss075 · Cited by 10,063
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-40065-5 · Cited by 9,008
Relaxed Phylogenetics and Dating with Confidence
Drummond, A. J., Ho, S. Y. W., Phillips, M. J., & Rambaut, A. (2006) · PLoS Biology · doi:10.1371/journal.pbio.0040088 · Cited by 6,463 · cited 6×
“To simulate trees with relaxed molecular clock (RMC), we used the uncorrelated lognormal model, which is one of the most widely used in BEAST (Drummond et al. 2006).”
BackgroundMethodInfluentialA Statistical Method for Evaluating Systematic Relationships
Sokal, R. R., & Michener, C. D. (1958) · Biodiversity Heritage Library (Smithsonian Institution) · doi:10.5281/zenodo.16435756 · Cited by 4,416
Fitch, W. M., & Margoliash, E. (1967) · Science · doi:10.1126/science.155.3760.279 · Cited by 3,610
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Sanderson, M. J. (2002) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a003974 · Cited by 1,977 · cited 1×
“…to cope with more complex, correlated molecular clock models, typically combining the least-squares framework with penalized criteria, similar to Sanderson (2002), or using some of our algorithmic solutions to deal with multi-normal approximations of the likelihood function (Thorne et al. 1998).”
MethodSanderson, M. J. (2003) · Bioinformatics · doi:10.1093/bioinformatics/19.2.301 · Cited by 1,906
BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data
Gascuel, O. (1997) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a025808 · Cited by 1,836
Self-citationFastME 2.0: A Comprehensive, Accurate, and Fast Distance-Based Phylogeny Inference Program: Table 1.
Lefort, V., Desper, R., & Gascuel, O. (2015) · Molecular Biology and Evolution · doi:10.1093/molbev/msv150 · Cited by 1,777
Self-citationParlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
Rambaut, A., & Grass, N. C. (1997) · Bioinformatics · doi:10.1093/bioinformatics/13.3.235 · Cited by 1,574
Evaluation of methods for detecting recombination from DNA sequences: Computer simulations
Posada, D., & Crandall, K. A. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.241370698 · Cited by 1,502
Unifying the Epidemiological and Evolutionary Dynamics of Pathogens
Grenfell, B. T., Pybus, O. G., Gog, J. R., Wood, J. L. N., Daly, J. M., Mumford, J. A., & Holmes, E. C. (2004) · Science · doi:10.1126/science.1090727 · Cited by 1,385
Estimating the rate of evolution of the rate of molecular evolution
Thorne, J. L., Kishino, H., & Painter, I. S. (1998) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a025892 · Cited by 1,317
A nonparametric approach to estimating divergence times in the absence of rate constancy.
Sanderson, M. J. (1997) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a025731 · Cited by 1,156
Introduction to Quadratic Forms
O’Meara, O. T. (1973) · Springer eBooks · doi:10.1007/978-3-662-41922-9 · Cited by 1,110
Linear complementarity, linear and nonlinear programming
(1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90500-6 · Cited by 978
Divergence time and evolutionary rate estimation with multilocus data.
Thorne, J. L., & Kishino, H. (2002) · Systematic Biology · doi:10.1080/10635150290102456 · Cited by 962
A Total-Evidence Approach to Dating with Fossils, Applied to the Early Radiation of the Hymenoptera
Ronquist, F., Klopfstein, S., Vilhelmsen, L., Schulmeister, S., Murray, D. L., & Rasnitsyn, A. P. (2012) · Systematic Biology · doi:10.1093/sysbio/sys058 · Cited by 930 · cited 2×
“Moreover, close relationships exist between the calibration-points and dated-tips approaches (Ronquist et al. 2012).”
BackgroundShankarappa, R., Margolick, J. B., Gange, S. J., Rodrigo, A. G., Upchurch, D., Farzadegan, H., Gupta, P., Rinaldo, C. R., Learn, G. H., He, X., et al. (1999) · Journal of Virology · doi:10.1128/jvi.73.12.10489-10502.1999 · Cited by 926
treePL: divergence time estimation using penalized likelihood for large phylogenies
Smith, S. A., & O’Meara, B. C. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts492 · Cited by 845
Ayres, D. L., Darling, A., Zwickl, D. J., Beerli, P., Holder, M. T., Lewis, P. O., Huelsenbeck, J. P., Ronquist, F., Swofford, D. L., Cummings, M. P., et al. (2012) · Systematic Biology · doi:10.1093/sysbio/syr100 · Cited by 706
Estimating divergence times in large molecular phylogenies
Tamura, K., Battistuzzi, F. U., Billing-Ross, P., Murillo, O., Filipski, A., & Kumar, S. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1213199109 · Cited by 676
Hedges, S. B., & Kumar, S. (2009) · Cited by 628
Global Distribution and Conservation of Evolutionary Distinctness in Birds
Jetz, W., Thomas, G. H., Joy, J. B., Redding, D. W., Hartmann, K., & Mooers, A. O. (2014) · Current Biology · doi:10.1016/j.cub.2014.03.011 · Cited by 625
A general comparison of relaxed molecular clock models
Lepage, T., Bryant, D., Philippe, H., & Lartillot, N. (2007) · Molecular Biology and Evolution · doi:10.1093/molbev/msm193 · Cited by 546 · cited 2×
“In all cases, very large input trees (>10,000 taxa) can easily be processed and transformed into time-scaled trees.”
Sampling-through-time in birth–death trees
Stadler, T. (2010) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2010.09.010 · Cited by 539
Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle
Desper, R., & Gascuel, O. (2002) · Journal of Computational Biology · doi:10.1089/106652702761034136 · Cited by 488
Self-citationAn examination of the constancy of the rate of molecular evolution
Langley, C. H., & Fitch, W. M. (1974) · Journal of Molecular Evolution · doi:10.1007/bf01797451 · Cited by 478
Inferring speciation times under an episodic molecular clock
Rannala, B., & Yang, Z. (2007) · Systematic Biology · doi:10.1080/10635150701420643 · Cited by 475 · cited 6×
“Such use of BEAST seems to be rather uncommon, but corresponds to the way a number of other dating programs proceed, for example, PAML (Rannala and Yang 2007).”
BackgroundInfluentialRambaut, A. (2000) · Bioinformatics · doi:10.1093/bioinformatics/16.4.395 · Cited by 418
Measurably evolving populations
Drummond, A. J., Pybus, O. G., Rambaut, A., Forsberg, R., & Rodrigo, A. G. (2003) · Trends in Ecology & Evolution · doi:10.1016/s0169-5347(03)00216-7 · Cited by 418
Volz, E. M., Koelle, K., & Bedford, T. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002947 · Cited by 417
Estimating Divergence Times in Large Phylogenetic Trees
Britton, T., Anderson, C. L., Jacquet, D., Lundqvist, S., & Bremer, K. (2007) · Systematic Biology · doi:10.1080/10635150701613783 · Cited by 298
Rates of Evolution in Ancient DNA from Adélie Penguins
Lambert, D. M., Ritchie, P. A., Millar, C. D., Holland, B., Drummond, A. J., & Baroni, C. (2002) · Science · doi:10.1126/science.1068105 · Cited by 270
(2009) · doi:10.1093/oso/9780199535033.001.0001 · Cited by 267
Seyfried, M. (2002) · INTERNATIONAL JOURNAL OF SYSTEMATIC AND EVOLUTIONARY MICROBIOLOGY · doi:10.1099/ijs.0.01472-0 · Cited by 259
Unified modeling of gene duplication, loss, and coalescence using a locus tree
Rasmussen, M. D., & Kellis, M. (2012) · Genome Research · doi:10.1101/gr.123901.111 · Cited by 170
Inference of Viral Evolutionary Rates from Molecular Sequences
DRUMMON, A., OLIVERGPYBUS, & RAMBAUT, A. (2003) · Advances in Parasitology · doi:10.1016/s0065-308x(03)54008-8 · Cited by 169
Simultaneous Bayesian gene tree reconstruction and reconciliation analysis
Åkerborg, Ö., Sennblad, B., Arvestad, L., & Lagergren, J. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0806251106 · Cited by 162
Models, algorithms and programs for phylogeny reconciliation
Doyon, J., Ranwez, V., Daubin, V., & Berry, V. (2011) · Briefings in Bioinformatics · doi:10.1093/bib/bbr045 · Cited by 149
Lemey, P., Suchard, M. A., & Rambaut, A. (2009) · PLoS Currents · doi:10.1371/currents.rrn1031 · Cited by 104
Douzery, E. J. P., Delsuc, F., Stanhope, M. J., & Huchon, D. (2003) · Journal of Molecular Evolution · doi:10.1007/s00239-003-0028-x · Cited by 102
Drummond, A. J., & Rodrigo, A. G. (2000) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a026281 · Cited by 94
Battistuzzi, F. U., Filipski, A., Hedges, S. B., & Kumar, S. (2010) · Molecular Biology and Evolution · doi:10.1093/molbev/msq014 · Cited by 89
Origin and evolutionary history of HIV-1 subtype C in Brazil
Bello, G., Passaes, C., Guimarães, M. L., Lorete, R. S., Almeida, S. E. D. M., de Medeiros, R. M., de Alencastro, P. R., & Morgado, M. G. (2008) · AIDS · doi:10.1097/qad.0b013e328315e0aa · Cited by 88
The early molecular epidemiology of the swine-origin A/H1N1 human influenza pandemic
Rambaut, A., & Holmes, E. C. (2009) · PLoS Currents · doi:10.1371/currents.rrn1003 · Cited by 87
Pandemic (H1N1) 2009 virus revisited: An evolutionary retrospective
Christman, M. C., Kedwaii, A., Xu, J., Donis, R. O., & Lu, G. (2011) · Infection Genetics and Evolution · doi:10.1016/j.meegid.2011.02.021 · Cited by 72
Bayesian Estimation of Divergence Times from Large Sequence Alignments
Guindon, S. (2010) · Molecular Biology and Evolution · doi:10.1093/molbev/msq060 · Cited by 63
Real-time characterization of the molecular epidemiology of an influenza pandemic
Hedge, J., Lycett, S., & Rambaut, A. (2013) · Biology Letters · doi:10.1098/rsbl.2013.0331 · Cited by 47
Self-citationA distance-based least-square method for dating speciation events
Xia, X., & Yang, Q. (2011) · Molecular Phylogenetics and Evolution · doi:10.1016/j.ympev.2011.01.017 · Cited by 43
Birth-death prior on phylogeny and speed dating
Åkerborg, Ö., Sennblad, B., & Lagergren, J. (2008) · BMC Evolutionary Biology · doi:10.1186/1471-2148-8-77 · Cited by 28
Tree and rate estimation by local evaluation of heterochronous nucleotide data
Yang, Z., O’Brien, J., Zheng, X., Zhu, H., & She, Z.-S. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl577 · Cited by 22
Cited by
Bayesian phylogenetic and phylodynamic data integration using BEAST 1.10
Suchard, M. A., Lemey, P., Baele, G., Ayres, D. L., Drummond, A. J., & Rambaut, A. (2018) · Virus Evolution · doi:10.1093/ve/vey016 · Cited by 3,792
TreeTime: Maximum-likelihood phylodynamic analysis
Sagulenko, P., Puller, V., & Neher, R. A. (2018) · Virus Evolution · doi:10.1093/ve/vex042 · Cited by 1,186
Hördt, A., López, M. G., Meier-Kolthoff, J. P., Schleuning, M., Weinhold, L.-M., Tindall, B. J., Gronow, S., Kyrpides, N. C., Woyke, T., & Göker, M. (2020) · Frontiers in Microbiology · doi:10.3389/fmicb.2020.00468 · Cited by 488
Bayesian molecular clock dating of species divergences in the genomics era
dos Reis, M., Donoghue, P. C. J., & Yang, Z. (2016) · Nature Reviews Genetics · doi:10.1038/nrg.2015.8 · Cited by 339
Phylogenomics of 10,575 genomes reveals evolutionary proximity between domains Bacteria and Archaea
Zhu, Q., Mai, U., Pfeiffer, W., Janssen, S., Asnicar, F., Sanders, J. G., Belda-Ferre, P., Al-Ghalith, G. A., Kopylova, E., McDonald, D., et al. (2019) · Nature Communications · doi:10.1038/s41467-019-13443-4 · Cited by 355
Metadata
- Authors
- To, T.-H., Jung, M., Lycett, S., & Gascuel, O.
- Venue
- Systematic Biology
- Publisher
- Oxford University Press (OUP)
- Published
- 2015-09-30
- Volume
- 65
- Issue
- 1
- Pages
- 82-97
- ISSN
- 1063-5157 (ISSN-L)
- 1076-836X
- OpenAlex
- W1923320973
- Cited by
- 437
- References
- 62
- FWCI
- 9.26
- 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
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.