A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals

In 1937, biologists Sturtevant and Tan posed a computational question: transform a chromosome represented by a permutation of genes, into a second permutation, using a minimum-length sequence of reversals, each inverting the order of a contiguous subset of elements.

Solutions to this problem, applied to Drosophila chromosomes, were computed by hand.

The first algorithmic result was a heuristic that was published in 1982.

In the 1990s a more biologically relevant version of the problem, where the elements have signs that are also inverted by a reversal, finally received serious attention by the computer science community.

This effort eventually resulted in the first polynomial time algorithm for Signed Sorting by Reversals.

Since then, a dozen more articles have been dedicated to simplifying the theory and developing algorithms with improved running times.

The current best algorithm, which runs in $O(n \log^2 n / \log\log n)$ time, fails to meet what some consider to be the likely lower bound of $O(n \log n)$.

In this article, we present the first algorithm that runs in $O(n \log n)$ time in the worst case.

The algorithm is fairly simple to implement, and the running time hides very low constants.

;Comment: 25 pages, 6 figures