計算生物學(xué)中基因組重組排序問題的算法研究.pdf

1、計算生物學(xué)是現(xiàn)今世界的熱門學(xué)科，計算生物學(xué)研究的有關(guān)成果直接影響著人類在生物進化、基因制藥等領(lǐng)域的研究進展。生物學(xué)、化學(xué)、數(shù)學(xué)、計算機科學(xué)等各領(lǐng)域?qū)＜覍W(xué)者都在關(guān)注著計算生物學(xué)的發(fā)展。 20世紀(jì)80年代末，Jeffrey Palmer及其同事在對比甘藍與蕪菁甘藍的基因序列時發(fā)現(xiàn)，排列形成兩種基因序列的分子幾乎完全相同，只是這些分子在兩種基因中的排列順序不一樣．這一發(fā)現(xiàn)以及其后的研究表明，基因重組是生物演化過程中的一個基本特征，是微

2、生物、植物、動物進化的一種重要模式．自此以后，與基因重組有關(guān)的技術(shù)與理論研究成為計算生物學(xué)研究中的一個熱點，其在生物種族進化研究、生物分類學(xué)研究、生物制藥研究等研究領(lǐng)域中顯示出重要的研究價值。 一條染色體由一個基因序列組成，一個基因組是染色體的集合。顯然，染色體可以看作是由單條染色體構(gòu)成的基因組?；蛐蛄锌梢猿示€狀(1inear)或環(huán)狀(circular)分布。若基因序列中每個基因的方向是已知的，則稱此序列是帶符號的(signe

3、d)，否則稱為無符號的(unsigned)。同理可定義帶符號的基因組和無符號的基因組。雖然基因組的重組過程十分復(fù)雜，但是只存在幾種基本的操作。在變異的過程中，這幾種變換為；反轉(zhuǎn)(reversal)，移位(translocation)和對換(transposition)。生物物種之間的進化實際上就是生物基因的變異過程。生物之間的進化關(guān)系可以通過基因組之間的變換來描述。給定兩個基因組Ⅱ和г，在規(guī)定了可以使用的變換的集合之后，尋找從Ⅱ到г的最

4、短的變換序列的問題稱為基因組重組排序問題。一般情況下，基因組重組排序問題可以進行以下的簡化：即假設(shè)基因組中不存在重復(fù)的基因。在這一簡化下，對于一個含有n個基因的基因組，我們通常用一個定義在{1，2…，n}上的排列(n-排列)來表示。若此基因組含有多個染色體，這個n-排列將被分成多個連續(xù)的“塊”，其中每個塊表示一個染色體。 基因組的重組排序問題在近幾年得到了廣泛的研究，已有大量的結(jié)果。對應(yīng)的三種不同的操作的排序問題難度有所不同。反

5、轉(zhuǎn)操作是將一個基因序列的一個子序列的順序反轉(zhuǎn)過來，對帶符號的基因序列則同時改變子序列中每個基因的符號。帶符號基因序列的反轉(zhuǎn)排序問題已證明有多項式時間算法[21]，后人則努力降低算法運行的時間[22，23，24]，目前最快的算法可在(二)(n平方根nlogn)時間內(nèi)完成[24]。而無符號基因序列的反轉(zhuǎn)排序問題已證明是NP-hard的[19]。Christie[17]給出了此問題的一個1。5-近似算法，目前該問題最好的近似算法是P.Berm

6、an等人給出的1.375-近似算法[18]．移位操作是將兩個基因序列分別在某處斷開，再將分屬兩個基因序列的子序列重新連接起來，形成兩個新的基因序列。帶符號基因組的移位排序問題有多項式時間算法[33，35，36]。無符號基因組的移位排序問題的復(fù)雜性一直以來都沒有得到解決，直到最近朱大銘和王魯生證明此問題也是NP-hard的[38]，目前該問題最好的近似比是1.75[40]．對換操作是將一個基因序列中的兩段相鄰的子序列交換位置。對于對換排序

