Document Open Access Logo

Can a permutation be sorted by best short swaps?

Authors Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, Haodi Feng

PDF
Thumbnail PDF

File

LIPIcs.CPM.2018.14.pdf
  • Filesize: 427 kB
  • 12 pages

Document Identifiers

Author Details

Shu Zhang
  • Department of Computer Science and Technology, Shandong University, Jinan, China
Daming Zhu
  • Department of Computer Science and Technology, Shandong University, Jinan, China
Haitao Jiang
  • Department of Computer Science and Technology, Shandong University, Jinan, China
Jingjing Ma
  • Department of Computer Science and Technology, Shandong University, Jinan, China
Jiong Guo
  • Department of Computer Science and Technology, Shandong University, Jinan, China
Haodi Feng
  • Department of Computer Science and Technology, Shandong University, Jinan, China

Cite As Get BibTex

Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng. Can a permutation be sorted by best short swaps?. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CPM.2018.14

Abstract

A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation.
A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
Keywords
  • Algorithm
  • Complexity
  • Short Swap
  • Permutation
  • Reversal

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. Siam Journal on Computing, 25(2):272-289, 1993. Google Scholar
  2. Piotr Berman, Sridhar Hannenhalli, and Marek Karpinski. 1.375-approximation algorithm for sorting by reversals. Lecture Notes in Computer Science, pages 200-210, 2002. Google Scholar
  3. Guillaume Bourque and Pavel A. Pevzner. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Research, 12(1):26-36, 2002. Google Scholar
  4. Alberto Caprara. Sorting permutations by reversals and eulerian cycle decompositions. Siam Journal on Discrete Mathematics, 12(1):91-110, 1999. Google Scholar
  5. Xuerong Feng, Ivan Hal Sudborough, and Enyue Lu. A fast algorithm for sorting by short swap. In Proceeding of the 10th IASTED International Conference on Computational and Systems Biology, pages 62-67, 2006. Google Scholar
  6. Gustavo Rodrigues Galvão and Zanoni Dias. Approximation algorithms for sorting by signed short reversals. In Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, BCB '14, Newport Beach, California, USA, September 20-23, 2014, pages 360-369. ACM, 2014. URL: http://dx.doi.org/10.1145/2649387.2649413.
  7. Gustavo Rodrigues Galvão, Orlando Lee, and Zanoni Dias. Sorting signed permutations by short operations. Algorithms for Molecular Biology, 10(1):1-17, 2015. Google Scholar
  8. Sridhar Hannenhalli. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Journal of the Acm, 46(1):1-27, 1999. Google Scholar
  9. L. S. Heath and J. P. Vergara. Sorting by short swaps. Journal of Computational Biology A Journal of Computational Molecular Cell Biology, 10(5):775-89, 2003. Google Scholar
  10. Mark R. Jerrum. The complexity of finding minimum-length generator sequences. In Colloquium on Automata, Languages and Programming, pages 270-280, 1984. Google Scholar
  11. Haim Kaplan, Ron Shamir, and Robert E. Tarjan. A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. Society for Industrial and Applied Mathematics, 1999. Google Scholar
  12. J. Kececioglu and D. Sankoff. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica, 13(1-2):180-210, 1995. Google Scholar
  13. P Pevzner and G Tesler. Genome rearrangements in mammalian evolution: lessons from human and mouse genomes. Genome Research, 13(1):37-45, 2003. Google Scholar
  14. G. P. Pradhan and P. V. Prasad. Evaluation of wheat chromosome translocation lines for high temperature stress tolerance at grain filling stage. Plos One, 10(2):1-20, 2015. Google Scholar
  15. D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B F Lang, and R. Cedergren. Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proceedings of the National Academy of Sciences of the United States of America, 89(14):6575-6579, 1992. Google Scholar
  16. G. A. Watterson, W. J. Ewens, T. E. Hall, and A. Morgan. The chromosome inversion problem. Journal of Theoretical Biology, 99(1):1-7, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact