An improved algorithm for sequence comparison with block reversals

Shan Muthukrishnan, S. Cenk Ṣahinalp

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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

Original languageEnglish (US)
Title of host publicationLATIN 2002
Subtitle of host publicationTheoretical Informatics - 5th Latin American Symposium, Proceedings
EditorsSergio Rajsbaum
PublisherSpringer Verlag
Pages319-325
Number of pages7
ISBN (Electronic)3540434003, 9783540434009
StatePublished - Jan 1 2002
Event5th Latin American Symposium on Theoretical Informatics, LATIN 2002 - Cancun, Mexico
Duration: Apr 3 2002Apr 6 2002

Publication series

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

Other

Other5th Latin American Symposium on Theoretical Informatics, LATIN 2002
CountryMexico
CityCancun
Period4/3/024/6/02

Fingerprint

Sequence Comparison
Reversal
Music
Replacement
Genomics
Trivial
Strings
Transform
Computing

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Muthukrishnan, S., & Ṣahinalp, S. C. (2002). An improved algorithm for sequence comparison with block reversals. In S. Rajsbaum (Ed.), LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings (pp. 319-325). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2286). Springer Verlag.
Muthukrishnan, Shan ; Ṣahinalp, S. Cenk. / An improved algorithm for sequence comparison with block reversals. LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings. editor / Sergio Rajsbaum. Springer Verlag, 2002. pp. 319-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cf321c14ecdc4c5491dd5f3b1fd06728,
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 = "Shan Muthukrishnan and Ṣahinalp, {S. Cenk}",
year = "2002",
month = "1",
day = "1",
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",
address = "Germany",

}

Muthukrishnan, S & Ṣahinalp, SC 2002, An improved algorithm for sequence comparison with block reversals. in S Rajsbaum (ed.), LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2286, Springer Verlag, pp. 319-325, 5th Latin American Symposium on Theoretical Informatics, LATIN 2002, Cancun, Mexico, 4/3/02.

An improved algorithm for sequence comparison with block reversals. / Muthukrishnan, Shan; Ṣahinalp, S. Cenk.

LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings. ed. / Sergio Rajsbaum. Springer Verlag, 2002. p. 319-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2286).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An improved algorithm for sequence comparison with block reversals

AU - Muthukrishnan, Shan

AU - Ṣahinalp, S. Cenk

PY - 2002/1/1

Y1 - 2002/1/1

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:84937412871

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 319

EP - 325

BT - LATIN 2002

A2 - Rajsbaum, Sergio

PB - Springer Verlag

ER -

Muthukrishnan S, Ṣahinalp SC. An improved algorithm for sequence comparison with block reversals. In Rajsbaum S, editor, LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings. Springer Verlag. 2002. p. 319-325. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).