作者:刘晓文; 朱大铭; 马绍汉; 李子茂; 王鲁生基因组移位排序问题算法计算生物学时间复杂度
摘要:有向基因组移位排序问题在计算生物学研究中占有重要位置.以前最好的算法时间复杂度为O(n2logn).该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n2).算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n2).
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社