Prefix and suffix transreversals on binary and ternary strings

The problem of sorting by a genome rearrangement event asks for the minimum number of that event required to sort the elements of a given permutation. In this paper, we study a variant of the rearrangement event called prefix and suffix transreversal. A transreversal is an operation which reverses the first block before exchanging two adjacent blocks in a permutation. A prefix (suffix) transreversal always reverses and moves a prefix (suffix) of the permutation to another location. Interestingly, we will apply transreversal not on permutations but on strings over an alphabet of fixed size. We determine the minimum number of prefix and suffix transreversals required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems.