For a permutation sorting, an algorithm based on the circular inversions of the permutation is proposed. Some its applications in molecular biology and in the theory of permutation groups are pointed.
Download file
Counter downloads: 313
- Title Circular inversions of permutations and their use in sorting problems
- Headline Circular inversions of permutations and their use in sorting problems
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(31)
- Date:
- DOI
Keywords
diameter of the permutation group, sorting linear and circular permutations, circular inversions of permutations, inversions, диаметр группы подстановок, сортировка линейных и круговых перестановок, инверсии и круговые инверсии перестановокAuthors
References
Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы // Кибернетика. 1971. №5. С. 33-39.
Глушков В. М. О полноте систем операций в электронных вычислительных машинах // Кибернетика. 1968. №2. С. 1-5.
Зубов А. Ю. О некоторых классах экстремальных ориентированных графов // Прикладная дискретная математика. 2015. №4(30). С. 45-50.
Зубов А. Ю. О представлении подстановок в виде произведений транспозиции и полного цикла // Фундаментальная и прикладная математика. 2009. Т. 15. Вып. 1. С. 31-52.
Зубов А. Ю. О диаметре группы Sn относительно системы образующих, состоящей из полного цикла и транспозиции // Труды по дискретной математике. Т. 2. М.: ТВП, 1998. С.112-150.
Глухов М. М., Погорелов Б. А. О некоторых применениях групп в криптографии // Материалы конф. «Математика и безопасность информационных технологий», МГУ, 28-29 октября 2004г. М.: МЦНМО, 2005. С. 19-31.
Глухов М.М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих // Математические вопросы кибернетики. Вып. 8. М.: Наука, 1999. С. 5-32.
Labarre A. Lower bounding edit distances between permutations // SIAM J. Discr. Math. 2013. Vol.27. No. 3. P. 1410-1428.
Bulteau L., Fertin G., and Rusu I. Sorting by transpositions is difficult // SIAM J. Discr. Math. 2012. Vol.26. No. 12. P. 1148-1180.
Feng J. and Zhu D. Faster algorithms for sorting by transpositions and sorting by block interchanges // ACM Transactions on Algorithms (TALG). 2007. Vol. 3. No. 3. Article No. 25.
Hartman T. and Shamir R. A simpler and faster 1.5-approximation algorithm for sorting by transpositions // Information and Computation. 2006. Vol. 204. P. 275-290.
Cranston D., Sudborough I. H., and West D. B. Short proofs for cat-and-paste sorting of permutations // Discr. Math. 2007. Vol.307. Iss.22. P.2866-2870.
Lin Y. C., Lu C. L., Chang H.-Y., and Tang C. Y. An efficient algorithm for sorting by block-interchanges and its application to the evolution of Vibrio Species // J. Computational Biology. 2005. Vol. 12. No. 1. P. 102-112.
Eriksen N. Combinatorial methods in comparative genomics. Doctoral dissertation. Royal Institute of Technology. Stockholm, 2003. 138 p.
Dias U. and Meidanis J. Sorting by prefix transpositions // String Processing and Information Retrieval. Springer, 2002. P. 65-76.
Eriksson H., Eriksson K., Karlander J., et al. Sorting a bridge hand // Discr. Math. 2001. Vol. 241. No. 1. P. 289-300.
Caprara A. Sorting permutations by reversals and Eulerian cycle decompositions // SIAM J. Discr. Math. 1999. No. 12. P. 91-110.
Heath L. S. and Vergara J. P. C. Sorting by short block-moves // Technical Report TR-98-03. Virginia Tech. Department of Computer Science, Feb. 1998.
Pevzner P. A. and Waterman M. S. Open combinatorial problems in computational molecular biology // Proc. 3rd Israel Symposium on the Theory of Computing and Systems. 1995. P. 158-173.
Kececioglu J. D. and Ravi R. Of mice and men: algorithms for evolutionary distances between genomes with translocation // Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA, USA, 1996. P. 604-613.
Christie D. A. Sorting permutations by block-interchanges // Inform. Proc. Lett. 1996. Vol. 60. No.4. P. 165-169.
Christie D. A. Genome rearrangement problems. Submitted for the degree of Doctor of Philosophy to the University of Glasgow. Glasgow, 1998. 165 p.
Bafna V. and Pevzner P. A. Genome rearrangement and sorting by reversals // SIAM J. Comput. 1996. Vol.25. No. 2. P. 272-289.
Bafna V. and Pevzner P. A. Sorting by transpositions // SIAM J. Discr. Math. 1998. Vol. 11. No. 2. P. 224-240.
Dobzhansky T. and Sturtevant A. H. Inversions in the chromosomes of drosophila pseudoobscura // Genetics. 1938. Vol. 23. P. 28-64.
Aigner M. and West D. B. Sorting by insertion of leading elements // J. Combinatorial Theory. Ser.A. 1987. Vol.45. No.2. P.306-309.
Circular inversions of permutations and their use in sorting problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 1(31).