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

• 作者: 尹晓 朱大铭
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 算法 基因组重组 移位 移位距离 计算生物学
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 785-796
• 分类号: TP18
• 字数: 15830字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.00785

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
2	尹晓	山东大学计算机科学与技术学院	6	22	2.0	4.0