Regular Research PaperNo Access

Sorting permutations by fragmentation-weighted operations

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

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

Corresponding author.

Center for Mathematics, Computation and Cognition, Federal University of ABC (UFABC), Santo André, São Paulo 09210-580, Brazil

E-mail Address: carla.negri@ufabc.edu.br

Search for more papers by this author

, and

Zanoni Dias

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

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

Search for more papers by this author

https://doi.org/10.1142/S0219720020500067Cited by:3 (Source: Crossref)

Abstract

One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species’ genome. When we represent genomes as permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so, the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the cost of that sequence is minimum. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about the lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for five versions of this problem involving reversals and transpositions. We also give bounds for the diameters concerning these problems and provide an improved approximation factor for simple permutations considering transpositions.

A preliminary version of this paper previously appeared in the Proceedings of the 5th International Conference on Algorithms for Computational Biology (AlCoB 2018).

Keywords:

References

1. Caprara A, Sorting permutations by reversals and Eulerian cycle decompositions, SIAM J Discrete Math 12(1) :91–110, 1999. Crossref, Google Scholar
2. Bulteau L, Fertin G, Rusu I, Sorting by transpositions is difficult, SIAM J Comput 26(3) :1148–1180, 2012. Google Scholar
3. Berman P, Hannenhalli S, Karpinski M, 1.375-Approximation algorithm for sorting by reversals, Proc 10th Annual European Symp Algorithms (ESA’2002), Möhring R, Raman R (eds.), Springer-Verlag Berlin Heidelberg, New York, Berlin/Heidelberg, Germany, pp. 200–210, 2002. Crossref, Google Scholar
4. Elias I, Hartman T, A 1.375-approximation algorithm for sorting by transpositions, IEEE/ACM Trans Comput Biol Bioinf 3(4) :369–379, 2006. Crossref, Medline, Google Scholar
5. 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
6. 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, Los Alamitos, CA, USA, pp. 96–102, 1998. Crossref, Google Scholar
7. Rahman A, Shatabda S, Hasan M, An approximation algorithm for sorting by reversals and transpositions, J Discrete Algorithms 6(3) :449–457, 2008. Crossref, 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. Oliveira AR, Brito KL, Dias U, Dias Z, On the Complexity of sorting by reversals and transpositions problems, J Comput Biol 26(11):1223–1229, 2019. Crossref, Medline, Google Scholar
10. Bader M, Ohlebusch E, Sorting by weighted reversals, transpositions, and inverted transpositions, J Comput Biol 14(5) :615–636, 2007. Crossref, Medline, Google Scholar
11. Blanchette M, Kunisawa T, Sankoff D, Parametric genome rearrangement, Gene 172(1) :GC11–GC17, 1996. Crossref, Medline, Google Scholar
12. Eriksen N, Combinatorics of Genome Rearrangements and Phylogeny, Teknologie Licentiat Thesis, Kungliga Tekniska Högskolan, Stockholm, 2001. Google Scholar
13. Oliveira AR, Brito KL, Dias Z, Dias U, Sorting by weighted reversals and transpositions, J Comput Biol PP :1–12, 2019. Google Scholar
14. Alexandrino AO, Lintzmayer CN, Dias Z, Approximation algorithms for sorting permutations by fragmentation-weighted operations, in Jansson J, Martín-Vide C, Vega-Rodríguez MA (eds.), Algorithms for Computational Biology, Springer International Publishing, Heidelberg, Germany, pp. 53–64, 2018. Crossref, Google Scholar
15. Chen X, On sorting unsigned permutations by double-cut-and-joins, J Comb Optim 25(3) :339–351, 2013. Crossref, Google Scholar
16. Riordan J, A recurrence for permutations without rising or falling successions, Ann Math Statist 36(2) :708–710, 1965. Crossref, Google Scholar
17. Lin G, Jiang T, A further improved approximation algorithm for breakpoint graph decomposition, J Comb Optim 8(2) :183–194, 2004. Crossref, Google Scholar
18. Bafna V, Pevzner PA, Sorting by transpositions, SIAM J Discrete Math 11(2) :224–240, 1998. Crossref, Google Scholar
19. Hartman T, Sharan R, A 1.5-approximation algorithm for sorting by transpositions and transreversals, J Comput Syst Sci 70(3) :300–320, 2005. Crossref, Google Scholar
20. 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
21. Chitturi B, Tighter upper bound for sorting permutations with prefix transpositions, Theor Comput Sci 602 :22–31, 2015. Crossref, Google Scholar