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

• Published in: IEEE/ACM transactions on computational biology and bioinformatics 2022-07, Vol.19 (4), p.2080-2091
• Main Authors: Matroud, Atheer, Tuffley, Christopher, Hendy, Michael
• Format: Article
• Language: English
• Subjects: Algorithms; Alignment; Approximation algorithms; Asymmetry; Boundaries; Computational modeling; Deletion; Deoxyribonucleic acid; DNA; dynamic programming; Evolution; Evolutionary algorithms; Gene polymorphism; Gene sequencing; Heuristic algorithms; History; Homology; nested tandem repeat; Nucleotide sequence; Periodic structures; Phylogenetics; Phylogeny; Polymorphism; Population genetics; Population studies; Repetitive structures; Reproduction (copying); sequence comparison; tandem repeat
• ISSN: 1545-5963; 1557-9964
• DOI: 10.1109/TCBB.2021.3059239

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_1 D1 and D_2 D2 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 A and D D , where D D is assumed to have descended from A 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 A and D D