Fast sorting by reversal

TitleFast sorting by reversal
Publication TypeBook Chapters
Year of Publication1996
AuthorsBerman P, Hannenhalli S
EditorHirschberg D, Myers G
Book TitleCombinatorial Pattern MatchingCombinatorial Pattern Matching
Series TitleLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-61258-2

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(n 4 ) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n 2 (n)) implementation of the algorithm where is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.