Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling

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

Abstract

Ancestral Sequence Reconstruction (ASR) is a fundamental task in evolutionary biology, yet most existing methods struggle with insertions and deletions (indels) due to the computational complexity of maintaining site alignments. This paper introduces the first explicit, polynomial-time algorithm for ASR that is statistically consistent under the TKF91 indel model. By focusing on "taxon-rich" scenarios—where species are densely sampled over a relatively short evolutionary timeframe—the authors demonstrate that the ancestral sequence can be recovered with high probability as the number of sampled species increases.

Introduction

Reconstructing the genetic sequences of extinct ancestors from the DNA of living descendants is a cornerstone of bioinformatics. While substitutions are well-modeled, indels pose a significant challenge because they alter sequence lengths and break site-wise correspondences. The TKF91 process is the standard mathematical model for indels, but until now, no computationally efficient algorithm provided statistical consistency for this model. This work addresses this gap by proposing a method that bypasses the need for error-prone multiple sequence alignments (MSA).

Methods

The proposed algorithm operates in three distinct phases tailored for trees with a fixed maximum height but an increasing number of leaves:

  1. Restriction: To mitigate correlations between closely related species, the algorithm selects a "well-spread" subset of leaves.
  2. Length Estimation: The ancestral sequence length is estimated using a weighted average of descendant sequence lengths.
  3. Sequence Estimation: The core innovation involves inverting the evolutionary process. By treating nucleotide probabilities at the leaves as a system of linear equations and employing a Vandermonde matrix approach, the algorithm solves for the most likely ancestral nucleotide at each position.
Dense taxon sampling over time, showing the increase in leaf nodes within a fixed tree height.

Key Insights and Theoretical Guarantees

The success of the reconstruction relies on the "Big Bang" condition, a combinatorial property requiring the tree to branch rapidly near the root. This rapid early radiation ensures that sufficient independent information is preserved in the descendants to allow for accurate inversion of the evolutionary mapping. The authors prove "constructive identifiability," providing the explicit mathematical framework to perform this inversion using linear algebra.

Illustration of the tree structure and parameters involved in the 'Big Bang' condition and sequence reconstruction.

Key Results

  • Statistical Consistency: The algorithm is proven to be statistically consistent: as the number of sampled species ($k$) grows, the probability of perfect reconstruction approaches 1.
  • Computational Efficiency: The algorithm is computationally tractable, with a running time that scales polynomially with sequence length and the number of species.
  • Error Bounds: Quantitative error bounds are provided, allowing researchers to estimate the data density required for reliable results based on the tree's height and leaf count.

Limitations and Future Work

The current approach assumes a "taxon-rich" environment and utilizes the TKF91 model, which handles single-nucleotide indels. Future work will focus on extending these mathematical principles to "fragment" indel models, where multiple nucleotides are inserted or deleted simultaneously, and testing the algorithm on empirical biological datasets to validate its practical performance.

Summary updated

BibTeX
@article{fan2020statistically,
  author = {Wai-Tong Louis Fan and Sébastien Roch},
  title = {{Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling}},
  journal = {Bulletin},
  year = {2020},
  doi = {10.1007/s11538-020-00693-3},
}
Figure