7、問題，已有多個1.5-近似算法[28，29，31]，此問題目前最好的近似比為1.375[32]，但它的復(fù)雜性仍然未知。本文主要對以下三個與基因組重組排序有關(guān)的問題進行了研究： (1)帶符號基因序列的固定長度的反轉(zhuǎn)排序問題。 (2)無符號基因序列的賦權(quán)對換排序問題． (3)帶符號基因組的移位、刪除(或移位、插入)排序問題。 下面我們逐一說明這些問題并列出我們的主要成果。帶符號基因序列的固定長度的反轉(zhuǎn)排序

8、問題“傳統(tǒng)”的反轉(zhuǎn)排序問題在排序過程中允許任何長度的反轉(zhuǎn)，與之對應(yīng)的就是反轉(zhuǎn)排序的“限制”模型，即只允許滿足一定條件的反轉(zhuǎn)。在1996年，Chen和Skiena[42]將這種條件定義為“長度為后”，即在反轉(zhuǎn)過程中只允許長度正好為k的反轉(zhuǎn)(記為k-反轉(zhuǎn))，研究了對無符號的長度為n的排列(記為n-排列)進行排序的問題。實際上，并不是所有的n-排列都可以被k-反轉(zhuǎn)調(diào)整為(1，2，3，…,n)，相反的，若僅通過k-反轉(zhuǎn)，某個n-排列可能永遠不會

9、被調(diào)整為另一個n-排列．例如，以(1，3，2)開頭的所有的n-排列(1，3，2，…)不可能通過3-反轉(zhuǎn)調(diào)整為(1，2，3，…，n)，因為3-反轉(zhuǎn)總是交換具有相同奇偶性的位置上的元素。若兩個n-排列可以通過k-反轉(zhuǎn)相互得到，則我們稱他們在k-反轉(zhuǎn)下屬于同一個等價類。在[42]中，Chen和Skiena對所有無符號的n-排列(線狀或環(huán)狀)被k-反轉(zhuǎn)劃分的等價類進行了詳細的刻畫。并且，他們提出了下面的open問題：帶符號的n-排列在k-反轉(zhuǎn)下

10、的等價類是什么樣的? 的確，因為帶符號基因序列上的反轉(zhuǎn)不僅改變基因的順序，而且要改變基因的符號，這使得此問題變得很困難。例如，帶符號的n-排列(+1，+3，+2，+4，．．．，+n)不可能通過2-反轉(zhuǎn)變換為(+1，+2，+3，+4，．．．，+n)，但當(dāng)不考慮他們的符號時，是可以的。在第二章中，當(dāng)k是偶數(shù)的時候，我們解決了這個歷時10年的問題．對帶符號的n-排列(線狀或環(huán)狀)在k-反轉(zhuǎn)下的等價類進行了詳細的刻畫．主要結(jié)果可見下

11、表，其中N<,1>(k，n)表示所有帶符號的n-線狀排列在k-反轉(zhuǎn)下的等價類的個數(shù)，N<,c>(k，n)表示所有帶符號的n-環(huán)狀排列在k-反轉(zhuǎn)下的等價類的個數(shù)． 當(dāng)k是奇數(shù)的時候，此問題仍然沒有得到解決，值得我們進一步的研究。無符號基因序列的賦權(quán)對換排序問題 以往對基因序列的對換排序問題或者反轉(zhuǎn)排序問題的研究都基于這樣的假設(shè)：每步操作的消費是單位費用1，而與操作的長度(即其作用的片斷的長度)無關(guān)．這樣的假設(shè)，在生物學(xué)上并不完全具

12、有實際意義．實驗表明，操作的長度在進化過程中扮演了重要的角色，某種操作發(fā)生的概率依賴于其作用的片斷的長度．自然的，人們開始將操作的長度考慮在內(nèi)，將操作的費用定義為是它的長度的函數(shù)，而一個操作序列的費用則是序列中所有操作的費用之和。賦權(quán)的反轉(zhuǎn)排序問題就是求將序列Ⅱ變成г的費用最小的反轉(zhuǎn)序列，此問題在[44，45，46]中已有深入研究。 受賦權(quán)反轉(zhuǎn)排序問題的啟發(fā)，在第三章我們考慮賦權(quán)的對換排序問題。這是首次對對換排序問題考慮賦權(quán)模型

