摘要
有向基因组移位排序问题在计算生物学研究中占有重要位置 .以前最好的算法时间复杂度为O (n2logn) .该文给出一个有向基因组移位排序的新多项式算法 ,将移位排序的时间复杂度改进为O(n2 ) .算法改进的关键在于找到一种寻找有效合理移位的新方法 ,通过在最小子排列中删除无关顶点确定一个合理移位是否有效 ,从而将寻找一个有效移位的时间复杂度改进为O(n) ,总时间复杂度由此降为O(n2 ) .
Sorting genomes by translocations plays an important role in computational biology. Translocation sorting problem for oriented genomes asks the minimum number of translocations to transform one oriented genome into the other. The previous best algorithm uses O(n 2logn) time to compute the optimal translocation sequence transforming one oriented genome into the other. This paper presents a new polynomial time algorithm to implement the same computation by O(n 2) time. The key part for the improvement of the new algorithm is the invention of a new method to compute one validate proper translocation. We find that the valid translocation in a minimum sub permutation is not related with all the vertices of the minimum sub permutation and we can determine a set of vertices unrelated. A proper translocation is determined to be valid by deleting the unrelated vertices in a minimum sub permutation recurrently, thus the valid translocation can be fixed in O(n) time by the new method. There are at most O(n) translocations to transform a genome of n genes into other. Thus the time complexity of finding the translocation sequence is improved to O(n 2).
出处
《计算机学报》
EI
CSCD
北大核心
2004年第10期1354-1360,共7页
Chinese Journal of Computers
基金
国家自然科学基金 (60 0 73 0 42
60 2 73 0 3 2 )
山东省中青年科学家奖励基金资助
