Rodrigues Oliveira Andre, Lima Brito Klairton, Dias Zanoni, Dias Ulisses
1 Institute of Computing, University of Campinas, Campinas, Brazil.
2 School of Technology, University of Campinas, Limeira, Brazil.
J Comput Biol. 2019 May;26(5):420-431. doi: 10.1089/cmb.2018.0257. Epub 2019 Feb 19.
Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event, and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem on signed permutations. In this study, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present two algorithms with approximation factors of 5/3 and 3/2. We also developed a generic approximation algorithm to deal with different weights for reversals and transpositions, and we show the approximation factor reached in each scenario.
