Tandem cyclic alignment

Gary Benson

doi:10.1007/3-540-48194-x_10

Tandem cyclic alignment

Gary Benson

Icahn School of Medicine at Mount Sinai

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

We present a solution for the following problem. Given two sequences X = x₁x₂ … x_n and Y = y₁y₂ … y_m, n ≤ m, find the best scoring alignment of X′ = X^k[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, X^k[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.

Original language	English
Title of host publication	Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings
Editors	Amihood Amir, Amihood Amir, Gad M. Landau, Gad M. Landau
Publisher	Springer Verlag
Pages	118-130
Number of pages	13
ISBN (Print)	3540422714, 9783540422716
DOIs	https://doi.org/10.1007/3-540-48194-x_10
State	Published - 2001
Event	12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001 - Jerusalem, Israel Duration: 1 Jul 2001 → 4 Jul 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2089
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001
Country/Territory	Israel
City	Jerusalem
Period	1/07/01 → 4/07/01

Access to Document

10.1007/3-540-48194-x_10

Cite this

Benson, G. (2001). Tandem cyclic alignment. In A. Amir, A. Amir, G. M. Landau, & G. M. Landau (Eds.), Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings (pp. 118-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2089). Springer Verlag. https://doi.org/10.1007/3-540-48194-x_10

@inproceedings{004a9df389864120b5b22294665c0b45,

title = "Tandem cyclic alignment",

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, 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.",

author = "Gary Benson",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001 ; Conference date: 01-07-2001 Through 04-07-2001",

year = "2001",

doi = "10.1007/3-540-48194-x_10",

language = "English",

isbn = "3540422714",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "118--130",

editor = "Amihood Amir and Amihood Amir and Landau, {Gad M.} and Landau, {Gad M.}",

booktitle = "Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings",

address = "Germany",

}

Benson, G 2001, Tandem cyclic alignment. in A Amir, A Amir, GM Landau & GM Landau (eds), Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2089, Springer Verlag, pp. 118-130, 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001, Jerusalem, Israel, 1/07/01. https://doi.org/10.1007/3-540-48194-x_10

Tandem cyclic alignment. / Benson, Gary.
Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings. ed. / Amihood Amir; Amihood Amir; Gad M. Landau; Gad M. Landau. Springer Verlag, 2001. p. 118-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2089).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 - 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 -

Tandem cyclic alignment

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this