Approximation algorithms for sorting by signed short reversals

During evolution, global mutations may modify the gene order in a genome. Such mutations are commonly referred to as rearrangement events. One of the most frequent rearrangement events observed in genomes are reversals, which are responsible for reversing the order and orientation of a sequence of genes. The problem of sorting by reversals, that is, the problem of computing the most parsimonious reversal scenario to transform one genome into another, is a well-studied problem that finds application in comparative genomics. There is a number of works concerning this problem in the literature, but these works generally do not take into account the length of the reversals. Since it has been observed that short reversals are prevalent in the evolution of some species, recent efforts have been made to address this issue algorithmically. In this paper, we add to these efforts by introducing the problem of sorting by signed short reversals and by presenting three approximation algorithms for solving it. Although the worst-case approximation ratios of these algorithms are high, we show that their expected approximation ratios for sorting a random equiprobable signed permutation are much lower. Moreover, we present experimental results on small signed permutations which indicate that the worst-case approximation ratios of these algorithms may be better than those we have been able to prove.