Geodesic
Circular inversions of permutations and their use in sorting problems
Prikladnaâ diskretnaâ matematika, no. 1 (2016), pp. 13-31.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : inversions, circular inversions of permutations
Keywords: sorting linear and circular permutations, diameter of the permutation group. 
@article{PDM_2016_1_a1,
     author = {A. Yu. Zubov},
     title = {Circular inversions of permutations and their use in sorting problems},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {13--31},
     publisher = {mathdoc},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_1_a1/}
}
TY  - JOUR
AU  - A. Yu. Zubov
TI  - Circular inversions of permutations and their use in sorting problems
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 13
EP  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_1_a1/
LA  - ru
ID  - PDM_2016_1_a1
ER  - 
%0 Journal Article
%A A. Yu. Zubov
%T Circular inversions of permutations and their use in sorting problems
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 13-31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_1_a1/
%G ru
%F PDM_2016_1_a1
A. Yu. Zubov. Circular inversions of permutations and their use in sorting problems. Prikladnaâ diskretnaâ matematika, no. 1 (2016), pp. 13-31. http://geodesic.mathdoc.fr/item/PDM_2016_1_a1/

[1] Dobzhansky T., Sturtevant A. H., “Inversions in the chromosomes of drosophila pseudoobscura”, Genetics, 23 (1938), 28–64

[2] Aigner M., West D. B., “Sorting by insertion of leading elements”, J. Combinatorial Theory. Ser. A, 45:2 (1987), 306–309 | DOI | MR | Zbl

[3] Bafna V., Pevzner P. A., “Genome rearrangement and sorting by reversals”, SIAM J. Comput., 25:2 (1996), 272–289 | DOI | MR | Zbl

[4] Bafna V., Pevzner P. A., “Sorting by transpositions”, SIAM J. Discr. Math., 11:2 (1998), 224–240 | DOI | MR | Zbl

[5] Christie D. A., “Sorting permutations by block-interchanges”, Inform. Proc. Lett., 60:4 (1996), 165–169 | DOI | MR

[6] Christie D. A., Genome rearrangement problems, Submitted for the degree of Doctor of Philosophy to the University of Glasgow, Glasgow, 1998, 165 pp.

[7] Kececioglu J. D., 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, 604–613 | MR

[8] Pevzner P. A., Waterman M. S., “Open combinatorial problems in computational molecular biology”, Proc. 3rd Israel Symposium on the Theory of Computing and Systems, 1995, 158–173 | DOI | MR

[9] Heath L. S., Vergara J. P. C., Sorting by short block-moves, Technical Report TR-98-03, Virginia Tech. Department of Computer Science, Feb. 1998

[10] Caprara A., “Sorting permutations by reversals and Eulerian cycle decompositions”, SIAM J. Discr. Math., 12 (1999), 91–110 | DOI | MR | Zbl

[11] Eriksson H., Eriksson K., Karlander J., et al., “Sorting a bridge hand”, Discr. Math., 241:1 (2001), 289–300 | DOI | MR | Zbl

[12] Dias U., Meidanis J., “Sorting by prefix transpositions”, String Processing and Information Retrieval, Springer, 2002, 65–76 | DOI

[13] Eriksen N., Combinatorial methods in comparative genomics, Doctoral dissertation, Royal Institute of Technology, Stockholm, 2003, 138 pp.

[14] Lin Y. C., Lu C. L., Chang H.-Y., Tang C. Y., “An efficient algorithm for sorting by block-interchanges and its application to the evolution of Vibrio Species”, J. Computational Biology, 12:1 (2005), 102–112 | DOI

[15] Cranston D., Sudborough I. H., West D. B., “Short proofs for cat-and-paste sorting of permutations”, Discr. Math., 307:22 (2007), 2866–2870 | DOI | MR | Zbl

[16] Hartman T., Shamir R., “A simpler and faster 1.5-approximation algorithm for sorting by transpositions”, Information and Computation, 204 (2006), 275–290 | DOI | MR | Zbl

[17] Feng J., Zhu D., “Faster algorithms for sorting by transpositions and sorting by block interchanges”, ACM Transactions on Algorithms (TALG), 3:3 (2007), Article No. 25, 14 pp. | MR | Zbl

[18] Bulteau L., Fertin G., Rusu I., “Sorting by transpositions is difficult”, SIAM J. Discr. Math., 26:12 (2012), 1148–1180 | DOI | MR | Zbl

[19] Labarre A., “Lower bounding edit distances between permutations”, SIAM J. Discr. Math., 27:3 (2013), 1410–1428 | DOI | MR | Zbl

[20] Glukhov M. M., Zubov A. Yu., “On the length of the symmetric and alternating substitutions groups in different systems of generators”, Matematicheskie Voprosy Kibernetiki, 8, Nauka Publ., Moscow, 1999, 5–32 (in Russian) | MR

[21] Glukhov M. M., Pogorelov B. A., “Some applications of groups in cryptography”, Materialy konf. “Matematika i bezopasnost' informatsionnykh tekhnologiy” (MSU, 28–29 October 2004), MCCME Publ., Moscow, 2005, 19–31 (in Russian)

[22] Zubov A. Yu., “On the diameter of the group $S_N$ with respect to a system of generators consisting of a complete cycle and a transposition”, Tr. Diskr. Mat., 2, 1998, 112–150 (in Russian) | MR | Zbl

[23] Zubov A. Yu., “On the representation of substitutions as products of a transposition and a full cycle”, Fundam. Prikl. Mat., 15:1 (2009), 31–51 (in Russian) | MR

[24] Zubov A. Yu., “About some classes of extremal oriented graphs”, Prikladnaya Diskretnaya Matematika, 2015, no. 4(30), 83–90 (in Russian)

[25] Glushkov V. M., “On the completeness of systems of operations in electronic computers”, Kibernetika, 2, 1968, 1–5 (in Russian)

[26] Golunkov Yu. V., “Software-automata implementation of the symmetric semigroup permutations”, Kibernetika, 5, 1971, 33–39 (in Russian)