《计算机学报》文章摘要   全文下载
文章题目	基因组一般移位排序问题的多项式时间算法
作者	尹晓 朱大铭
作者单位	(山东大学计算机科学与技术学院 济南 250101)
发表年份	2010
发表月份	5期(785—796)
文章摘要	摘要 基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的，未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法，给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题，利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测. 关键词 算法;基因组重组;移位;移位距离;计算生物学 中图法分类号 TP18 DOI号: 10.3724/SP.J.1016.2010.00785