Approximation Algorithms For Sorting By Signed Short Reversals

During evolution, global mutations may modify the gene order in a genome. Such mutations are commonly referred to as rearrangement events. One of the most frequent rearrangement events observed in genomes are reversals, which are responsible for reversing the order and orientation of a sequence of genes. The problem of sorting by reversals, that is, the problem of computing the most parsimonious reversal scenario to transform one genome into another, is a well-studied problem that finds application in comparative genomics. There is a number of works concerning this problem in the literature, but these works generally do not take into account the length of the reversals. Since it has been observed that short reversals are prevalent in the evolution of some species, recent efforts have been made to address this issue algorithmically. In this paper, we add to these efforts by introducing the problem of sorting by signed short reversals and by presenting three approximation algorithms for solving it. Although the worst-case approximation ratios of these algorithms are high, we show that their expected approximation ratios for sorting a random equiprobable signed permutation are much lower. Moreover, we present experimental results on small signed permutations which indicate that the worst-case approximation ratios of these algorithms may be better than those we have been able to prove.360369 ACM Special Interest Group on Biomedical Computing (SIGBIO)Arruda, T.S., Dias, U., Dias, Z., Heuristics for the sorting by length-weighted inversion problem (2013) Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics (BCB'2013), pp. 498-507. , Washington DC, USA, ACMArruda, T.S., Dias, U., Dias, Z., Heuristics for the sorting by length-weighted inversions problem on signed permutations (2014) Proceedings of the First International Conference on Algorithms for Computational Biology (AlCoB'2014), , Lecture Notes in Computer Science, Tarragona, Spain, Springer-Verlag. To appearBader, D., Moret, B., Yan, M., A linear-time algorithm for computing inversion distance between signed permutations with an experimental study (2001) Journal of Computational Biology, 8 (5), pp. 483-491Bafna, V., Pevzner, P.A., Genome rearrangements and sorting by reversals (1996) SIAM Journal on Computing, 25 (2), pp. 272-289Bender, M.A., Ge, D., He, S., Hu, H., Pinter, R.Y., Skiena, S., Swidan, F., Improved bounds on sorting by length-weighted reversals (2008) Journal of Computer and System Sciences, 74 (5), pp. 744-774Berman, P., Hannenhalli, S., Karpinski, M., 1.375-Approximation algorithm for sorting by reversals (2002) Proceedings of the 10th Annual European Symposium on Algorithms (ESA'2002), pp. 200-210. , volume 2461 of Lecture Notes in Computer Science, Rome, Italy, Springer-VerlagCaprara, A., Sorting permutations by reversals and eulerian cycle decompositions (1999) SIAM Journal on Discrete Mathematics, 12 (1), pp. 91-110Dalevi, D., Eriksen, N., Eriksson, K., Andersson, S., Genome comparison: The number of evolutionary events separating C. Pneumoniae and C. Trachomatis (2000) Technical Report, University of UppsalaEgri-Nagy, A., Gebhardt, V., Tanaka, M.M., Francis, A.R., Group-theoretic models of the inversion process in bacterial genomes (2013) Journal of Mathematical Biology, pp. 1-23Galvao, G.R., Dias, Z., GRAAu: Genome rearrangement algorithm auditor (2012) Proceedings of the 4th International Conference on Bioinformatics and Computational Biology (BICoB'2012), pp. 97-101. , Las Vegas, Nevada, USA, Curran Associates, IncHannenhalli, S., Pevzner, P.A., Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals (1999) Journal of the ACM, 46 (1), pp. 1-27Heath, L.S., Vergara, J.P.C., Sorting by short swaps (2003) Journal of Computational Biology, 10 (5), pp. 775-789Jerrum, M., The complexity of finding minimum-length generator sequences (1985) Theoretical Computer Science, 36, pp. 265-289Kececioglu, J.D., Sankofi, D., Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement (1995) Algorithmica, 13 (1-2), pp. 80-110Lefebvre, J.F., El-Mabrouk, N., Tillier, E., Sankofi, D., Detection and validation of single gene inversions (2003) Bioinformatics, 19, pp. i190-i196McLysaght, A., Seoighe, C., Wolfe, K.H., High frequency of inversions during eukaryote gene order evolution (2000) Comparative Genomics, Computational Biology, 1, pp. 47-58. , D. Sankofi and J. Nadeau, editors, of, Springer NetherlandsNguyen, T.C., Ngo, H.T., Nguyen, N.B., Sorting by restricted-length-weighted reversals (2005) Genomics Proteomics Bioinformatics, 3 (2), pp. 120-127Pinter, R.Y., Skiena, S., Genomic sorting with length-weighted reversals (2002) Genome Informatics, 13, pp. 103-111Sankofi, D., Short inversions and conserved gene cluster (2002) Bioinformatics, 18 (10), p. 1305Seoighe, C., Federspiel, N., Jones, T., Hansen, N., Bivolarovic, V., Surzycki, R., Tamse, R., Wolfe, K.H., Prevalence of small inversions in yeast gene order evolution (2000) Proceedings of the National Academy of Sciences USA, 97 (26), pp. 14433-14437Swidan, F., Bender, M.A., Ge, D., He, S., Hu, H., Pinter, R.Y., Sorting by length-weighted reversals: Dealing with signs and circularity (2004) Combinatorial Pattern Matching, pp. 32-46. , S. Sahinalp, S. Muthukrishnan, and U. Dogrusoz, editors, volume 3109 of Lecture Notes in Computer Science, Springer Berlin HeidelbergTannier, E., Bergeron, A., Sagot, M.F., Advances on sorting by reversals (2007) Discrete Applied Mathematics, 155 (6-7), pp. 881-888Watterson, G.A., Ewens, W.J., Hall, T.E., Morgan, A., The chromosome inversion problem (1982) Journal of Theoretical Biology, 99 (1), pp. 1-