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

Faster algorithm for computing translocation distance of sorting signed genomes

作　　者：刘燕[1] 李辉智[2] 易东[1] 敬培胜[1] 

机构地区：[1]第三军医大学卫生统计学教研室 [2]西南政法学院刑侦系,重庆400016

出　　处：《北京生物医学工程》2007年第2期172-174,198,共4页Beijing Biomedical Engineering

基　　金：国家自然科学基金(60371034)资助

摘　　要：目的寻找一种有向染色体组织移位排序距离的快速算法,解决其计算的复杂性问题。方法引入长圈的分裂和新的长圈分组算法,降低计算复杂性。结果原有的排序最好算法的复杂度为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.

关 键 词：染色体组排序 移位距离 计算分子生物学 

分 类 号：R318.08[医药卫生—生物医学工程]