Sequence-Length Requirement of Distance-Based Phylogeny Reconstruction:\n Breaking the Polynomial Barrier

Sébastien Roch

Abstract

We introduce a new distance-based phylogeny reconstruction technique which provably achieves, at sufficiently short branch lengths, a polylogarithmic sequence-length requirement—improving significantly over previous polynomial bounds for distance-based methods. The technique is based on an averaging procedure that implicitly reconstructs ancestral sequences. In the same token, we extend previous results on phase transitions in phylogeny reconstruction to general time-reversible (GTR) models. More precisely, we show that in the so-called Kesten-Stigum zone (a region of the parameter space where ancestral sequences are well approximated by linear combinations of the observed sequences), sequences of length $poly(\log n)$ suffice for reconstruction when branch lengths are discretized, where $n$ is the number of extant species. Our results challenge the conventional wisdom that estimates of evolutionary distances alone carry significantly less information about phylogenies than full sequence datasets.

Introduction

In the field of phylogenetics, reconstructing the "Tree of Life" from the DNA sequences of extant species is a fundamental challenge. Historically, algorithms for this task have fallen into two distinct camps. Distance-based methods, such as Neighbor-Joining, are computationally efficient and simple; they reduce sequence data into a matrix of pairwise evolutionary distances to cluster species. Holistic methods, such as Maximum Likelihood, utilize the full sequence data simultaneously. While statistically powerful, holistic methods are often NP-hard and computationally intensive.

A long-standing "conventional wisdom" suggested a fundamental information gap between these two approaches. It was believed that by reducing sequences to a simple distance matrix, vital information was lost, necessitating sequence lengths ($k$) that grow polynomially with the number of species ($n$)—the so-called Polynomial Barrier. In contrast, holistic methods were known to achieve reconstruction with much shorter, logarithmic sequences ($k = O(\log n)$) under certain conditions. This paper investigates whether this gap is inherent to distance matrices or a limitation of previous algorithmic approaches.

Methodology: Exponential Averaging

The core innovation of this work is a technique termed Exponential Averaging. Rather than treating a distance matrix as a static collection of independent values, this method exploits the underlying correlation structure between distance estimates.

Implicit Ancestral Reconstruction

The algorithm performs a site-wise average of sequences across subtrees. While it does not explicitly reconstruct the DNA of ancestral nodes, this averaging procedure on the sequences is mathematically equivalent to a specific weighted average of the distances themselves. This allows the method to mimic the information-retention properties of ancestral reconstruction within a distance-based framework.

GTR Distance Estimator

To ensure broad applicability, the paper moves beyond simple models to the General Time-Reversible (GTR) model. It utilizes a distance estimator based on the right eigenvector corresponding to the second eigenvalue of the mutation rate matrix. This allows the theoretical guarantees to hold for the complex evolutionary models used in real-world biological research.

Accuracy Amplification

To ensure robustness against noise, the algorithm employs an accuracy amplification step. It probes several levels deep into the tree to compute multiple independent distance estimates, then utilizes a "dense ball" or majority-style procedure to select the most concentrated and reliable value.

Theoretical Framework and Results

The study provides rigorous mathematical proofs based on standard stochastic models of evolution, including the Cavender-Farris-Neyman (CFN) model and the GTR model. The proofs are established for balanced trees and subsequently extended to general topologies.

Breaking the Polynomial Barrier

The primary result is the proof that for species within the Kesten-Stigum zone, a distance-based method can reconstruct the tree with a sequence length of $k = poly(\log n)$. The Kesten-Stigum zone represents a regime where branch lengths are short enough that the signal from the root of the tree is not entirely obscured by mutations at the leaves.

This finding effectively closes the perceived gap between distance-based and holistic methods, proving that distance-based approaches are far more information-efficient than previously assumed. Furthermore, the work extends phase-transition results—previously limited to very simple symmetric models—to the biologically relevant GTR models.

Discussion and Limitations

While this work represents a significant theoretical leap, it identifies specific constraints:

  1. Branch Length Sensitivity: The polylogarithmic efficiency is contingent on being within the Kesten-Stigum zone. If branch lengths are too long, the signal decays, and the polynomial requirement returns.
  2. Discretized Lengths: The current proof requires branch lengths to be multiples of a small unit ($\Delta$), a technical necessity for the combinatorial steps of the proof.
  3. The Path to Optimality: While this paper achieves $poly(\log n)$, it sets the stage for reaching the absolute theoretical limit of $O(\log n)$.

In conclusion, this research demonstrates that distance-based methods do not inherently discard the information necessary for efficient reconstruction. By acknowledging that distances are derived from correlated sequences rather than an abstract oracle, we can bypass the polynomial barrier and achieve high-fidelity reconstruction with significantly less data.

Summary updated

Abstract

We introduce a new distance-based phylogeny reconstruction technique which\nprovably achieves, at sufficiently short branch lengths, a polylogarithmic\nsequence-length requirement -- improving significantly over previous polynomial\nbounds for distance-based methods. The technique is based on an averaging\nprocedure that implicitly reconstructs ancestral sequences.\n In the same token, we extend previous results on phase transitions in\nphylogeny reconstruction to general time-reversible models. More precisely, we\nshow that in the so-called Kesten-Stigum zone (roughly, a region of the\nparameter space where ancestral sequences are well approximated by ``linear\ncombinations'' of the observed sequences) sequences of length $\\poly(\\log n)$\nsuffice for reconstruction when branch lengths are discretized. Here $n$ is the\nnumber of extant species.\n Our results challenge, to some extent, the conventional wisdom that estimates\nof evolutionary distances alone carry significantly less information about\nphylogenies than full sequence datasets.\n
BibTeX
@misc{roch2009sequence,
  author = {Sébastien Roch},
  title = {{Sequence-Length Requirement of Distance-Based Phylogeny Reconstruction:\textbackslash\{\}n Breaking the Polynomial Barrier}},
  year = {2009},
  eprint = {0908.2061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0908.2061},
}

Loading related content...

Figure