An Asymmetric Alignment Algorithm for Estimating Ancestor-Descendant Edit Distance for Tandem Repeats

Abstract

Tandem repeats are repetitive structures present in some DNA sequences, consisting of many repeated copies of a single motif. They can serve as important markers for phylogenetic and population genetic studies, due to the high polymorphism in the number of motif copies as well as variations in the motif. The first step in using tandem repeats for phylogenetic studies is to estimate the evolutionary distance between a pair D₁ and D₂ of tandem repeat sequences with homologous motifs. This problem can be broken into two sub-problems: 1) Construct the most recent common ancestor of the sequences. 2) Calculate the evolutionary distance between each sequence and the hypothesised common ancestor. We present an algorithm that estimates the solution to the second problem. This takes the form of an asymmetric alignment algorithm to estimate the evolutionary distance between two tandem repeat sequences A and D, where D is assumed to have descended from A, under a model that allows block duplication, deletion, and variant substitution. The algorithm is asymmetric in the sense that the two input sequences A and D play different roles in the calculations, reflecting the assumption that D descends from A. Our model assumes static motif boundaries, meaning that motif duplication and deletion events must respect the motif boundaries. The algorithm may also be applied without modification to more complex repetitive structures with two or more motifs, such as nested tandem repeats.