關(guān)于部分排序的基因組重組問(wèn)題的研究.pdf

1、基因組重組是計(jì)算生物學(xué)和生物信息學(xué)的一個(gè)重要研究領(lǐng)域，許多研究表明，基因組重組是生物進(jìn)化的一種普遍模式，也是植物、哺乳動(dòng)物及細(xì)菌等呈現(xiàn)多樣性的主要原因之一。
　　 1938年，Dobzhansky和Sturtevant開(kāi)創(chuàng)了基因組重組的分子生物學(xué)分析，他們發(fā)表了里程碑式的論文，文中對(duì)果蠅基因組提出了含17次反轉(zhuǎn)操作的重組方案。就最簡(jiǎn)單的形式而言，將一種基因組轉(zhuǎn)換為另一種基因組的重組可以用尋找最小轉(zhuǎn)換次數(shù)的組合問(wèn)題來(lái)模擬。隨著大規(guī)

2、模作圖和測(cè)序的出現(xiàn)，在不同的領(lǐng)域內(nèi)有關(guān)基因組比較問(wèn)題的數(shù)目迅速增長(zhǎng)，這些領(lǐng)域包括病毒、細(xì)菌、酵母、植物和動(dòng)物的進(jìn)化。在20世紀(jì)80年代末，Jeffrey Palmer和他的同事們?cè)谥参锛?xì)胞器中發(fā)現(xiàn)了一種有關(guān)進(jìn)化變異不尋常的新的模式。他們比較了甘藍(lán)和蕪菁甘藍(lán)的線粒體基因組，兩者之間的聯(lián)系非常緊密(許多基因是99％同源的)。令他們感到驚奇的是，這些分子在基因序列上幾乎相同，但在基因排列次序上則有顯著的差別。這個(gè)發(fā)現(xiàn)和后來(lái)十年中許多其他的研究

3、令人信服地證明了基因組重組是分子進(jìn)化的一種模式。
　　 基因組是一組染色體的集合，一條染色體是一個(gè)基因序列，用一個(gè)整數(shù)序列來(lái)表示。每個(gè)基因都有方向。當(dāng)每個(gè)基因的方向在一個(gè)有符號(hào)基因組中是已知時(shí)，用帶符號(hào)的整數(shù)表示該基因組中的基因.當(dāng)基因的方向在一個(gè)無(wú)符號(hào)基因組中都是未知時(shí)，用不帶符號(hào)的整數(shù)表示該基因組中的基因。給定兩個(gè)基因組，重組排序問(wèn)題是要計(jì)算一個(gè)重組操作序列，將其中一個(gè)基因組轉(zhuǎn)化為另一個(gè)基因組，并使得重組操作次數(shù)最少。對(duì)于有

4、符號(hào)基因組的重組問(wèn)題，重組操作在改變基因序列的同時(shí)也改變基因的符號(hào)；對(duì)于無(wú)符號(hào)基因組的重組排序問(wèn)題，重組排序操作只改變基因序列，不會(huì)改變基因的符號(hào)。
　　 雖然基因組的重組過(guò)程十分復(fù)雜，但是只存在幾種基本的操作：反轉(zhuǎn)，移位和對(duì)換。通常情況下，基因組重組問(wèn)題可以進(jìn)行如下簡(jiǎn)化：即假設(shè)基因組中不存在重復(fù)的基因。在這一簡(jiǎn)化下，對(duì)于一個(gè)含有n個(gè)基因的基因組，通常用定義在｛1，2，…，n｝上的一個(gè)排列來(lái)表示。若一個(gè)基因組可以僅通過(guò)移位操作變

