反轉(zhuǎn)排序問題的評測與移位排序問題的改進(jìn).pdf

1、基因重組是生物進(jìn)化的重要方式,如果對每個基因,用一個有符號的整數(shù)代替,則對基因重組的研究就演變?yōu)閷ε判蛩惴ǖ难芯?用排序算法模擬基因組的重組時,在模擬和生物學(xué)數(shù)據(jù)上得到了令人驚異的準(zhǔn)確結(jié)果.因此,基因重組算法的研究是對分子生物學(xué)中研究生物進(jìn)化有重要的意義.本文討論了基因重組問題中的2個問題——有符號排列的反轉(zhuǎn)排序問題(Sort Signed Permutation By Reversals)和移位排序問題(Sort By Translo

2、cations).這兩個問題分別是對于單條染色體基因重組和染色體組基因重組的模擬.有符號排列的反轉(zhuǎn)排序問題.將單條染色體用有符號整數(shù)表示,從而使染色體通過反轉(zhuǎn)變異的分子生物學(xué)問題演變?yōu)檠芯坑蟹栒麛?shù)排列通過反轉(zhuǎn)排序的計算機(jī)算法問題.該問題目前對于計算反轉(zhuǎn)距離,有時間復(fù)雜度為O(n<'2>)的算法,對計算反轉(zhuǎn)步驟,有時間復(fù)雜度為O(n)的算法.本文對于該問題的研究,主要是總結(jié),驗(yàn)證了前人的研究成果,提出了經(jīng)過優(yōu)化的算法實(shí)現(xiàn)和數(shù)據(jù)結(jié)構(gòu),對算

3、法進(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果顯示,本文的算法實(shí)現(xiàn)比對照算法實(shí)現(xiàn)快7-10倍,并且將可計算的輸入長度改進(jìn)為僅受限于計算機(jī)硬件條件.移位排序問題.將含有多條染色體的染色體組用幾組有符號整數(shù)的排列表示,從而模擬了染色體組通過移位變異的分子生物學(xué)問題.該問題目前的研究成果,對于計算移位距離,有時間復(fù)雜度為O(n<'2>)的算法,對計算移位步驟,其算法的時間復(fù)雜度為O(n<'2>logn).本文總結(jié)了前人的研究成果,并對計算移位距離的問題進(jìn)行了深入的研

4、究,大大改進(jìn)了其時間復(fù)雜度,提出一個計算移位距離的時間復(fù)雜度為O(n)的算法.然后,設(shè)計了數(shù)據(jù)結(jié)構(gòu),提出了算法的實(shí)現(xiàn),取得了實(shí)驗(yàn)數(shù)據(jù),驗(yàn)證了算法.本文的算法實(shí)現(xiàn),在計算50000個基因的移位排序時,用時為30秒.本文的研究,1)總結(jié)并詳細(xì)敘述了有符號排列的反轉(zhuǎn)排序問題的算法前人研究中的錯誤,予以更正,并給出了優(yōu)化的實(shí)現(xiàn)方法;2)改進(jìn)了有符號染色體組的移位排序問題算法,同樣給出了高效的實(shí)現(xiàn)方法.本文的研究成果和實(shí)驗(yàn)數(shù)據(jù),對于將其應(yīng)用于實(shí)際