Impossibility of Consistent Distance Estimation from Sequence Lengths Under the TKF91 Model

Wai-Tong Louis Fan, Brandon Legried, Sébastien RochBulletin 2020 · DOI · arXiv

Abstract

In the field of phylogenetics, the reconstruction of evolutionary history typically relies on sequence alignments and substitution models. However, the computational complexity of alignment has led to interest in "alignment-free" methods, including those utilizing sequence lengths alone. This paper provides a rigorous mathematical proof that consistent distance estimation from sequence lengths is impossible under the Thorne-Kishino-Felsenstein (TKF91) model. While sequence lengths are theoretically identifiable—meaning every tree produces a unique distribution of lengths—the authors demonstrate that the statistical noise from insertions and deletions grows faster than the signal of evolutionary time. By calculating the Total Variation (TV) distance between length distributions, the study proves that no estimator can achieve consistency as sequence lengths approach infinity.

Introduction

Phylogenetic inference is the cornerstone of understanding biological relationships across the tree of life. Traditional methods rely on sequence alignment to identify homologous sites and quantify substitutions. Because alignment is computationally expensive and often error-prone, researchers have sought alternative "alignment-free" approaches. One such proposal involves using only the lengths of sequences to estimate evolutionary distances.

Under the TKF91 model—a foundational birth-death process for sequence evolution—it was previously established that sequence lengths are "identifiable." This theoretical property suggests that, given an infinite number of independent observations, one could uniquely determine the evolutionary distance. However, this paper addresses a more practical statistical hurdle: consistency. The authors investigate whether a single, increasingly long sequence provides enough information to distinguish between different evolutionary distances.

The TKF91 Model and the Asymptotic Regime

The TKF91 model treats sequence evolution as a stochastic process where individual sites are added (inserted) at rate $\lambda$ and removed (deleted) at rate $\mu$. A unique feature of this model is the "immortal link," a permanent starting point that prevents the sequence from disappearing entirely.

The authors focus their analysis on the "asymptotic regime" where the insertion rate $\lambda$ approaches the deletion rate $\mu$. In this state, the expected length of the sequence grows toward infinity. This regime is critical because it represents the limit where one would expect the most "data" to be available for estimation.

The Signal-to-Noise Paradox

The core of the paper’s argument lies in the relationship between the "signal" (the change in average sequence length over time) and the "noise" (the variance of the sequence length distribution).

In many statistical models, increasing the amount of data (in this case, sequence length) reduces the relative error of an estimate. However, the authors show that the TKF91 model suffers from a "Signal-to-Noise Trap":

  1. Constant Signal: The difference in expected sequence lengths between two distinct evolutionary distances remains relatively small, specifically $O(1)$.
  2. Exploding Noise: The standard deviation of the sequence lengths grows at a rate of $O(1/\sqrt{1-\lambda})$.

As $\lambda$ approaches $\mu$, the variance of the distribution blows up, completely burying the signal of time. Even though the distributions are technically unique (identifiable), they overlap so significantly that they become statistically indistinguishable.

Mathematical Proof of Impossibility

To formalize this, the authors employ the Berry-Esseen Theorem, a version of the Central Limit Theorem that provides uniform bounds on how closely a distribution matches a Gaussian (normal) distribution. They use this to calculate the Total Variation (TV) distance between the probability distributions of sequence lengths at two different evolutionary heights.

Their primary result, Theorem 1, proves that the TV distance between these distributions is strictly less than 1, even in the limit of infinitely long sequences. In statistical terms, if the TV distance is less than 1, there is a non-vanishing probability of error for any possible estimator. Therefore, a "consistent estimator"—one that is guaranteed to converge on the true evolutionary distance as more data is collected—is mathematically impossible using sequence lengths alone under this model.

Conclusion and Implications

This research highlights a critical distinction in statistical phylogenetics: identifiability does not guarantee consistency. While sequence lengths contain a theoretical signature of the past, that signature is too faint to be recovered from the noise of the insertion-deletion process.

These findings have significant implications for the development of alignment-free phylogenetic tools. While the proof is specific to the TKF91 model, the technical approach—using the Berry-Esseen theorem to demonstrate distribution overlap—provides a framework for testing the consistency of other methods, such as those based on $k$-mer frequencies. Future work may determine if more complex models, such as the TKF92 model which allows for block insertions and deletions, suffer from similar fundamental limitations.

Summary updated

BibTeX
@article{fan2020impossibility,
  author = {Wai-Tong Louis Fan and Brandon Legried and Sébastien Roch},
  title = {{Impossibility of Consistent Distance Estimation from Sequence Lengths Under the TKF91 Model}},
  journal = {Bulletin},
  year = {2020},
  doi = {10.1007/s11538-020-00801-3},
}

Loading related content...

Figure