Heuristics for the Sorting Signed Permutations by Reversals and Transpositions Problem

We present two heuristics, Sliding Window and Look Ahead, to improve solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem. To assess the heuristics, we implemented algorithms described in the literature to provide initial solutions. Despite the fact that we addressed a specific problem, both heuristics can be applied to many others within the area of genome rearrangement. When time is a crucial factor, Sliding Window is a better choice because it runs in linear time and improves the initial solutions in 76.4% of cases. If the quality of the solution is a priority, Look Ahead should be preferred because it improves the initial solutions in 97.6% of cases, but it runs in O(n(3) x alg(n)), where alg(n) is the complexity of the algorithm given as input. By using these heuristics one may find a good tradeoff between running time and solution improvement.