TY - GEN

T1 - Tandem cyclic alignment

AU - Benson, Gary

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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, 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 runs in time O(nm log n). We have used it to identify related tandem repeats in the C. elegans genome as part of the development of a multi-genome database of tandem repeats.

AB - 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, 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 runs in time O(nm log n). We have used it to identify related tandem repeats in the C. elegans genome as part of the development of a multi-genome database of tandem repeats.

UR - http://www.scopus.com/inward/record.url?scp=84956985076&partnerID=8YFLogxK

U2 - 10.1007/3-540-48194-x_10

DO - 10.1007/3-540-48194-x_10

M3 - Conference contribution

AN - SCOPUS:84956985076

SN - 3540422714

SN - 9783540422716

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 118

EP - 130

BT - Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings

A2 - Amir, Amihood

A2 - Amir, Amihood

A2 - Landau, Gad M.

A2 - Landau, Gad M.

PB - Springer Verlag

T2 - 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001

Y2 - 1 July 2001 through 4 July 2001

ER -