An efficient algorithm for sequence comparison with block reversals

S. Muthukrishnan, S. Cenk Sahinalp

    Research output: Contribution to journalConference articlepeer-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 2|X|), and hence, is near-linear. Trivial approach takes quadratic time.

    Original languageEnglish (US)
    Pages (from-to)95-101
    Number of pages7
    JournalTheoretical Computer Science
    Volume321
    Issue number1
    DOIs
    StatePublished - Jun 16 2004
    EventLatin American Theoretical Informatics - Cancun, Mexico
    Duration: Apr 3 2002Apr 6 2002

    Keywords

    • Block edit distance
    • Sequence comparison
    • String periodicity

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

    Cite this