關于部分排序的基因組重組問題的研究.pdf

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

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

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

4、符號基因組的重組問題，重組操作在改變基因序列的同時也改變基因的符號；對于無符號基因組的重組排序問題，重組排序操作只改變基因序列，不會改變基因的符號。
　　 雖然基因組的重組過程十分復雜，但是只存在幾種基本的操作：反轉，移位和對換。通常情況下，基因組重組問題可以進行如下簡化：即假設基因組中不存在重復的基因。在這一簡化下，對于一個含有n個基因的基因組，通常用定義在｛1，2，…，n｝上的一個排列來表示。若一個基因組可以僅通過移位操作變

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

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

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

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

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

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