Sorting permutations by reversals and/or transpositions is an important genome rearrangement problem in computational molecular biology. From theoretical point of view, finding efficient algorithms for this problem and its variations are quite challenging. In this paper we consider the problem of sorting unsigned permutations by prefix reversals and prefix transpositions , where a prefix reversal or a prefix transposition is applied always at the unsorted suffix of the given permutation. For this problem we first present a 3-approximation algorithm, which performs close to 2 in practice. We further analyze the problem in more practical way and consider the variation where a certain number of prefix reversals are forced to happen in the sorting process. Here we achieve an improved approximation ratio of (3-\frac{3r{b(\pi)+r}), where r is the }  number of prefix reversals that must happen in the sorting, when possible, and b(\pi)\geq 2r is the number of breakpoints in the given permutation. Again, in this variation our algorithm performs close to 1.6 in practice .
In this paper we study several variations of thepancake flipping problem, which is also well known as the problem ofsorting by prefix reversals. We consider the variations in the sorting process by adding with prefix reversals other similar operations such as prefix transpositions and prefix transreversals. These type of sorting problems have applications in interconnection networks and computational biology. We first study the problem of sorting unsigned permutations by prefix reversals and prefix transpositions and present a 3-approximation algorithm for this problem. Then we give a 2-approximation algorithm for sorting by prefix reversals and prefix transreversals. We also provide a 3-approximation algorithm for sorting by prefix reversals and prefix transpositions where the operations are always applied at the unsorted suffix of the permutation. We further analyze the problem in more practical way and {b(\pi)+r}), where r is the } show quantitatively how approximation ratios of our algorithms improve with the increase of number of prefix reversals applied by optimal algorithms. Finally, we present experimental results to support our analysis .
R
Sorting permutations by reversals and/or transpositions is an important genome rearrangement problem in computational molecular biology. From theoretical point of view, finding efficient algorithms for this problem and its variations are quite challenging. In this paper we consider
In this paper we study several variations of the
A
pancake flipping problem
A
, which is also well known as the problem of
A
sorting by prefix reversals
A
. We consider the variations in the sorting process by adding with prefix reversals other similar operations such as prefix transpositions and prefix transreversals. These type of sorting problems have applications in interconnection networks and computational biology. We first study
R
, where a prefix reversal or a prefix transposition is applied always
and present a 3-approximation algorithm for this problem. Then we give a 2-approximation algorithm for sorting by prefix reversals and prefix transreversals. We also provide a 3-approximation algorithm for sorting by prefix reversals and prefix transpositions where the operations are always applied
R
given permutation. For this problem we first present a 3-approximation algorithm, which performs close to 2 in practice.
permutation.
D
consider the variation where a certain number of prefix reversals are forced to happen in the sorting process. Here we achieve an improved approximation ratio of (3-\frac{3r
A
show quantitatively how approximation ratios of our algorithms improve with the increase of
R
that must happen in the sorting, when possible, and b(\pi)\geq 2r is the number of breakpoints in the given permutation. Again, in this variation our algorithm performs close to 1.6 in practice
applied by optimal algorithms. Finally, we present experimental results to support our analysis