@inproceedings{069d119a215c491991626b6b0cb6d467,

title = "An improved 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). 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 improved algorithm for exactly computing the distance d(X, Y); it takes time O(|X| log2 |X|), and hence, is near-linear. Trivial approach takes quadratic time and the best known previous algorithm for this problem takes time Ω(|X| log3 |X|).",

author = "S. Muthukrishnan and Ṣahinalp, {S. Cenk}",

year = "2002",

doi = "10.1007/3-540-45995-2_30",

language = "English (US)",

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

publisher = "Springer Verlag",

pages = "319--325",

editor = "Sergio Rajsbaum",

booktitle = "LATIN 2002",

note = "5th Latin American Symposium on Theoretical Informatics, LATIN 2002 ; Conference date: 03-04-2002 Through 06-04-2002",

}