有向基因组移位排序问题的O(n2)快速算法

• 作者: 刘晓文 朱大铭 李子茂 王鲁生 马绍汉
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 基因组 移位 计算生物学 算法 时间复杂度
• 年，卷（期）: 2004,（10）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1354-1360
• 页数: 7页
• 分类号: TP301
• 字数: 7163字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2004.10.007

摘要

有向基因组移位排序问题在计算生物学研究中占有重要位置.以前最好的算法时间复杂度为O(n2logn).该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n2).算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
2	马绍汉	山东大学计算机科学与技术学院	39	302	10.0	15.0
3	李子茂	山东大学计算机科学与技术学院	3	7	2.0	2.0
4	刘晓文	山东大学计算机科学与技术学院	1	4	1.0	1.0
5	王鲁生	香港城市大学计算机科学系	1	4	1.0	1.0