5、換為另一個(gè)基因組，那么首先這兩個(gè)基因組必須有相同的基因集合。但是在生物學(xué)實(shí)際中，這種情況非常少見(jiàn)。所以我們需要考慮一般的情形：即兩個(gè)基因組含有不同的基因集合時(shí)的情況。顯然，在這種情況下，“刪除”或“插入”將成為必需的操作。目標(biāo)仍然是通過(guò)最少的重組操作(移位、刪除或插入)，將源基因組轉(zhuǎn)化為目標(biāo)基因組。
　　 大部分比較基因組學(xué)研究假設(shè)一條染色體中的基因的排列次序是給定的，但是目前的基因圖譜技術(shù)，比如重組分析和物理成像等，經(jīng)常由于缺

6、乏解決的方法，使得基因圖譜中幾個(gè)基因位于同一個(gè)位置或者遺漏一些其它的基因，這就使得將它們結(jié)合起來(lái)僅能產(chǎn)生基因組的一個(gè)部分排序而不是全排序。
　　 本文主要研究部分排序的基因組重組問(wèn)題。分四章進(jìn)行討論：在第一章中概述基因組重組排序的基本概念及算法。
　　 第二章主要研究部分排序基因組斷點(diǎn)距離(PBD)問(wèn)題，即給定兩個(gè)含有相同基因集合的部分排序基因組п和г，分別找到п和г的一個(gè)可能的全序排列L(п)和L(г)，使得L(п)和

7、L(г)之間的斷點(diǎn)距離db(п，г)最小。在這一章中給出了計(jì)算兩個(gè)部分排序基因組之間斷點(diǎn)距離的一個(gè)O(n4)啟發(fā)式算法，其中n為所考慮基因組中基因的個(gè)數(shù)。文中，首先引入了一個(gè)新的組合優(yōu)化問(wèn)題-最小雙斷點(diǎn)集問(wèn)題(MDBVS)，并且給出了該問(wèn)題的一個(gè)2(m2+4m-3)-近似算法，其中m是分別構(gòu)成兩個(gè)部分排序的基因組所需要的最大基因圖譜的個(gè)數(shù)，然后根據(jù)PBD問(wèn)題和MDBVS問(wèn)題之間的關(guān)系，設(shè)計(jì)了解決PBD問(wèn)題的一個(gè)啟發(fā)式算法。它們之間的關(guān)系

8、由下面的定理給出：
　　 定理設(shè)｜MDBVS｜是最小的雙斷點(diǎn)集所含元素的個(gè)數(shù)，｜W｜是W中元素的個(gè)數(shù)，n表示п中所含基因的個(gè)數(shù)。則db(п，г)=n-1-｜W｜+｜MDBVS｜。
　　 由上述定理可以看出，如果｜W｜　　 在計(jì)算生物學(xué)中，

9、如果一組同源基因(即有一個(gè)共同祖先的基因)在兩個(gè)不同的物種中共同存在，則這些基因可能在共同的祖先那里是保持在一起的，并且在以后的進(jìn)化過(guò)程中也不被分開(kāi)。這樣的一組結(jié)合在一起的同源基因稱為公共區(qū)間。因此，最近又出現(xiàn)了另外一個(gè)組合優(yōu)化問(wèn)題，稱為完美排序問(wèn)題，它是指尋找一組最少的重組操作，使得當(dāng)由一個(gè)基因組轉(zhuǎn)化為另一個(gè)基因組時(shí)，這些重組操作不破壞所考慮基因組的公共區(qū)間。
　　 在第三章中，推廣了Bérard等人關(guān)于基因反轉(zhuǎn)完美排序問(wèn)題的

10、一個(gè)算法，考慮允許有刪除和限制條件的插入(即不允許有重復(fù)基因)操作的基因組完美重組問(wèn)題。
　　 在第四章中，研究了含有不同基因集合的部分排序基因組重組問(wèn)題，即給定兩個(gè)含有不同基因集合的部分排序的基因組，分別找到它們的一個(gè)可能的全排序，使得從一個(gè)全排序到另外一個(gè)全排序所需要的重組操作次數(shù)最少。顯然，在這種情況下，插入和刪除將成為必須的操作。在這一章中，推廣了zheng等人的算法，設(shè)計(jì)了一個(gè)解決允許有刪除和插入操作的部分排序基因組重