A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929296183918592 |
|---|---|
| author | Swenson, Krister M. |
| author_facet | Swenson, Krister M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_20165 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals Swenson, Krister M. Data Structures and Algorithms 68Q25, 68P10, 62P10 F.2.2; G.2.1; J.3 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. |
| title | A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals |
| topic | Data Structures and Algorithms 68Q25, 68P10, 62P10 F.2.2; G.2.1; J.3 |
| url | https://arxiv.org/abs/2403.20165 |