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

作者：刘晓; 朱大铭; 马绍汉; 李子茂; 王鲁生

来源：计算机学报, 2004, (10): 1354-1360.

• 基因组
• 移位
• 计算生物学
• 算法
• 时间复杂度 genomes
• translocation
• computational biology
• algorithm
• time complexity

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

• 单位
  山东大学; 香港城市大学