An improved algorithm for sequence comparison with block reversals

S. Muthukrishnan, S. Cenk Ṣahinalp

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

    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
    DOIs
    StatePublished - 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
    Country/TerritoryMexico
    CityCancun
    Period4/3/024/6/02

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'An improved algorithm for sequence comparison with block reversals'. Together they form a unique fingerprint.

    Cite this