An efficient algorithm for sequence comparison with block reversals

S. Muthukrishnan; S. Cenk Sahinalp

doi:10.1016/j.tcs.2003.05.005

An efficient algorithm for sequence comparison with block reversals

S. Muthukrishnan, S. Cenk Sahinalp

Research output: Contribution to journal › Conference article › peer-review

Abstract

Given two sequences X and Y that are strings over some alphabet set, we consider the distance d(X,Y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform X to Y (or vice versa). The operations are required to be disjoint. This is the "simplest" sequence comparison problem we know of that allows natural block edit operations. Block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. We present an algorithm for exactly computing the distance d(X,Y); it takes time O(|X|log ²|X|), and hence, is near-linear. Trivial approach takes quadratic time.

Original language	English (US)
Pages (from-to)	95-101
Number of pages	7
Journal	Theoretical Computer Science
Volume	321
Issue number	1
DOIs	https://doi.org/10.1016/j.tcs.2003.05.005
State	Published - Jun 16 2004
Event	Latin American Theoretical Informatics - Cancun, Mexico Duration: Apr 3 2002 → Apr 6 2002

Keywords

Block edit distance
Sequence comparison
String periodicity

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2003.05.005

Cite this

@article{85d044387bf44515ad8e44f8d9061634,

title = "An efficient algorithm for sequence comparison with block reversals",

abstract = "Given two sequences X and Y that are strings over some alphabet set, we consider the distance d(X,Y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform X to Y (or vice versa). The operations are required to be disjoint. This is the {"}simplest{"} sequence comparison problem we know of that allows natural block edit operations. Block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. We present an algorithm for exactly computing the distance d(X,Y); it takes time O(|X|log 2|X|), and hence, is near-linear. Trivial approach takes quadratic time.",

keywords = "Block edit distance, Sequence comparison, String periodicity",

author = "S. Muthukrishnan and Sahinalp, {S. Cenk}",

year = "2004",

month = jun,

day = "16",

doi = "10.1016/j.tcs.2003.05.005",

language = "English (US)",

volume = "321",

pages = "95--101",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

note = "Latin American Theoretical Informatics ; Conference date: 03-04-2002 Through 06-04-2002",

}

TY - JOUR

T1 - An efficient algorithm for sequence comparison with block reversals

AU - Muthukrishnan, S.

AU - Sahinalp, S. Cenk

PY - 2004/6/16

Y1 - 2004/6/16

N2 - Given two sequences X and Y that are strings over some alphabet set, we consider the distance d(X,Y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform X to Y (or vice versa). The operations are required to be disjoint. This is the "simplest" sequence comparison problem we know of that allows natural block edit operations. Block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. We present an algorithm for exactly computing the distance d(X,Y); it takes time O(|X|log 2|X|), and hence, is near-linear. Trivial approach takes quadratic time.

AB - Given two sequences X and Y that are strings over some alphabet set, we consider the distance d(X,Y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform X to Y (or vice versa). The operations are required to be disjoint. This is the "simplest" sequence comparison problem we know of that allows natural block edit operations. Block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. We present an algorithm for exactly computing the distance d(X,Y); it takes time O(|X|log 2|X|), and hence, is near-linear. Trivial approach takes quadratic time.

KW - Block edit distance

KW - Sequence comparison

KW - String periodicity

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

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

U2 - 10.1016/j.tcs.2003.05.005

DO - 10.1016/j.tcs.2003.05.005

M3 - Conference article

AN - SCOPUS:2442543058

SN - 0304-3975

VL - 321

SP - 95

EP - 101

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Latin American Theoretical Informatics

Y2 - 3 April 2002 through 6 April 2002

ER -

An efficient algorithm for sequence comparison with block reversals

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this