Distorted metrics on trees and phylogenetic forests

Elchanan Mossel

Abstract

Reconstructing the full evolutionary tree of life is a fundamental challenge in biology, often hampered by the unreliability of long-range genetic distances. This paper introduces a polynomial-time algorithm to reconstruct a "phylogenetic forest"—a collection of trees capturing most of the original structure—using sequences of only logarithmic length. By formalizing the concept of distorted metrics, the study proves that while the entire tree might be elusive with limited data, a high-quality forest can be recovered efficiently.

Introduction: The Challenge of Deep Time

In phylogenetics, the goal is to reconstruct the branching history of species from genetic sequences. However, as species diverge, the statistical signal of their common ancestry decays. Empirical distance estimates, such as those derived from the log-det of a covariance matrix, become highly distorted for distant species. Traditionally, accurate reconstruction of the entire tree required an exponential amount of data. This research addresses what can be recovered when only logarithmic sequence length is available.

Methodology: Distorted Metrics and Glueing

The core of the approach is the definition of an $(\epsilon, M)$ distortion. Distances are considered reliable (within $\epsilon$) only if they fall below a threshold $M$. Beyond $M$, the metric provides no useful information.

The reconstruction follows a two-stage process:

  1. Local Reconstruction: For each leaf, a small local tree is built using only reliable distances.
  2. The Glueing Algorithm: These overlapping local trees are merged into an edge-disjoint forest. This process utilizes the "4-point method" to resolve topologies and identify shared edges.
Figure 2: Illustration of the topological relationships used in the glueing algorithm, showing how local paths and internal nodes are identified and connected.

The algorithm is validated using standard evolutionary models like Cavender-Farris-Neyman (CFN) and Jukes-Cantor, ensuring the theoretical results translate to biological sequence data.

Key Results and Insights

The primary result is a reconstruction guarantee: the algorithm produces a forest $T_1, \dots, T_\alpha$ such that the true tree $T$ can be recovered by adding exactly $\alpha - 1$ edges. Crucially, the number of components $\alpha$ is bounded by: $$\alpha \leq \lfloor 1 + \frac{60n}{\sqrt{2}} 2^{-\frac{M-\epsilon}{2g}} \rfloor$$ where $g$ is the maximum edge length. As the reliability threshold $M$ increases, the forest naturally converges toward a single tree.

Furthermore, the paper demonstrates that a high-quality forest can be reconstructed with sequence lengths of $O(\log n)$, a significant improvement over previous requirements. This provides a formal proof for the biological intuition that most of a tree's edges are relatively easy to recover, even if the full topology remains uncertain.

Conclusion

By shifting the goal from a single, potentially erroneous tree to a robust phylogenetic forest, this work provides a mathematically rigorous framework for large-scale evolutionary reconstruction. The techniques offer a promising "divide and conquer" strategy for systematic biology, particularly in scenarios with low mutation rates or limited data.

Summary updated

Abstract

We study distorted metrics on binary trees in the context of phylogenetic reconstruction. Given a binary tree $T$ on $n$ leaves with a path metric $d$, consider the pairwise distances $\{d(u,v)\}$ between leaves. It is well known that these determine the tree and the $d$ length of all edges. Here we consider distortions $\d$ of $d$ such that for all leaves $u$ and $v$ it holds that $|d(u,v) - \d(u,v)| < f/2$ if either $d(u,v) < M$ or $\d(u,v) < M$, where $d$ satisfies $f \leq d(e) \leq g$ for all edges $e$. Given such distortions we show how to reconstruct in polynomial time a forest $T_1,...,T_α$ such that the true tree $T$ may be obtained from that forest by adding $α-1$ edges and $α-1 \leq 2^{-Ω(M/g)} n$. Metric distortions arise naturally in phylogeny, where $d(u,v)$ is defined by the log-det of a covariance matrix associated with $u$ and $v$. of a covariance matrix associated with $u$ and $v$. When $u$ and $v$ are ``far'', the entries of the covariance matrix are small and therefore $\d(u,v)$, which is defined by log-det of an associated empirical-correlation matrix may be a bad estimate of $d(u,v)$ even if the correlation matrix is ``close'' to the covariance matrix. Our metric results are used in order to show how to reconstruct phylogenetic forests with small number of trees from sequences of length logarithmic in the size of the tree. Our method also yields an independent proof that phylogenetic trees can be reconstructed in polynomial time from sequences of polynomial length under the standard assumptions in phylogeny. Both the metric result and its applications to phylogeny are almost tight.
BibTeX
@article{mossel2007distorted,
  author = {Elchanan Mossel},
  title = {{Distorted metrics on trees and phylogenetic forests}},
  journal = {IEEE ACM Trans. Comput. Biol. Bioinform.},
  year = {2007},
  doi = {10.1109/tcbb.2007.1010},
}

Loading related content...

Figure