计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2004年
10期
1354-1360
,共7页
刘晓文%朱大铭%马绍汉%李子茂%王鲁生
劉曉文%硃大銘%馬紹漢%李子茂%王魯生
류효문%주대명%마소한%리자무%왕로생
基因组%移位%计算生物学%算法%时间复杂度
基因組%移位%計算生物學%算法%時間複雜度
기인조%이위%계산생물학%산법%시간복잡도
有向基因组移位排序问题在计算生物学研究中占有重要位置.以前最好的算法时间复杂度为O(n2logn).该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n2).算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n2).
有嚮基因組移位排序問題在計算生物學研究中佔有重要位置.以前最好的算法時間複雜度為O(n2logn).該文給齣一箇有嚮基因組移位排序的新多項式算法,將移位排序的時間複雜度改進為O(n2).算法改進的關鍵在于找到一種尋找有效閤理移位的新方法,通過在最小子排列中刪除無關頂點確定一箇閤理移位是否有效,從而將尋找一箇有效移位的時間複雜度改進為O(n),總時間複雜度由此降為O(n2).
유향기인조이위배서문제재계산생물학연구중점유중요위치.이전최호적산법시간복잡도위O(n2logn).해문급출일개유향기인조이위배서적신다항식산법,장이위배서적시간복잡도개진위O(n2).산법개진적관건재우조도일충심조유효합리이위적신방법,통과재최소자배렬중산제무관정점학정일개합리이위시부유효,종이장심조일개유효이위적시간복잡도개진위O(n),총시간복잡도유차강위O(n2).
