Statistically Consistent Rooting of Species Trees under the Multispecies Coalescent Model

Yasamin Tabatabaee, Sébastien Roch, Tandy WarnowbioRxiv 2022 · DOI

TL;DR

This paper introduces QR-STAR, a new algorithm for rooting phylogenetic species trees that is statistically consistent under the multispecies coalescent model. Unlike its predecessor QR, QR-STAR's statistical guarantees ensure it will converge to the correct root as more gene tree data becomes available, making it a more reliable tool for evolutionary inference.

What Problem Does This Paper Address?

Phylogenetic trees are fundamental to understanding evolutionary relationships. Rooted species trees, in particular, are crucial for applications like comparative genomics and evolutionary dating. However, inferring these rooted trees is challenging. A common approach is to first infer an unrooted species tree and then use a separate method to determine the root. This rooting step is often problematic, as traditional methods like using outgroups can be unreliable, and other approaches that rely on molecular clock assumptions can degrade in accuracy.

Recently, Quintet Rooting (QR) was developed as a polynomial-time method to root species trees using unrooted gene trees, specifically addressing discordance caused by incomplete lineage sorting (ILS) under the multispecies coalescent (MSC) model. While QR showed good accuracy, its statistical consistency – its ability to guarantee finding the correct root with increasing amounts of data – was an open question. This paper aims to address this gap by developing a statistically consistent rooting method.

Methods

The core innovation of QR-STAR is an extension to the existing Quintet Rooting (QR) algorithm. QR works by evaluating potential rootings of a species tree based on how well they explain the observed unrooted gene tree topologies, using a cost function derived from theoretical properties of 5-taxon trees under the MSC model (known as ADR invariants and inequalities).

QR-STAR enhances QR by adding a crucial preprocessing step: determining the rooted shape of each quintet tree. This involves analyzing the distribution of unrooted gene trees for a given set of five taxa and inferring whether the underlying rooted species tree shape is caterpillar, balanced, or pseudo-caterpillar. This inferred shape information is then incorporated into the cost function as a "shape penalty." This penalty term penalizes rootings that do not match the inferred shape, thereby guiding the algorithm towards a statistically consistent solution. The authors prove that QR-STAR is statistically consistent under the MSC model, meaning that as the number of input gene trees increases, the probability of correctly rooting the species tree converges to 1.

Datasets

The study utilizes simulated datasets for training and evaluation.

  • Training Data: 101-taxon simulated datasets from [35] were used to explore QR-STAR's parameter space and tune its algorithmic parameters.
  • Test Data: 201-taxon simulated datasets from [20] were used for evaluating QR-STAR's accuracy against QR. These datasets were characterized by varying speciation rates, tree heights (influencing ILS levels), and number of genes.

Key Insights and Ideas

  • Statistical Consistency is Crucial for Rooting: While QR showed good accuracy, the lack of statistical consistency meant it couldn't guarantee finding the correct root with more data. QR-STAR's key contribution is providing this guarantee.
  • Rooted Shape Matters: Incorporating the inferred rooted shape of quintet trees into the cost function is the critical modification that leads to statistical consistency. This suggests that understanding the local topological structure (shape) is vital for robust rooting.
  • Trade-offs in Rooting and Estimation: The paper hints at complex interactions between ILS, gene tree estimation error (GTEE), and rooting accuracy. High ILS can sometimes make rooting easier if gene tree estimation is accurate, but high GTEE can be detrimental to both species tree estimation and rooting.
  • Sample Complexity: The theoretical analysis suggests that the sample complexity (how many gene trees are needed for consistency) depends on the "path length parameter" of the species tree, which is related to its shortest and longest internal branches. This is different from species tree estimation methods where only the shortest branch length is typically considered.

Key Results

  • Statistical Consistency Proven: QR-STAR is mathematically proven to be statistically consistent under the multispecies coalescent model.
  • Competitive Accuracy: Simulation studies show that QR-STAR matches or improves upon the accuracy of the original QR algorithm across various model conditions.
  • Polynomial Time Complexity: QR-STAR maintains the polynomial time complexity of QR, making it computationally feasible for large datasets.
  • Impact of Parameters: Experiments highlight that QR-STAR's performance is sensitive to its parameters (shape coefficient C and the ratio of inequality to invariant weights), but optimal accuracy can be achieved within a reasonable range.

Limitations and Future Work

  • Assumption of ILS: The statistical consistency proofs are based on the assumption that discordance between gene trees and species trees is solely due to ILS. The method's performance under other sources of discordance, such as gene duplication and loss (GDL), is not addressed.
  • True Gene Trees: The theoretical proofs assume that the input gene trees are "true" gene trees, meaning they have no gene tree estimation error. While simulations explore GTEE, the theoretical guarantees do not directly account for it.
  • Cost Function Variations: The paper proves consistency for a specific form of cost function (linear combination of invariant, inequality, and shape penalties). Exploring other cost function forms that might lead to statistical consistency is a future direction.
  • Direct Rooted Tree Inference: The authors suggest that the proof of consistency for 5-taxon trees implies that it might be possible to directly estimate the rooted species tree topology from unrooted gene trees without first inferring an unrooted species tree. This is a challenging but promising area for future research.
  • Empirical Performance: While statistically consistent, the empirical performance of a cost function is also important. Future work could focus on designing cost functions that not only guarantee consistency but also provide accurate rooted tree estimations in practice. Incorporating estimated branch lengths is also suggested.

Summary updated

Abstract

Abstract Rooted species trees are used in several downstream applications of phylogenetics. Most species tree estimation methods produce unrooted trees and additional methods are then used to root these unrooted trees. Recently, Quintet Rooting (QR) (Tabatabaee et al., ISMB and Bioinformatics 2022), a polynomial-time method for rooting an unrooted species tree given unrooted gene trees under the multispecies coalescent, was introduced. QR, which is based on a proof of identifiability of rooted 5-taxon trees in the presence of incomplete lineage sorting, was shown to have good accuracy, improving over other methods for rooting species trees when incomplete lineage sorting was the only cause of gene tree discordance, except when gene tree estimation error was very high. However, the statistical consistency of QR was left as an open question. Here, we present QR-STAR, a polynomial-time variant of QR that has an additional step for determining the rooted shape of each quintet tree. We prove that QR-STAR is statistically consistent under the multispecies coalescent model. Our simulation study under a variety of model conditions shows that QR-STAR matches or improves on the accuracy of QR. QR-STAR is available in open source form at https://github.com/ytabatabaee/Quintet-Rooting .
BibTeX
@misc{tabatabaee2022statistically,
  author = {Yasamin Tabatabaee and Sébastien Roch and Tandy Warnow},
  title = {{Statistically Consistent Rooting of Species Trees under the Multispecies Coalescent Model}},
  year = {2022},
  doi = {10.1101/2022.10.26.513897},
  howpublished = {bioRxiv},
}
Figure