基因組重組排序問題的算法研究.pdf

1、利用遺傳信息解答人們關(guān)于生命的困惑是人類與自然界共存并與自然界作斗爭(zhēng)的重要挑戰(zhàn),利用遺傳信息探尋生命規(guī)律的每一步都離不開“計(jì)算”,因此計(jì)算生物學(xué)成為近20年來十分活躍的學(xué)科。
　　 基因組重組是計(jì)算生物學(xué)的一個(gè)重要研究領(lǐng)域。20世紀(jì)30年代末,Dobzhansky和Sturtevant證明了兩個(gè)不同物種Drosophilia pseudoobscura和Miranda的基因組可以通過17次反轉(zhuǎn)相互轉(zhuǎn)換,從而給出了基因組重組存在的

2、有力證據(jù)。隨后的許多研究表明,基因組重組是生物進(jìn)化的一種普遍模式,也是微生物、植物、動(dòng)物呈現(xiàn)多樣性的主要因?yàn)橹弧?br>　　 一條染色體是一個(gè)基因序列,基因組是一組染色體的集合。用一個(gè)整數(shù)表示一個(gè)基因。每個(gè)基因都有方向。若基因的方向是已知的,在表示基因的整數(shù)前增加一個(gè)符號(hào)(“+”或“-”)表示基因的相對(duì)方向。若基因的方向是未知的,則整數(shù)前不帶符號(hào)。有些物種的基因組只包含單條染色體,而高級(jí)物種的基因組則由多條染色體構(gòu)成。若一個(gè)基因組(

3、或染色體)中的基因用有符號(hào)整數(shù)表示,則稱這個(gè)基因組(或染色體)是有向的或有符號(hào)的(Signed):否則,稱之為無向的或無符號(hào)的(Unsigned)。
　　 雖然基因組的重組過程非常復(fù)雜,但可歸為三種基本操作:反轉(zhuǎn)(Reversal)、移位(Translocation)和轉(zhuǎn)位(Transposition)。一次重組操作可將一個(gè)基因組轉(zhuǎn)化為另一個(gè)新的基因組。生物物種的進(jìn)化實(shí)際上就是通過各種重組操作將一個(gè)基因組轉(zhuǎn)化為另一個(gè)基因組的過程

4、。
　　 給定兩個(gè)基因組A和B,基因組重組排序問題要求計(jì)算將A轉(zhuǎn)化為B所需的最少重組操作次數(shù)以及相應(yīng)的最短重組操作序列。A轉(zhuǎn)化為B的最少重組操作次數(shù)稱作A和B之間的重組距離?；诜肿由飳W(xué)的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證,重組距離是衡量生物種族之間親緣關(guān)系的一個(gè)重要指標(biāo),對(duì)生物種族進(jìn)化研究具有重要意義。
　　 基因組的重組排序問題在近幾年得到了廣泛的研究,產(chǎn)生了大量的研究成果。只考慮單一操作的排序問題是最基本的重組排序問題,如反轉(zhuǎn)排序、移

5、位排序、轉(zhuǎn)位排序。反轉(zhuǎn)將一條染色體中～段連續(xù)的基因序列倒置。有向基因組反轉(zhuǎn)排序問題有多個(gè)多項(xiàng)式時(shí)間算法,目前最好的時(shí)間復(fù)雜度為O(n√nlogn)。而無向基因組反轉(zhuǎn)排序問題被證明為Np-hard。目前該問題最好的近似度是1.375。移位將兩條染色體分別斷開再重新連接,形成兩條新的染色體。有向基因組移位排序問題被證明有多項(xiàng)式時(shí)間算法,后來又有多個(gè)改進(jìn)算法,目前最好的時(shí)間復(fù)雜度為O(n√nlogn)。無向基因組的移位排序問題被證明是Np-h

6、ard,目前該問題最好的近似度為1.5+ε。轉(zhuǎn)位將一條染色體上兩段相鄰的基因序列交換位置。轉(zhuǎn)位排序問題的復(fù)雜性仍然是未知的,該問題有多個(gè)1.5-近似算法。目前該問題最好的近似度是1.375。考慮兩種或兩種以上操作的組合操作排序的計(jì)算結(jié)果更為分子生物學(xué)研究所接受。其中,反轉(zhuǎn)和移位排序是最自然的組合重組排序問題。Hannenhalli和Pevzner將有向基因組反轉(zhuǎn)和移位排序問題歸約到有向基因組反轉(zhuǎn)排序問題,給出了該問題的多項(xiàng)式時(shí)間算法,時(shí)

7、間復(fù)雜度為D(n4)。
　　 斷點(diǎn)圖是研究基因組重組排序算法的重要工具。已經(jīng)證明,兩個(gè)基因組的重組距離與斷點(diǎn)圖中特定的組合結(jié)構(gòu)密切相關(guān)。
　　 本文主要對(duì)基因組重組排序的兩個(gè)問題進(jìn)行了研究:
　　 (1)有向基因組的一般移位排序問題。
　　 交互型移位和非交互型移位均為移位的特殊形式。移位排序問題要求計(jì)算從一個(gè)包含多條染色體的基因組轉(zhuǎn)化為另一個(gè)基因組所需的最少移位次數(shù)以及相應(yīng)的最短移位序列。有向基因組的移

