Tandem cyclic alignment

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.