基因组一般移位排序问题的多项式时间算法

摘要：

基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的,未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法,给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题,利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测.

关键词：算法、基因组重组、移位、移位距离、计算生物学

所属期刊栏目：33

分类号：TPL8

资助基金：国家自然科学基金60573024,60970003,60603007;教育部博士点基金20090131110009

在线出版日期：2010-06-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：785-796