计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2010年
9期
152-156
,共5页
基因组重组%交互移位排序%移位距离
基因組重組%交互移位排序%移位距離
기인조중조%교호이위배서%이위거리
交互移位排序问题(SRT)是寻找一个使一个基因组转变为另一个基因组的最短交互移位序列.现在已有多个多项式时间的SRT算法,但大多数问题实例都有许多个最短交互移位序列,因此寻找所有最短交互移位序列问题是SRT一个自然的推广.这个问题可以归约为寻找一个基因组相对于另一个基因组的全部可行交互移位,即所有移位ρ满足:在一个基因组上执行ρ之后,所得基因组相对于另一个基因组的移位距离会减少.本文提出一个用来寻找全部可行交互移位的有效算法,尽管新算法的时间复杂度比穷举法改进不大,但实验结果表明,其在实际运行中表现更好.
交互移位排序問題(SRT)是尋找一箇使一箇基因組轉變為另一箇基因組的最短交互移位序列.現在已有多箇多項式時間的SRT算法,但大多數問題實例都有許多箇最短交互移位序列,因此尋找所有最短交互移位序列問題是SRT一箇自然的推廣.這箇問題可以歸約為尋找一箇基因組相對于另一箇基因組的全部可行交互移位,即所有移位ρ滿足:在一箇基因組上執行ρ之後,所得基因組相對于另一箇基因組的移位距離會減少.本文提齣一箇用來尋找全部可行交互移位的有效算法,儘管新算法的時間複雜度比窮舉法改進不大,但實驗結果錶明,其在實際運行中錶現更好.
교호이위배서문제(SRT)시심조일개사일개기인조전변위령일개기인조적최단교호이위서렬.현재이유다개다항식시간적SRT산법,단대다수문제실례도유허다개최단교호이위서렬,인차심조소유최단교호이위서렬문제시SRT일개자연적추엄.저개문제가이귀약위심조일개기인조상대우령일개기인조적전부가행교호이위,즉소유이위ρ만족:재일개기인조상집행ρ지후,소득기인조상대우령일개기인조적이위거리회감소.본문제출일개용래심조전부가행교호이위적유효산법,진관신산법적시간복잡도비궁거법개진불대,단실험결과표명,기재실제운행중표현경호.
