Species Trees are Recoverable from Unrooted Gene Tree Topologies Under a Constant Rate of Horizontal Gene Transfer

Constantinos Daskalakis, Sébastien Roch

Abstract

Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes, which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of horizontal genetic transfer (HGT), where a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from, but related to, the species phylogeny. In previous work, a natural stochastic models of HGT was introduced and studied. It was shown, both in simulation and theoretical studies, that a species phylogeny can be reconstructed from gene trees despite surprisingly high rates of HGT under this model. Rigorous lower and upper bounds on this achievable rate were also obtained, but a large gap remained. Here we close this gap, up to a constant. Specifically we show that a species phylogeny can be reconstructed correctly from gene trees even when, on each gene, each edge of the species tree has a constant probability of being the location of an HGT event. Our new reconstruction algorithm, which relies only on unrooted gene tree topologies, builds the tree recursively from the leaves and runs in polynomial time. We also provide a matching bound in the negative direction (up to a constant) and extend our results to some cases where gene trees are not perfectly known.

Introduction: The Messy Reality of Evolution

In an ideal evolutionary scenario, every gene in an organism would share a single history, tracing back to a common ancestor in a neat, branching "Tree of Life." However, biological reality is often more complex. Through Horizontal Gene Transfer (HGT)—prevalent in bacteria and viruses—genes can jump between distant species rather than being inherited vertically. This process creates a conflict: the "Gene Tree" (the history of a specific gene) may differ significantly from the "Species Tree" (the actual history of the species).

A Horizontal Gene Transfer (HGT) event (left) where a gene moves from donor D to recipient R, resulting in a gene tree (right) with a topology distinct from the species tree.

The central challenge addressed in this work is determining how much HGT a reconstruction algorithm can tolerate before the species tree's signal is lost. Previous theoretical bounds suggested that recovery was only possible if HGT rates vanished as the tree grew ($O(1/\log n)$). This paper demonstrates that recovery is possible even when HGT occurs at a constant rate across every branch, regardless of the number of species.

Methodology: A Robust Recursive Approach

The authors utilize a stochastic model where HGT events follow a Poisson process along the species tree. They propose a new, polynomial-time recursive reconstruction algorithm that builds the tree from the leaves upward. Key methodological innovations include:

  • Median Distance Estimation: Using the median distance between species across multiple gene trees provides a robust estimator. Since HGT events act as random outliers, they do not skew the median as they would a simple average.
  • Diluted Subtrees: To reconstruct deeper ancestral nodes, the algorithm identifies "diluted subtrees"—parts of gene trees that have fortuitously escaped HGT. These serve as anchors for estimating deeper phylogenetic distances.
  • Resilience to Imperfect Data: The algorithm is designed to handle unrooted gene trees and $\epsilon$-contractions, where short branches might be missing or poorly resolved.

Key Results and Theoretical Breakthroughs

The most significant contribution of this work is the proof that the phylogenetic signal is not destroyed by a constant rate of HGT. As long as the rate $\lambda$ is below a certain constant threshold, the species tree remains recoverable.

  • Theorem 1 (Algorithmic Recovery): For a species tree with $n$ leaves, the topology can be reconstructed with high probability using $N = \Omega(\log n)$ gene trees, even under a constant HGT rate.
  • Theorem 3 (Impossibility Bound): The authors provide a matching negative result, showing that if the HGT rate exceeds a specific constant threshold, distinct species trees become statistically indistinguishable based on gene tree distributions, making recovery impossible regardless of the algorithm used.
  • Efficiency: The proposed recursive approach is computationally efficient, running in polynomial time relative to the number of species and genes.

Discussion and Future Outlook

This work closes a significant theoretical gap in phylogenetics by proving the recoverability of species trees under constant-rate HGT. While the model currently focuses on HGT, future work could integrate other sources of gene tree discordance, such as incomplete lineage sorting (ILS) or gene duplication and loss. Additionally, refining the exact numerical threshold for the HGT rate in practical applications remains an important open question. The current model assumes some bounds on substitution rates are known; extending this to completely unknown, heterogeneous rates across all branches would be a valuable next step.

Summary updated

Abstract

Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes, which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of horizontal genetic transfer (HGT), where a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from, but related to, the species phylogeny. In previous work, a natural stochastic models of HGT was introduced and studied. It was shown, both in simulation and theoretical studies, that a species phylogeny can be reconstructed from gene trees despite surprisingly high rates of HGT under this model. Rigorous lower and upper bounds on this achievable rate were also obtained, but a large gap remained. Here we close this gap, up to a constant. Specifically we show that a species phylogeny can be reconstructed correctly from gene trees even when, on each gene, each edge of the species tree has a constant probability of being the location of an HGT event. Our new reconstruction algorithm, which relies only on unrooted gene tree topologies, builds the tree recursively from the leaves and runs in polynomial time. We also provide a matching bound in the negative direction (up to a constant) and extend our results to some cases where gene trees are not perfectly known.
BibTeX
@misc{daskalakis2015species,
  author = {Constantinos Daskalakis and Sébastien Roch},
  title = {{Species Trees are Recoverable from Unrooted Gene Tree Topologies Under a Constant Rate of Horizontal Gene Transfer}},
  year = {2015},
  eprint = {1508.01962},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.01962},
}
Figure