## Sorting signed permutations by inversions in O(nlogn) time

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inversions, improved algorithms have been designed, culminating with an optimal linear-time algorithm for computing the inversion distance and a subquadratic algorithm for providing a shortest sequence of inversions-also known as sorting by inversions. Remaining open was the question of whether sorting by inversions Could be done in O(n log n) time.

Published in:
Proc. 13th Int'l Conf. on Research in Comput. Molecular Biol. RECOMB'09, 386-399
Presented at:
13th Int'l Conf. on Research in Comput. Molecular Biol. RECOMB'09
Year:
2009
Publisher:
Berlin, Springer
Keywords:
Laboratories: