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

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

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

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

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

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

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

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

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

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

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

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

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

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

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