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

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² log n) 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²) 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²).