Tandem cyclic alignment

Gary Benson

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We present a solution for the following problem. Given two sequences X=x1x2⋯xn and Y=y1y2⋯ym, n≤m, find the best scoring alignment of X′=Xk[i] vs. Y over all possible pairs (k,i), for k=1,2,... and 1≤i≤n, where X[i] is the cyclic permutation of X starting at xi, Xk[i] is the concatenation of k complete copies of X[i] (k tandem copies), and the alignment must include all of Y and all of X′. Our algorithm allows any alignment scoring scheme with additive gap costs and uses O(nmlogn) time and O(nm) space. We use it to identify related tandem repeats in the C. elegans genome as part of the development of a multi-genome database of tandem repeats.

Original languageEnglish
Pages (from-to)124-133
Number of pages10
JournalDiscrete Applied Mathematics
Volume146
Issue number2
DOIs
StatePublished - 1 Mar 2005
Externally publishedYes

Keywords

  • Cyclic alignment
  • Tandem repeats
  • Wraparound dynamic programming

Fingerprint

Dive into the research topics of 'Tandem cyclic alignment'. Together they form a unique fingerprint.

Cite this