计算机研究与发展
計算機研究與髮展
계산궤연구여발전
Journal of Computer Research and Development
2015年
11期
2622-2627
,共6页
短块移动%跳%换位%逆序%双重递增序
短塊移動%跳%換位%逆序%雙重遞增序
단괴이동%도%환위%역서%쌍중체증서
short block move%hop%skip%inversion%a double increasing permutation
近20年来,计算生物学领域一直试图用基因组重组事件来追溯物种进化的规律,因此基因组排列的重组排序问题被广泛而深入地研究.基因组重组包含翻转、移位、转位等多种形式.Bulteau等人证明排列的转位排序问题是NP-完全的.一次转位操作也称为一次块移动,短块移动是最常见的一种块移动.一次短块移动是将一个元素从排列中某个位置移动到最多偏离原来2个位置的块移动,因此也称为3-bounded转位.针对排列短块移动排序距离问题,给出了一类特殊排列(称之为双递增排列)的短块移动排序次数的下界.以此为依据,分析原始排列中的所有最大双递增子排列,从而给出了任意排列短块移动排序次数的下界,改进了Heath和Vergara的负面结果,并为更好的近似算法的设计打下基础.
近20年來,計算生物學領域一直試圖用基因組重組事件來追溯物種進化的規律,因此基因組排列的重組排序問題被廣汎而深入地研究.基因組重組包含翻轉、移位、轉位等多種形式.Bulteau等人證明排列的轉位排序問題是NP-完全的.一次轉位操作也稱為一次塊移動,短塊移動是最常見的一種塊移動.一次短塊移動是將一箇元素從排列中某箇位置移動到最多偏離原來2箇位置的塊移動,因此也稱為3-bounded轉位.針對排列短塊移動排序距離問題,給齣瞭一類特殊排列(稱之為雙遞增排列)的短塊移動排序次數的下界.以此為依據,分析原始排列中的所有最大雙遞增子排列,從而給齣瞭任意排列短塊移動排序次數的下界,改進瞭Heath和Vergara的負麵結果,併為更好的近似算法的設計打下基礎.
근20년래,계산생물학영역일직시도용기인조중조사건래추소물충진화적규률,인차기인조배렬적중조배서문제피엄범이심입지연구.기인조중조포함번전、이위、전위등다충형식.Bulteau등인증명배렬적전위배서문제시NP-완전적.일차전위조작야칭위일차괴이동,단괴이동시최상견적일충괴이동.일차단괴이동시장일개원소종배렬중모개위치이동도최다편리원래2개위치적괴이동,인차야칭위3-bounded전위.침대배렬단괴이동배서거리문제,급출료일류특수배렬(칭지위쌍체증배렬)적단괴이동배서차수적하계.이차위의거,분석원시배렬중적소유최대쌍체증자배렬,종이급출료임의배렬단괴이동배서차수적하계,개진료Heath화Vergara적부면결과,병위경호적근사산법적설계타하기출.
