Title: Efficient and consistent inference of ancestral sequences in an evolutionary model with insertions and deletions under dense taxon sampling,
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.