@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}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 5th Latin American Symposium on Theoretical Informatics, LATIN 2002 ; Conference date: 03-04-2002 Through 06-04-2002",
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",
}