CoChat

Terrace Aware Data Structure for Phylogenomic Inference from Supermatrices

Open access
Chernomor, Olga, von Haeseler, Arndt, Minh, Bui Quang · 2016 · Systematic Biology

The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.

Abstract

In phylogenomics the analysis of concatenated gene alignments, the so-called supermatrix, is commonly accompanied by the assumption of partition models. Under such models each gene, or more generally partition, is allowed to evolve under its own evolutionary model. Although partition models provide a more comprehensive analysis of supermatrices, missing data may hamper the tree search algorithms due to the existence of phylogenetic (partial) terraces. Here, we introduce the phylogenetic terrace aware (PTA) data structure for the efficient analysis under partition models. In the presence of missing data PTA exploits (partial) terraces and induced partition trees to save computation time. We show that an implementation of PTA in IQ-TREE leads to a substantial speedup of up to 4.5 and 8 times compared with the standard IQ-TREE and RAxML implementations, respectively. PTA is generally applicable to all types of partition models and common topological rearrangements thus can be employed by all phylogenomic inference software.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/sysbio/syw037

Cites

42 of 42 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1. The species tree T and the two NNI neighboring trees TNNI1 and TNNI2, obtained by NNIs around the central edge e. NNI, nearest neighbor interchange.
Figure 1. The species tree T and the two NNI neighboring trees TNNI1 and TNNI2, obtained by NNIs around the central edge e. NNI, nearest neighbor interchange.CC BY-NC · PubMed Central
Figure 2. (a) Three adjacent edges on species tree T and (b) their corresponding edges on partition tree T|Yi.
Figure 2. (a) Three adjacent edges on species tree T and (b) their corresponding edges on partition tree T|Yi.CC BY-NC · PubMed Central
Figure 3. CPU time comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the runtime ratios for 10 runs between a comparing program and the mean runtime of IQ-TREEPTA. Boxes below the horizontal line indicate instances where corresponding program is slower than IQ-TREEPTA. EUL, Edge-Unlinked and EL, Edge-Linked.
Figure 3. CPU time comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the runtime ratios for 10 runs between a comparing program and the mean runtime of IQ-TREEPTA. Boxes below the horizontal line indicate instances where corresponding program is slower than IQ-TREEPTA. EUL, Edge-Unlinked and EL, Edge-Linked.CC BY-NC · PubMed Central
Figure 4. Log-likelihood comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the log-likelihood differences for 10 runs between a comparing program and the mean log-likelihood of RAxML standard (panels a and b) or IQ-TREE standard (panel c). Boxes below the horizontal line indicate that the corresponding program has a smaller log-likelihood than RAxML mean log-likelihood (panels a and b) or IQ-TREE mean log-likelihood (panel c). RAxML and RAxMLoptU have identical log-likelihoods given the same starting tree. We therefore omit RAxMLoptU in the plot.
Figure 4. Log-likelihood comparisons of different implementations under (a) EUL, (b) EL-equal, and (c) EL-proportional partition models. Each boxplot shows the distribution of the log-likelihood differences for 10 runs between a comparing program and the mean log-likelihood of RAxML standard (panels a and b) or IQ-TREE standard (panel c). Boxes below the horizontal line indicate that the corresponding program has a smaller log-likelihood than RAxML mean log-likelihood (panels a and b) or IQ-TREE mean log-likelihood (panel c). RAxML and RAxMLoptU have identical log-likelihoods given the same starting tree. We therefore omit RAxMLoptU in the plot.CC BY-NC · PubMed Central
Figure A.1. Cases that do not change the topology of the partition tree under the EL models. Each tree is a species tree: before NNI (T, first row) and after NNI (TNNI, second and third rows). The edges and the species sets leading to them are the same as in Figure 1 (e.g., on T the upper left edge is e1 with the species set A and so on). Here, fi(.) of gray colored edges is equal to ϵ and gray triangles correspond to taxa sets, which are absent on the considered partition tree: T|Yi,TNNI1|Yi or TNNI2|Yi. The black colored parts correspond to the topologies of these induced partition trees. The arrows show edges that were swapped during NNI around the central branch e on T.
Figure A.1. Cases that do not change the topology of the partition tree under the EL models. Each tree is a species tree: before NNI (T, first row) and after NNI (TNNI, second and third rows). The edges and the species sets leading to them are the same as in Figure 1 (e.g., on T the upper left edge is e1 with the species set A and so on). Here, fi(.) of gray colored edges is equal to ϵ and gray triangles correspond to taxa sets, which are absent on the considered partition tree: T|Yi,TNNI1|Yi or TNNI2|Yi. The black colored parts correspond to the topologies of these induced partition trees. The arrows show edges that were swapped during NNI around the central branch e on T.CC BY-NC · PubMed Central
Figure A.2. General representations of (a) SPR and (b) TBR, where the triangles denote the subtrees below the corresponding edges. SPR, subtree pruning and regrafting, TBR, tree bisection and reconnection.
Figure A.2. General representations of (a) SPR and (b) TBR, where the triangles denote the subtrees below the corresponding edges. SPR, subtree pruning and regrafting, TBR, tree bisection and reconnection.CC BY-NC · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

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

1 retracted

Cited by

See all 2,252

Metadata

Authors
Chernomor, O., von Haeseler, A., & Minh, B. Q.
Affiliations
University of Vienna (AT)
Venue
Systematic Biology
Published
2016-04-26
Volume
65
Issue
6
Pages
997-1008
ISSN
  • 1063-5157 (ISSN-L)
  • 1076-836X
OpenAlex
W2344940607
Cited by
2,252
References
41
Citations by year
2026: 240 · 2025: 285 · 2024: 328 · 2023: 322 · 2022: 289 · 2021: 331 · 2020: 214 · 2019: 134 · 2018: 75 · 2017: 31 · 2016: 3
FWCI
42.08
Type
journal article
Language
en
Open access
Licence
cc-by-nc
Locations
  • Systematic Biology (publishedVersion, cc-by-nc)
  • PubMed Central (publishedVersion, cc-by-nc)
  • PubMed (publishedVersion)
  • HighWire Press Open Archive (submittedVersion)
Funders
Austrian Science Fund (I-2805-B29, I-1824-B22)
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
  • Life Sciences › Agricultural and Biological Sciences › Ecology, Evolution, Behavior and Systematics › Plant Diversity and Evolution
Keywords
partition model, supermatrix, missing data, phylogenetic tree search, IQ-TREE, RAxML, data structures
MeSH terms
Algorithms, Classification, Biological Evolution, Models, Biological, Phylogeny, Software, Sequence Analysis, DNA

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.