@inbook {38257, title = {Fast sorting by reversal}, booktitle = {Combinatorial Pattern MatchingCombinatorial Pattern Matching}, series = {Lecture Notes in Computer Science}, volume = {1075}, year = {1996}, publisher = {Springer Berlin / Heidelberg}, organization = {Springer Berlin / Heidelberg}, abstract = {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.}, isbn = {978-3-540-61258-2}, author = {Berman, Piotr and Sridhar Hannenhalli}, editor = {Hirschberg, Dan and Myers, Gene} }