13、．我們考慮了一類消費函數(shù)，即f(ι)=ι<'α>，這里α≥0，ι表示對換的長度。對不同的α值，我們分別給出了相應(yīng)的足夠?qū)⑷魏?/1序列調(diào)整為0…01…1或者將任何n．排列調(diào)整為(1，2，．．．，n)的最小費用的上下界。當(dāng)0≤α<1，α=1和1<α<2時，我們給出了相應(yīng)的賦權(quán)對換排序問題的近似算法；當(dāng)α≥2時，我們證明Bubble sort是此問題的O(n<'2>)精確算法。我們的結(jié)果歸納在下表，其中佗表示序列的長度。對換的賦權(quán)模型使人

14、們更深入的了解對換在基因重組過程中如何發(fā)揮作用。帶符號基因組的移位、刪除(或移位、插人)排序問題基因組移位距離是多條基因序列組成的基因組(源基因組)通過移位操作變換為另一個基因組(目標(biāo)基因組)所需的最少的變換次數(shù)，它是揭示生物種族之間親緣關(guān)系疏密程度的一個重要指標(biāo)．該指標(biāo)對生物種族進化研究具有重要意義。帶符號基因組間移位排序問題的多項式時間算法首先由Hannenhalli給出[33]，但遺憾的是，Hannenhalli給出的這個算法，調(diào)

15、整策略上存在著錯誤．在2005年，AnneBergeron等人[36]重新研究丁這個問題，并給出了一個正確的移位排序算法。 值得注意的是，一個基因組若可以僅通過移位操作變換為另一個基因組，那么這兩個基因組首先必須有相同的基因集合。即移位排序算法“工作”的前提是輸入的基因組有相同的基因集合。但在生物學(xué)實際中，這種情況非常少見。所以我們需要考慮一般的情形：即當(dāng)兩個基因組含有不同的基因集合時。很明顯，在這種情況下，“插入”或“刪除”將

16、成為必需的操作。我們的目標(biāo)仍然是通過最少的操作(移位、插入或刪除)，將源基因組Ⅱ變換為目標(biāo)基因組D。 將在Ⅱ和D中都出現(xiàn)的基因集合記作A，將只出現(xiàn)在Ⅱ中和只出現(xiàn)在D中的基因集合分別記作AⅡ和AD．我們假設(shè)A中的基因在Ⅱ和r中都只出現(xiàn)一次。在第四章，我們將考慮如何推廣移位排序問題的多項式時間算法，使之能夠處理含有不同基因集合的基因組Ⅱ和r。當(dāng)An≠θ，Ar=θ時，我們給出了此問題的一個漸進最優(yōu)的近似算法。由此算法得到的操作(移位

17、、刪除)序列的長度至多為OPT+2，這里OPT是將基因組Ⅱ變換為D所需的最少的操作(移位、刪除)的個數(shù)．并且，只需將Ⅱ和r的角色互換，此算法也可用來處理當(dāng)A<,Ⅱ>=θ，Ar≠θ時的情形(即通過最少的移位和插入將Ⅱ變換為r)。 本文的主要結(jié)果和創(chuàng)新點歸納如下： (1)部分解決了1996年Chen和Skiena提出的open問題。當(dāng)k是偶數(shù)時，對帶符號的n－排列(線狀或環(huán)狀)在к－反轉(zhuǎn)下的等價類進行了詳細的刻畫。

18、 (2) 首次提出了對換排序的賦權(quán)模型。考慮了一類消費函數(shù)：f(l)＝l,<'α>，這里α≥0，l表示對換的長度，對不同的α值，分別給出了足夠調(diào)整任何排列或任何0/1序 列的最小費用的上下界；同時對不同的α值，給出相應(yīng)的賦權(quán)對換排序問題的 近似或精確算法。賦權(quán)模型的建立，為更好的了解對換在基因進化過程中發(fā)揮 的作用提供了一個新的思路。 (3) 首次考慮了當(dāng)“源”基因組和“目標(biāo)”基因組包含不同的基因集合時的移位排序 問題。