An Algorithm to Solve the Motif Alignment Problem for Approximate Nested Tandem Repeats

被引：0

作者：

Matroud, Atheer A. ^{[1
,2
]}

Hendy, Michael D. ^{[1
,2
]}

Tuffley, Christopher P. ^{[2
]}

机构：

[1] Massey Univ, Allan Wilson Ctr Mol Ecol & Evolut, Private Bag 11222, Palmerston North, New Zealand

[2] Massey Univ, Inst Fundamental Sci, Palmerston North, New Zealand

来源：

COMPARATIVE GENOMICS | 2010年 / 6398卷

关键词：

SEQUENCES;

D O I：

暂无

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

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 NTRF inder 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(vertical bar T vertical bar (vertical bar x vertical bar + vertical bar X vertical bar)) space and time. Our alignment algorithm is based on Fischetti et al.'s wrap-around dynamic programming.

引用

页码：188 / +

页数：3