%0 Book Section %B Combinatorial Pattern MatchingCombinatorial Pattern Matching %D 1996 %T Fast sorting by reversal %A Berman,Piotr %A Hannenhalli, Sridhar %E Hirschberg,Dan %E Myers,Gene %X 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. %B Combinatorial Pattern MatchingCombinatorial Pattern Matching %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 1075 %P 168 - 185 %8 1996/// %@ 978-3-540-61258-2 %G eng %U http://dx.doi.org/10.1007/3-540-61258-0_14