Species tree estimation under joint modeling of coalescence and duplication: Sample complexity of quartet methods

Max Hill, Brandon Legried, Sébastien RochThe Annals of Applied Probability 2022 · DOI

TL;DR

This paper tackles the challenge of accurately reconstructing species evolutionary trees when gene trees are influenced by both incomplete lineage sorting (ILS) and gene duplication/loss (GDL). The authors derive theoretical bounds on how many gene sequences (sample complexity) are needed for quartet-based methods to reliably estimate the true species tree, revealing how duplication and loss rates impact this requirement.

What Problem Does This Paper Address?

Evolutionary biologists often infer the history of species by analyzing the evolutionary history of individual genes within those species. However, the evolutionary history of a gene (a gene tree) doesn't always perfectly mirror the evolutionary history of the species it belongs to (the species tree). This discordance arises from several biological processes, primarily:

  • Incomplete Lineage Sorting (ILS): When a speciation event occurs, ancestral gene lineages may not sort perfectly into the new species, leading to gene trees that differ from the species tree. This is often modeled by the coalescent process.
  • Gene Duplication and Loss (GDL): Genes can be duplicated within a genome, and some copies can be lost over time. These events can also lead to gene trees that don't align with the species tree.

Reconstructing the species tree accurately in the presence of both ILS and GDL is a significant challenge. While methods exist that handle ILS or GDL individually, understanding their combined effect and the data requirements for accurate inference is crucial. This paper addresses this by developing a unified model and analyzing the sample complexity of popular quartet-based methods under this combined evolutionary scenario.

Methods

The authors employ a probabilistic approach to analyze the DLCoal model, which unifies the multispecies coalescent (for ILS) and a branching process (for GDL). Their core contribution is deriving sample complexity bounds for quartet-based species tree estimation methods, specifically ASTRAL-one.

The analysis involves:

  • Probabilistic Modeling: Rigorously defining the DLCoal model and the generation of gene trees from a species tree.
  • Identifiability Proofs: Demonstrating that the species tree topology can, in principle, be uniquely determined from the distribution of gene trees under the DLCoal model. This is a foundational step for any statistical inference method.
  • Mathematical Analysis of Quartet Frequencies: Analyzing how the frequencies of different gene tree topologies for quartets (groups of four species) are influenced by the species tree topology, ILS, and GDL rates.
  • Derivation of Sample Complexity Bounds: Using these analyses, they derive upper bounds on the number of gene trees ($k$) required for ASTRAL-one to reconstruct the true species tree with high probability. These bounds explicitly depend on parameters like the shortest branch length of the species tree ($f$), the tree depth ($\Delta$), and the duplication ($\lambda$) and loss ($\mu$) rates.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and deriving bounds based on a simulated model rather than empirical datasets.

Key Insights and Ideas

  • Unified Model is Key: The DLCoal model provides a more realistic framework for understanding gene tree discordance than models considering ILS or GDL in isolation.
  • Quartet Methods are Robust (Theoretically): The paper shows that quartet-based methods like ASTRAL-one have strong theoretical guarantees (identifiability and consistency) even under the complex DLCoal model.
  • Duplication and Loss Rates Matter Significantly: The sample complexity is not just dependent on the tree's structure but also crucially on the rates of gene duplication and loss. This highlights that these evolutionary processes can obscure the true species history.
  • Counter-Intuitive Behavior in Supercritical Regimes: The analysis reveals that in the "supercritical" regime (where duplication rates are higher than loss rates, $\lambda > \mu$), the sample complexity can increase. This is because a high number of gene copies at a common ancestor can lead to a large number of conflicting quartet topologies, making it harder to discern the true species tree.
  • Identifiability is Achieved: The paper proves that the species tree is identifiable from gene trees, meaning that different species trees will, in principle, produce different distributions of gene trees.

Key Results

  • Identifiability Theorem: The unrooted species tree is identifiable from the distribution of multi-labeled gene trees under the DLCoal model.
  • Consistency Theorems: Both ASTRAL-one and ASTRAL-multi are shown to be statistically consistent, meaning they converge to the true species tree as the number of gene trees increases.
  • Sample Complexity Bound (Theorem 1): The paper provides the first theoretical upper bound on the sample complexity of ASTRAL-one under the DLCoal model. This bound shows that the number of gene trees required ($k$) depends on:
  • The shortest branch length of the species tree ($f$).
  • The depth of the species tree ($\Delta$).
  • The duplication ($\lambda$) and loss ($\mu$) rates.
  • The number of species ($n$). The bound highlights that both subcritical ($\mu > \lambda$) and supercritical ($\lambda > \mu$) regimes can lead to increased sample complexity, albeit for different biological reasons.

Limitations and Future Work

  • Theoretical Bounds: The derived bounds are upper bounds, and it's an open question whether they are tight or if tighter bounds exist.
  • Optimality of Dependence: The paper poses the question of whether the dependence on parameters like $\alpha$ (maximum expected number of lineages) and $\sigma$ (minimum survival probability of a quartet) is optimal.
  • Alternative Methods: The authors suggest exploring alternative methods for processing multi-labeled gene trees that might be less sensitive to the effects of gene duplication.
  • Incorporating LGT: Extending these analyses to include Lateral Gene Transfer (LGT) is a significant future direction, as LGT is another important factor causing gene tree discordance.
  • Lower Bounds: Deriving lower bounds for sample complexity would be a valuable next step to complement the upper bounds.

Summary updated

Abstract

We consider species tree estimation under a standard stochastic model of gene tree evolution that incorporates incomplete lineage sorting (as modeled by a coalescent process) and gene duplication and loss (as modeled by a branching process). Through a probabilistic analysis of the model, we derive sample complexity bounds for widely used quartet-based inference methods that highlight the effect of the duplication and loss rates in both subcritical and supercritical regimes.
BibTeX
@article{hill2022species,
  author = {Max Hill and Brandon Legried and Sébastien Roch},
  title = {{Species tree estimation under joint modeling of coalescence and duplication: Sample complexity of quartet methods}},
  journal = {The Annals of Applied Probability},
  year = {2022},
  doi = {10.1214/22-aap1799},
}
Figure