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:
- Local Reconstruction: For each leaf, a small local tree is built using only reliable distances.
- 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.
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