title: Sorting signed permutations by inversions in O(nlogn) time.
abstract: 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(nlogn) time. In this article, we present a qualified answer to this question, by providing two new sorting algorithms, a simple and fast randomized algorithm and a deterministic refinement. The deterministic algorithm runs in time O(nlogn + kn), where k is a data-dependent parameter. We provide the results of extensive experiments showing that both the average and the standard deviation for k are small constants, independent of the size of the permutation. We conclude (but do not prove) that almost all signed permutations can be sorted by inversions in O(nlogn) time.
authors.affiliation: Laboratory for Computational Biology and Bioinformatics, EPFL (Ecole Polytechnique Fédérale de Lausanne), Lausanne, Switzerland. akswenson@uottawa.ca
authors.forename: Krister M
authors.initials: KM
authors.lastname: Swenson
authors.forename: Vaibhav
authors.initials: V
authors.lastname: Rajan
authors.forename: Yu
authors.initials: Y
authors.lastname: Lin
authors.forename: Bernard M E
authors.initials: BM
authors.lastname: Moret
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D007446:Chromosome Inversion / Q000235:genetics*; D019295:Computational Biology / Q000379:methods*; D013997:Time Factors