Polynomial-Time Statistical Estimation of Species Trees Under Gene Duplication and Loss

Brandon Legried, Erin K. Molloy, Tandy Warnow, Sébastien Roch

TL;DR

This paper tackles the challenge of accurately reconstructing species evolutionary trees when genes can be duplicated and lost, a common complication in genomic data. The authors prove that species trees are theoretically identifiable under a standard gene duplication and loss (GDL) model and demonstrate that the ASTRAL-multi algorithm is statistically consistent for this task, meaning it will converge to the correct tree with enough data.

What Problem Does This Paper Address?

Estimating the evolutionary history of species (phylogenomics) is crucial for understanding biodiversity. A common approach is to analyze multiple gene families from different species. However, the evolutionary history of individual genes can differ from the species' history due to processes like incomplete lineage sorting (ILS) and gene duplication and loss (GDL). While ILS has been extensively studied, GDL presents a more significant challenge for species tree reconstruction. This paper focuses on the GDL problem, specifically addressing whether the true species tree can be reliably inferred from gene trees that have undergone duplication and loss.

Methods

The core of the paper involves two main components: theoretical guarantees and empirical validation.

  • Theoretical Guarantees: The authors first establish the "identifiability" of a species tree under a specific GDL model. This means that if two different species trees generate gene tree distributions, those distributions must be distinguishable. They then prove the "statistical consistency" of ASTRAL-multi, a polynomial-time algorithm. Statistical consistency means that as the number of gene trees analyzed increases, the algorithm is guaranteed to converge to the correct species tree topology.
  • ASTRAL-multi: This algorithm is a variant of the ASTRAL suite designed to handle "multi-labeled trees" (MUL-trees), where a single species can have multiple gene copies due to duplication. It works by considering all possible quartet relationships (relationships among four species) and finding the species tree that best explains these relationships. The paper discusses both the exact (potentially exponential time) and default (polynomial time) versions of ASTRAL-multi.

Datasets

The study uses simulated datasets generated to mimic real biological scenarios.

  • Simulated Data: The authors generated 16-taxon datasets using the SimPhy software. These datasets were simulated under a gene duplication and loss (GDL) model with varying GDL rates and gene tree estimation error (GTEE) levels. The GDL rates were based on estimates from a fungal dataset, and GTEE was introduced by varying sequence alignment lengths.

Key Insights and Ideas

  • Identifiability is Key: The paper's theoretical contribution hinges on proving that species trees are indeed identifiable from gene trees under GDL. This is a fundamental prerequisite for any statistical method to be successful.
  • ASTRAL-multi's Promise: The demonstration that ASTRAL-multi is statistically consistent under GDL is a significant finding. It suggests that this polynomial-time method can reliably reconstruct species trees even in the presence of gene duplication and loss, provided sufficient data.
  • GDL vs. ILS: The paper highlights that GDL poses a distinct challenge compared to ILS, requiring specific theoretical and algorithmic considerations.
  • Quartet-Based Methods Shine: The success of ASTRAL-multi, a quartet-based method, under GDL conditions reinforces the power of such approaches in phylogenomics.

Key Results

  • Theoretical Consistency: The paper provides formal proofs for the identifiability of species trees and the statistical consistency of ASTRAL-multi under a standard GDL model.
  • Simulation Performance: In simulation studies, ASTRAL-multi demonstrated high accuracy, especially when a sufficient number of gene trees were analyzed.
  • Even with only 25 true gene trees, ASTRAL-multi showed low error rates (<1% for lower GDL rates, <6% for higher GDL rates).
  • Error generally increased with higher GDL rates and gene tree estimation error (GTEE), and decreased with more genes.
  • When compared to other methods (DupTree, MulRF, STAG, ASTRID-multi), ASTRAL-multi was competitive, particularly with larger gene numbers. In some challenging scenarios (high GDL, high GTEE), ASTRID-multi sometimes outperformed ASTRAL-multi.

Limitations and Future Work

  • Model Simplification: The theoretical proofs are based on a "simple GDL model" and do not explicitly account for incomplete lineage sorting (ILS) or other complexities like horizontal gene transfer. While the simulations do incorporate ILS, the theoretical guarantees are for a simplified scenario.
  • Dataset Size: The simulation study was limited to a 16-taxon species tree. The authors suggest future work should investigate performance on larger datasets with more species.
  • Computational Complexity: While ASTRAL-multi is polynomial-time, the "exact mode" can still be computationally intensive. The default mode's efficiency is crucial for large-scale applications.
  • Broader Conditions: Future research should explore empirical performance and statistical consistency under a wider range of gene tree heterogeneity causes and more complex biological scenarios.
  • Comparison with Other Methods: The authors suggest exploring other methods like DynaDup, InferNetwork, and PHYLDOG, especially their performance on larger datasets and under more realistic evolutionary models.

Summary updated

Abstract

Phylogenomics-the estimation of species trees from multilocus data sets-is a common step in many biological studies. However, this estimation is challenged by the fact that genes can evolve under processes, including incomplete lineage sorting (ILS) and gene duplication and loss (GDL), that make their trees different from the species tree. In this article, we address the challenge of estimating the species tree under GDL. We show that species trees are <i>identifiable</i> under a standard stochastic model for GDL, and that the polynomial-time algorithm ASTRAL-multi, a recent development in the ASTRAL suite of methods, is <i>statistically consistent</i> under this GDL model. We also provide a simulation study evaluating ASTRAL-multi for species tree estimation under GDL.
BibTeX
@article{legried2020polynomial,
  author = {Brandon Legried and Erin K. Molloy and Tandy Warnow and Sébastien Roch},
  title = {{Polynomial-Time Statistical Estimation of Species Trees Under Gene Duplication and Loss}},
  journal = {Journal of Computational Biology},
  year = {2020},
  doi = {10.1089/cmb.2020.0424},
}
Figure