排列短块移动排序距离的新下界

近20年来，计算生物学领域一直试图用基因组重组事件来追溯物种进化的规律，因此基因组排列的重组排序问题被广泛而深入地研究.基因组重组包含翻转、移位、转位等多种形式.Bulteau等人证明排列的转位排序问题是NP-完全的.一次转位操作也称为一次块移动，短块移动是最常见的一种块移动.一次短块移动是将一个元素从排列中某个位置移动到最多偏离原来2个位置的块移动，因此也称为3-bounded 转位.针对排列短块移动排序距离问题，给出了一类特殊排列(称之为双递增排列)的短块移动排序次数的下界.以此为依据，分析原始排列中的所有最大双递增子排列，从而给出了任意排列短块移动排序次数的下界，改进了Heath和Vergara的负面结果，并为更好的近似算法的设计打下基础.

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.