反轉(zhuǎn)排序問(wèn)題的評(píng)測(cè)與移位排序問(wèn)題的改進(jìn).pdf

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

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

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

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