Regular Papers: Research PapersNo Access

Sorting permutations by prefix and suffix rearrangements

Carla Negri Lintzmayer

Institute of Computing, University of Campinas, Campinas, São Paulo, 13083-852, Brazil

E-mail Address: carlanl@ic.unicamp.br

Corresponding author.

Search for more papers by this author

Guillaume Fertin

Laboratoire des Sciences du Numérique de Nantes, UMR CNRS 6004, University of Nantes, 44322 Nantes Cedex 3, France

E-mail Address: guillaume.fertin@univ-nantes.fr

Search for more papers by this author

, and

Zanoni Dias

Laboratoire des Sciences du Numérique de Nantes, UMR CNRS 6004, University of Nantes, 44322 Nantes Cedex 3, France

E-mail Address: zanoni@ic.unicamp.br

Search for more papers by this author

https://doi.org/10.1142/S0219720017500020Cited by:6 (Source: Crossref)

Abstract

Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ( $2 + λ$ )-approximation algorithms for these problems, where $λ$ is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.

Parts of this paper appeared in Proceedings of the 11th Latin American Symposium 2014 and Proceedings of the 1st International Conference on Algorithms for Computational Biology 2014.

Keywords:

References

1. Dweighter H, Problem E2569, Am Math Monthly 82 :1010, 1975. Crossref, Google Scholar
2. Pevzner PA, Waterman MS, Open combinatorial problems in computational molecular biology, Proc 3rd Israel Symp Theory of Computing Systems (ISTCS’1995), IEEE Computer Society, Washington, DC, USA, pp. 158–173, 1995. Google Scholar
3. Gates WH, Papadimitriou CH, Bounds for sorting by prefix reversal, Discrete Math 27 (1) :47–57, 1979. Crossref, Google Scholar
4. Heydari MH, Sudborough IH, On the diameter of the pancake network, J Algor 25 (1) :67–94, 1997. Crossref, Google Scholar
5. Chitturi B, Fahle W, Meng Z, Morales L, Shields CO, Sudborough IH, Voit W, An (18/11) $n$ upper bound for sorting by prefix reversals, Theor Comput Sci 410 (36) :3372–3390, 2009. Crossref, Google Scholar
6. Bulteau L, Fertin G, Rusu I, Pancake flipping is hard, J Comput Syst Sci 81 (8) :1556–1574, 2015. Crossref, Google Scholar
7. Fischer J, Ginzinger SW, A 2-approximation algorithm for sorting by prefix reversals, Proc 13th Annual European Conf Algorithms (ESA’2005), Springer-Verlag, Berlin, Heidelberg, pp. 415–425, 2005. Google Scholar
8. Cibulka J, On average and highest number of flips in pancake sorting, Theor Comput Sci 412 (8–10) :822–834, 2011. Crossref, Google Scholar
9. Cohen DS, Blum M, On the problem of sorting burnt pancakes, Discrete Appl Math 61 (2) :105–120, 1995. Crossref, Google Scholar
10. Berman P, Hannenhalli S, Karpinski M, 1.375-Approximation algorithm for sorting by Reversals, Proc 10th Annual European Symp Algorithms (ESA’2002), Springer-Verlag, London, UK, pp. 200–210, 2002. Google Scholar
11. Elias I, Hartman T, A 1.375-approximation algorithm for sorting by transpositions, IEEE/ACM Trans Comput Biol Bioinform 3 (4) :369–379, 2006. Crossref, Medline, Google Scholar
12. Bulteau L, Fertin G, Rusu I, Sorting by transpositions is difficult, SIAM J Comput 26 (3) :1148–1180, 2012. Google Scholar
13. Caprara A, Sorting permutations by reversals and Eulerian cycle decompositions, SIAM J Discrete Math 12 (1) :91–110, 1999. Crossref, Google Scholar
14. Bafna V, Pevzner PA, Genome rearrangements and sorting by reversals, SIAM J Comput 25 (2) :272–289, 1996. Crossref, Google Scholar
15. Eriksson H, Eriksson K, Karlander J, Svensson L, Wastlund J, Sorting a bridge hand, Discrete Math 241 (1–3) :289–300, 2001. Crossref, Google Scholar
16. Hannenhalli S, Pevzner PA, Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals, J ACM 46 (1) :1–27, 1999. Crossref, Google Scholar
17. Tannier E, Bergeron A, Sagot MF, Advances on sorting by reversals, Discrete Appl Math 155 (6–7) :881–888, 2007. Crossref, Google Scholar
18. Bader DA, Moret BME, Yan M, A linear-time algorithm for computing inversion distance between signed permutations with an experimental study, J Comput Biol 8 :483–491, 2001. Crossref, Medline, Google Scholar
19. Fertin G, Labarre A, Rusu I, Tannier É, Vialette S, Combinatorics of Genome Rearrangements, Computational Molecular Biology, The MIT Press, 2009. Crossref, Google Scholar
20. Walter MEMT, Dias Z, Meidanis J, Reversal and transposition distance of linear chromosomes, Proc 5th Int Symp String Processing and Information Retrieval (SPIRE’1998), IEEE Computer Society, Santa Cruz, Bolivia, pp. 96–102, 1998. Google Scholar
21. Rahman A, Shatabda S, Hasan M, An approximation algorithm for sorting by reversals and transpositions, J Discrete Algor 6 (3) :449–457, 2008. Crossref, Google Scholar
22. Bafna V, Pevzner PA, Sorting by transpositions, SIAM J Discrete Math 11 (2) :224–240, 1998. Crossref, Google Scholar
23. Chen X, On sorting unsigned permutations by double-cut-and-joins, J Combin Optim 25 (3) :339–351, 2013. Crossref, Google Scholar
24. Dias Z, Meidanis J, Sorting by prefix transpositions, Proc 9th Int Symp String Processing and Information Retrieval (SPIRE’2002), Springer-Verlag, London, UK, pp. 65–76, 2002. Google Scholar
25. Labarre A, Edit distances and factorisations of even permutations, Proc 16th Annual European Symp Algorithms (ESA’2008), Springer-Verlag, Berlin, Heidelberg, pp. 635–646, 2008. Google Scholar
26. Chitturi B, Tighter upper bound for sorting permutations with prefix transpositions, Theor Comput Sci 602 :22–31, 2015. Crossref, Google Scholar
27. Hasan M, Rahman A, Rahman MK, Rahman MS, Sharmin M, Yeasmin R, Pancake flipping and sorting permutations, J Discrete Algor 33 :139–149, 2015. Crossref, Google Scholar
28. Dias Z, Dias U, Sorting by prefix reversals and prefix transpositions, Discrete Appl Math 181 :78–89, 2015. Crossref, Google Scholar
29. Fertin G, Jankowiak L, Jean G, Prefix and suffix reversals on strings, Proc 22nd Int Symp String Processing and Information Retrieval (SPIRE’2015), Springer International Publishing, London, UK, pp. 165–176, 2015. Google Scholar
30. Rusu I, Log-lists and their applications to sorting by transpositions, reversals and block-interchanges, CoRR abs/1507.01512, 2015, Available at http://arxiv.org/abs/1507.01512. Google Scholar
31. Dias U, Dias Z, Heuristics for the transposition distance problem, J Bioinform Comput Biol 11 (5) :17, 2013. Link, Google Scholar
32. Dias U, Galvão GR, Lintzmayer CN, Dias Z, A general heuristic for genome rearrangement problems, J Bioinform Comput Biol 12 (3) :26, 2014. Link, Google Scholar
33. Galvão GR, Dias Z, An audit tool for genome rearrangement algorithms, J Exp Algor 19 :1.7:1.1–1.7:1.34, 2015. Google Scholar