Advertisement
Published in:
2010 | OriginalPaper | Chapter
An Algorithm to Solve the Motif Alignment Problem for Approximate Nested Tandem Repeats
Authors : Atheer A. Matroud, Michael D. Hendy, Christopher P. Tuffley
Published in: Comparative Genomics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
An
approximate nested tandem repeat
(NTR) in a string
T
is a complex repetitive structure consisting of many approximate copies of two substrings
x
and
X
(“motifs”) interspersed with one another. NTRs have been found in real DNA sequences and are expected to have applications for evolutionary studies, both as a tool to understand concerted evolution, and as a potential marker in population studies.
In this paper we describe software tools developed for database searches for NTRs. After a first program
NTRFinder
identifies putative NTR motifs, a confirmation step requires the application of the alignment of the putative NTR against exact NTRs built from the putative template motifs
x
and
X
. In this paper we describe an algorithm to solve this alignment problem in
O
(|
T|(|
x| + |
X|))
space and time. Our alignment algorithm is based on Fischetti et al.’s wrap-around dynamic programming.