Algorithms for Transforming Strings by Reversals
Palavras-chave:Transforming strings, Reversals, Algorithms, Heuristics
A reversal is an operation that cuts a segment of a string and reverses it. The problem of Transforming Strings by Reversals (TSbR) consists of, given two strings, ﬁnding the minimum number of reversals that transform one string into the other. TSbR is NP-hard and there are not many algorithmic results for it. In this work, we propose eight practical algorithms for TSbR and compare them, experimentally
Berman, P., Hannenhalli, S., and Karpinski, M. (2002). 1.375-Approximation Algorithm for Sorting by Reversals. In Mohring, R. and Raman, R., editors, Proceedings of the 10th Annual European Symposium on Algorithms (ESA’2002), volume 2461 of Lecture Notes in Computer Science, pages 200–210. Springer-Verlag, Berlin, Germany.
Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., and Jiang, T. (2005). Assignment of Orthologous Genes via Genome Rearrangement. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2(4):302–315.
Chrobak, M., Kolman, P., and Sgall, J. (2004). The Greedy Algorithm for the Minimum Common String Partition Problem. In Jansen, K., Khanna, S., Rolim, J. D. P., and Ron, D., editors, Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), and 8th International Workshop on Randomization and Computation (RANDOM’2004), pages 84–95, Berlin, Heidelberg. Springer.
Gonc¸alves, J. F. and Resende, M. G. C. (2010). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Hannenhalli, S. and Pevzner, P. (1996). To Cut ... or Not to Cut (Applications of Comparative Physical Maps in Molecular Evolution). In Tardos, E., editor, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’1996), pages 304–313, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.
Hannenhalli, S. and Pevzner, P. A. (1999). Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals. Journal of the ACM, 46(1):1–27.
Kececioglu, J. D. and Sankoff, D. (1995). Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement. Algorithmica, 13:180–210.
Kolman, P. and Walen, T. (2007). Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set. In Erlebach, T. and Kaklamanis, C., editors, Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA’2006), pages 279–289, Berlin, Heidelberg. Springer.
Siqueira, G., Brito, K. L., Dias, U., and Dias, Z. (2020). Heuristics for reversal distance between genomes with duplicated genes. In International Conference on Algorithms for Computational Biology, pages 29–40. Springer.
Tesler, G. (2002). GRIMM: Genome Rearrangements Web Server. Bioinformatics, 18(3):492–493