8、位排序問題已有多個(gè)多項(xiàng)式時(shí)間算法。
　　 值得注意的是,已有的移位排序算法都只考慮了交互型移位。一個(gè)基因組若僅通過交互型移位轉(zhuǎn)化為另一個(gè)基因組,那么這兩個(gè)基因組必須具有相同的尾基因集合。然而在生物學(xué)實(shí)際應(yīng)用中,源基因組和目標(biāo)基因組往往不包含相同的尾基因。可以認(rèn)為,兩個(gè)基因組包含不同的尾基因,是因非交互型移位形成的。因而我們需要考慮更一般的情況,即允許兩個(gè)基因組包含不同的尾基因。顯然,在這種情況下,非交互型移位是必需的操作。將交互

9、型移位和非交互型移位統(tǒng)稱為一般移位。Ozery-Flato首先提出了一般移位排序問題,并猜測(cè)該問題可以在多項(xiàng)式時(shí)間內(nèi)解決。但一直沒有人給出該問題的算法和復(fù)雜性研究結(jié)果。
　　 在第三章和第四章,主要討論如何推廣交互型移位排序的多項(xiàng)式時(shí)間算法,使之能夠處理包含不同尾基因集合的基因組。本文提出了給源基因組和目標(biāo)基因組分別添加元素使之包含相同的尾基因,從而用交互型移位排序模擬一般移位排序的思想。根據(jù)該思想,可得到一個(gè)指數(shù)時(shí)間算法。為了

10、改進(jìn)算法的時(shí)間復(fù)雜度,本文進(jìn)一步提出用添加元素后的同尾基因組的斷點(diǎn)圖構(gòu)造部分圖的方法,從而將問題轉(zhuǎn)化為如何在部分圖中添加灰邊得到斷點(diǎn)圖,令其交互型移位距離最小。
　　 在第三章,給出了一般移位排序的OPT+2-近似算法,這里OPT是將源基因組轉(zhuǎn)化為目標(biāo)基因組所需的最少一般移位的次數(shù)。斷點(diǎn)圖中圈和最小子排列的數(shù)目是交互型移位距離公式中的重要參數(shù)。在該算法的設(shè)計(jì)中,通過討論部分圖中可能導(dǎo)致增加最小子排列的組合結(jié)構(gòu),給出一種在部分圖中

11、添加灰邊的方法,可令添加灰邊后的斷點(diǎn)圖的圈數(shù)盡可能多,最小子排列數(shù)盡可能少,從而使圈數(shù)和最小子排列數(shù)之差達(dá)到最大值。
　　 在第四章,給出了一般移位距離的精確計(jì)算公式以及一般移位排序的多項(xiàng)式精確算法。證明一般移位距離精確值的關(guān)鍵在于對(duì)交互型移位距離公式中的參數(shù)f的討論。因?yàn)閒的取值與最小子排列數(shù)的奇偶性以及是否構(gòu)成偶隔離帶有關(guān),因而是精確計(jì)算一般移位距離的一個(gè)難點(diǎn)。在該算法的設(shè)計(jì)中,通過進(jìn)一步研究部分圖的性質(zhì),發(fā)現(xiàn)了四種可能導(dǎo)致

12、偶隔離帶的組合結(jié)構(gòu)。根據(jù)這四種結(jié)構(gòu)定義了新的參數(shù),從而證明了一般移位距離的一個(gè)精確下界。最后給出一種往部分圖中添加灰邊的方法,使添加灰邊后的斷點(diǎn)圖的交互型移位距離可以達(dá)到這個(gè)下界。
　　 (2)有向基因組的反轉(zhuǎn)和移位排序問題。
　　 Hannenhalli曾通過將該問題歸約到有向基因組反轉(zhuǎn)排序問題,給出該問題的一個(gè)多項(xiàng)式時(shí)間算法。算法中將源基因組的多條染色體連接為一個(gè)排列,用排列上的一個(gè)反轉(zhuǎn)模擬原來基因組上的一個(gè)內(nèi)反轉(zhuǎn)或

13、交互型移位。由于該算法中每個(gè)反轉(zhuǎn)或移位都是由一個(gè)反轉(zhuǎn)來模擬的,因而在排序過程中不能將反轉(zhuǎn)和移位區(qū)分開。Ozery-Flato曾在論文中提到,能在排序時(shí)明確區(qū)分反轉(zhuǎn)和移位這兩種操作的多項(xiàng)式算法,比Hannenhalli的算法更加自然和實(shí)用。
　　 在第五章,給出了可在排序時(shí)區(qū)分反轉(zhuǎn)和移位這兩種操作的新的多項(xiàng)式算法,從而對(duì)Ozery-Flato提出的問題給予了肯定的回答。斷點(diǎn)圖中結(jié)的數(shù)目是影響反轉(zhuǎn)和移位距離的重要參數(shù)。若斷點(diǎn)圖中不包

14、含結(jié),則可利用已有的反轉(zhuǎn)排序和移位排序的理論在多項(xiàng)式時(shí)間內(nèi)求解該問題。因而,算法設(shè)計(jì)的關(guān)鍵在于如何找一個(gè)合理的反轉(zhuǎn)和移位序列消除斷點(diǎn)圖中所有的結(jié)。
　　 本文的創(chuàng)新點(diǎn)可歸納如下:
　　 (1)首次考慮了當(dāng)源基因組和目標(biāo)基因組包含不同尾基因集合的一般移位排序問題,設(shè)計(jì)了一個(gè)OPT+2-近似算法。由該算法可得到一個(gè)將源基因組調(diào)整為目標(biāo)基因組的一般移位序列,且此序列的長(zhǎng)度與最優(yōu)序列的長(zhǎng)度之差不超過2。
　　 (2)首次