@inproceedings{dcba0d2f351b49709768612a3288de03,
title = "Fast sorting by reversal",
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(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.",
author = "Piotr Berman and Sridhar Hannenhalli",
year = "1996",
month = jan,
day = "1",
doi = "10.1007/3-540-61258-0_14",
language = "English (US)",
isbn = "3540612580",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "168--185",
editor = "Gene Myers and Dan Hirschberg",
booktitle = "Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings",
address = "Germany",
note = "7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 ; Conference date: 10-06-1996 Through 12-06-1996",
}