A New Lower Bound for the Distance of Sorting Permutations by Short Block Moves

Over the past twenty years, computational biology has been trying tracing the rule of evolution by genome rearrangement events, therefore the rearrangement problem of genomic permutations has been researched widely and deeply. The operations of genome rearrangement include reversals, translocations, transpositions and so on. Bulteau et al proved that the problem of sorting permutations by transpositions was NP-complete. A transposition is also called a block-move. The short block-move is the most common case of block-moves. A short block-move is a block-move whose segments are moved from its original position at most two positions，so its another name is 3-bounded transposition. For the problem of the distance of sorting permutations by short block moves, we present an implicit lower bound. In this paper, we use a special permutation called “double increasing permutation” and gain a new lower bound through analyzing the double increasing permutation. On this basis, we analyse all the maximal double increasing sub-permutations of the original permutations, and then simply sum the lower bounds to obtain a new lower bound for the distance of sorting permutations by short block moves, which improves Health and Vergaras result greatly, so that we will lay a foundation of the design of a better approximate algorithm.