Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
Motivation: The current molecular data explosion poses new challenges for large-scale phylogenomic analyses that can comprise hundreds or even thousands of genes. A property that characterizes phylogenomic datasets is that they tend to be gappy, i.e. can contain taxa with (many and disparate) missing genes. In current phylogenomic analyses, this type of alignment gappyness that is induced by missing data frequently exceeds 90%. We present and implement a generally applicable mechanism that allows for reducing memory footprints of likelihood-based [maximum likelihood (ML) or Bayesian] phylogenomic analyses proportional to the amount of missing data in the alignment. We also introduce a set of algorithmic rules to efficiently conduct tree searches via subtree pruning and re-grafting moves using this mechanism. Results: On a large phylogenomic DNA dataset with 2177 taxa, 68 genes and a gappyness of 90%, we achieve a memory footprint reduction from 9 GB down to 1 GB, a speedup for optimizing ML model parameters of 11, and accelerate the Subtree Pruning Regrafting tree search phase by factor 16. Thus, our approach can be deployed to improve efficiency for the two most important resources, CPU time and memory, by up to one order of magnitude. Availability: Current open-source version of RAxML v7.2.6 available at http://wwwkramer.in.tum.de/exelixis/software.html. Contact: stamatak@cs.tum.edu
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Evolutionary trees from DNA sequences: A maximum likelihood approach.
Felsenstein, J. (1981) · Journal of Molecular Evolution · doi:10.1007/bf01734359 · Cited by 14,571
Yang, Z. (1994) · Journal of Molecular Evolution · doi:10.1007/bf00160154 · Cited by 2,960
Whelan, S., & Goldman, N. (2001) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a003851 · Cited by 2,849 · cited 2×
“The inferences were conducted under the General Time Reversible (GTR) model of nucleotide substitution (Tavaré, 1986) and the WAG (Whelan and Goldman, 2001) amino acid substitution model for protein data.”
MethodAssessing the root of bilaterian animals with scalable phylogenomic methods
Hejnol, A., Obst, M., Stamatakis, A., Ott, M., Rouse, G. W., Edgecombe, G. D., Martinez, P., Baguñà, J., Bailly, X., Jondelius, U., et al. (2009) · Proceedings of the Royal Society B: Biological Sciences · doi:10.1098/rspb.2009.0896 · Cited by 747 · cited 2×
“The largest published ML-based phylogenomic study in terms of CPU hours and memory requirements already required 2.25 million CPU hours and 15 GB of main memory on an IBM BlueGene/L supercomputer (Hejnol et al., 2009).”
BackgroundInfluentialSelf-citation
Cited by
UFBoot2: Improving the Ultrafast Bootstrap Approximation
Hoang, D. T., Chernomor, O., von Haeseler, A., Minh, B. Q., & Vinh, L. S. (2018) · Molecular Biology and Evolution · doi:10.1093/molbev/msx281 · Cited by 10,881
“(Bouchenak-Khelladi et al. 2008; Fabre et al. 2009; Stamatakis and Alachiotis 2010; van der Linde et al. 2010; Pyron et al. 2011; Nyakatura and Bininda-Emonds 2012; Springer et al. 2012; Hinchliff and Roalson 2013; Salichos and Rokas 2013; Dell’Ampio et al. 2014), we observed more discrepancies between resampling stra…”
BackgroundraxmlGUI: a graphical front-end for RAxML
Silvestro, D., & Michalak, I. (2012) · Organisms Diversity & Evolution · doi:10.1007/s13127-011-0056-0 · Cited by 2,864
Terrace Aware Data Structure for Phylogenomic Inference from Supermatrices
Chernomor, O., von Haeseler, A., & Minh, B. Q. (2016) · Systematic Biology · doi:10.1093/sysbio/syw037 · Cited by 2,252
Woudenberg, J. H. C., Groenewald, J. Z., Binder, M., & Crous, P. W. (2013) · Studies in Mycology · doi:10.3114/sim0015 · Cited by 835
Alternaria section Alternaria: Species,formae speciales or pathotypes?
Woudenberg, J. H. C., Seidl, M. F., Groenewald, J. Z., de Vries, M., Stielow, J. B., Thomma, B. P. H. J., & Crous, P. W. (2015) · Studies in Mycology · doi:10.1016/j.simyco.2015.07.001 · Cited by 618
Metadata
- Authors
- Stamatakis, A., & Alachiotis, N.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2010-06-01
- Volume
- 26
- Issue
- 12
- Pages
- i132-i139
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2102840198
- Cited by
- 124
- References
- 4
- FWCI
- 1.77
- 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: Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data. https://app.cochat.ai/papers/10.1093/bioinformatics/btq205
- The paper
- Stamatakis, A., & Alachiotis, N. (2010). Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data. Bioinformatics. https://doi.org/10.1093/bioinformatics/btq205
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.