bioRxivGenomicsPreprint
The 2-approximation algorithm of sorting by prefix transposition revisited
Md. Shafiqul Islam, Md. Khaledur RahmaniD, M. Sohel RahmaniD
Abstract
A transposition is an operation that exchanges two adjacent blocks in a permutation. A prefix transposition always moves a prefix of the permutation to another location. In this article, we use a data structure, called the permutation tree, to improve the running time of the best known approximation algorithm (with approximation ratio 2) for sorting a permutation by prefix transpositions. By using the permutation tree, we improve the running time of the 2-approximation algorithm to O(n log n).
Reproducibility ledger
Nobody has reported trying to reproduce this paper yet. Did you replicate an experiment or run the code? Your report saves the next lab a week.
Sign in to file a reproducibility report.
Related papers
- Prefix Block-Interchanges on Binary and Ternary Strings
Md. Khaledur Rahman, M. Sohel Rahman·bioRxiv·Jun 4, 2019
- Rapidly Computing the Phylogenetic Transfer Index
Jakub Truszkowski, Olivier Gascuel, Krister M. Swenson·bioRxiv·Aug 22, 2019
- Linear indexing for all strings under all internal nodes in suffix trees
Anas Al-okaily, Abdelghani Tbakhi·Frontiers in BioinformaticsPeer-reviewed·Sep 4, 2025
- Parallelized calculation of permutation tests
Markus Ekvall, Michael Höhle, Lukas Käll·BioinformaticsPeer-reviewed·Nov 19, 2020
- Recursive Prefix-Free Parsing for Building Big BWTs
Marco Oliva, Travis Gagie, Christina A. Boucher·DCCPeer-reviewed·Mar 1, 2023
- Prefix-Free Parsing for Building Big BWTs
Christina A. Boucher, Travis Gagie, … Taher Mun·Algorithms for Molecular BiologyPeer-reviewed·May 24, 2019