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

DOI10.1007/S11538-020-00693-3MaRDI QIDQ2299336zbMATH OpenOpenAlexWikidataFDO

Authors Wai-Tong (Louis) Fan, Sebastien Roch

Publication date 21 February 2020

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.05711

ancestral reconstruction insertion/deletions phylogenetics

Abstract: In evolutionary biology, the speciation history of living organisms is represented graphically by a phylogeny, that is, a rooted tree whose leaves correspond to current species and branchings indicate past speciation events. Phylogenies are commonly estimated from molecular sequences, such as DNA sequences, collected from the species of interest. At a high level, the idea behind this inference is simple: the further apart in the Tree of Life are two species, the greater is the number of mutations to have accumulated in their genomes since their most recent common ancestor. In order to obtain accurate estimates in phylogenetic analyses, it is standard practice to employ statistical approaches based on stochastic models of sequence evolution on a tree. For tractability, such models necessarily make simplifying assumptions about the evolutionary mechanisms involved. In particular, commonly omitted are insertions and deletions of nucleotides -- also known as indels. Properly accounting for indels in statistical phylogenetic analyses remains a major challenge in computational evolutionary biology. Here we consider the problem of reconstructing ancestral sequences on a known phylogeny in a model of sequence evolution incorporating nucleotide substitutions, insertions and deletions, specifically the classical TKF91 process. We focus on the case of dense phylogenies of bounded height, which we refer to as the taxon-rich setting, where statistical consistency is achievable. We give the first polynomial-time ancestral reconstruction algorithm with provable guarantees under constant rates of mutation. Our algorithm succeeds when the phylogeny satisfies the "big bang" condition, a necessary and sufficient condition for statistical consistency in this context.

Review text

In the present paper, the authors are interested in statistically consistent estimators for the ASR problem under the TKF91 process in the taxon-rich setting, which differs from the ``solvability results in [\textit{A. Andoni} et al., Stochastic Processes Appl. 122, No. 12, 3852--3874 (2012; Zbl 1250.92034)]. In fact, an ASR statistical consistency result in this context is already implied by the general results of [\textit{W.-T. Fan} and \textit{S. Roch}, Electron. J. Probab. 23, Paper No. 47, 24 p. (2018; Zbl 1410.60074)]. More concrete they are considered the ancestral sequence reconstruction (ASR) problem in the taxon-rich context for the TKF91 process. It has been known from previous work [Zbl 1410.60074, Theorem 1] that the Big Bang condition is necessary for the existence of consistent estimators. In this paper, the authors design the first estimator which is not only consistent but also explicit and computationally tractable. They ancestral reconstruction algorithm involves two steps: first is estimated the length of the ancestral sequence and then are estimated the nucleotides conditioned on the sequence length. The novel observation that leads to the design of authors estimator is a new constructive proof of initial-state identifiability, formulated in Lemma 2, which says that one can explicitly invert the mapping from the root sequence to the distribution of the leaf sequences. This is nontrivial for evolutionary models with indels. This estimator is computationally efficient in the sense that the number of arithmetic operations required scales like a polynomial in the size of the input data. Indeed the length estimator is linear in the number of input sequences and the matrix manipulations in the sequence estimator are polynomial in the length of the longest input sequence.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2299336)