Fast sorting by reversal

Piotr Berman, Sridhar Hannenhalli

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

    95 Scopus citations


    Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n4) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n2α(n)) implementation of the algorithm where a is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings
    EditorsGene Myers, Dan Hirschberg
    PublisherSpringer Verlag
    Number of pages18
    ISBN (Print)3540612580, 9783540612582
    StatePublished - Jan 1 1996
    Event7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 - Laguna Beach, United States
    Duration: Jun 10 1996Jun 12 1996

    Publication series

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


    Other7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996
    Country/TerritoryUnited States
    CityLaguna Beach

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • Computer Science(all)


    Dive into the research topics of 'Fast sorting by reversal'. Together they form a unique fingerprint.

    Cite this