On the tightness of the alternating-cycle lower bound for sorting by reversals

We give a theoretical answer to a natural question arising from a few years of computational experiments on the problem of sorting a permutation by th e minimum number of reversals, which has relevant applications in computati onal molecular biology. The experiments carried out on the problem showed t hat the so-called alternating-cycle lower bound is equal to the optimal sol ution value in almost all cases, and this is the main reason why the state- of-the-art algorithms for the problem are quite effective in practice. Sinc e worst-case analysis cannot give an adequate justification for this observ ation, we focus our attention on estimating the probability that, for a ran dom permutation of n elements, the above lower bound is not tight. We show that this probability is low even for small n, and asymptotically Theta(1/n (5)), i.e., O(1/n(5)) and Omega(1/n(5)). This gives a satisfactory explanat ion to empirical observations and shows that the problem of sorting by reve rsals and its alternating-cycle relaxation are essentially the same problem , with the exception of a small fraction of "pathological" instances, justi fying the use of algorithms which are heavily based on this relaxation. Fro m our analysis we obtain convenient sufficient conditions to test if the al ternating-cycle lower bound is tight for a given instance. We also consider the case of signed permutations, for which the analysis is much simpler, a nd show that the probability that the alternating-cycle lower bound is not tight for a random signed permutation of m elements is asymptotically Theta (1/m(2)).