有向染色体组移位排序距离的快速算法

Faster algorithm for computing translocation distance of sorting signed genomes

目的寻找一种有向染色体组织移位排序距离的快速算法,解决其计算的复杂性问题。方法引入长圈的分裂和新的长圈分组算法,降低计算复杂性。结果原有的排序最好算法的复杂度为O(n^2),改进算法的复杂度为O(nlg·n)。结论改进算法能大大提高计算速度,避免了排序算法的NP难问题。

objective To find a fast algorithm for computing translocation distance of sorting signed genomes, and to solve the computational complexity of the algorithm. Methods We introduced the decomposition of long cycles and a new algorithm for grouping long cycles. Results The time complexity of the best known sorting algorithm is O（ n^2 ） , and the time complexity of the improved algorithm is O （ nlg^＊ n）. Conclusion The improved algorithm speeds up the computation greatly and avoids the NP-hardness of the sorting algorithm.