Fast sorting by reversal
Title | Fast sorting by reversal |
Publication Type | Book Chapters |
Year of Publication | 1996 |
Authors | Berman P, Hannenhalli S |
Editor | Hirschberg D, Myers G |
Book Title | Combinatorial Pattern MatchingCombinatorial Pattern Matching |
Series Title | Lecture Notes in Computer Science |
Volume | 1075 |
Publisher | Springer Berlin / Heidelberg |
ISBN Number | 978-3-540-61258-2 |
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. |