A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals
<|reference_start|>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.<|reference_end|>
@article{swenson2024a,
    title={A Simple and Efficient Algorithm for Sorting Signed Permutations by
  Reversals},
    author={Krister M. Swenson},
    journal={arXiv preprint arXiv:2403.20165},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.20165},
    primaryClass={cs.DS}
}