Abstract
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 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.