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

来源：计算机研究与发展杂志2015年第11期北京时间：

作者：王彤,姜海涛,朱大铭,

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

关键词：短块移动, 跳, 换位, 逆序, 双重递增序,