無向基因組的移位排序算法.pdf

1、隨著基因測序技術(shù)的飛速發(fā)展，對大規(guī)模DNA分子的研究與它們的基因序列密切相關(guān)?；蚪M重組排序已經(jīng)成為計算生物學(xué)和生物信息學(xué)的重要研究領(lǐng)域。許多研究表明，基因組重組是生物進(jìn)化的一種普遍模式，也是植物、哺乳動物及細(xì)菌等呈現(xiàn)多樣性的主要原因之一。 有三種典型的基因組重組操作：反轉(zhuǎn)(Reversal)、移位(Translocation)和轉(zhuǎn)位(Transposition)，一次重組將一個基因組轉(zhuǎn)化為一個新基因組。反轉(zhuǎn)與轉(zhuǎn)位操作總是作用在

2、單條染色體上，而移位操作則作用在兩條染色體上。給定兩個基因組，重組排序問題是要計算一個重組操作序列，將其中一個基因組轉(zhuǎn)化為另一個，并使得重組操作次數(shù)最少?；诜肿由飳W(xué)積累的實(shí)驗數(shù)據(jù)驗證，重組操作次數(shù)最少的操作序列被認(rèn)為是能較好地估計物種間的親緣關(guān)系，有助于推斷生物的實(shí)際進(jìn)化過程。 基因組是一組染色體的集合，一條染色體是一個基因序列，表示為一個整數(shù)序列。每個基因都有方向。當(dāng)每個基因的符號都是已知的時候，用帶符號的整數(shù)表示有向基因

3、組中的基因。當(dāng)基因符號都是未知時，用正整數(shù)表示無向基因組中的基因。對于有向基因組的重組排序問題，重組排序操作在改變基因序列的同時也改變基因的符號；對于無向基因組的重組排序問題，重組排序操作只改變基因序列，不會改變基因的符號。 對于有向基因組的移位排序問題，Hannenhalli設(shè)計出O(n3)多項式時間精確算法，并給出有向移位距離的求解公式。隨后，Zhu等將算法的時間復(fù)雜度改進(jìn)為O(n2logn)，Wang等進(jìn)一步改進(jìn)為O(n2

4、)。Zhu等證明無向基因組移位排序問題也是NP-hard問題。Kececioglu和Ravi給出一個近似度為2的貪心算法，是目前該問題的最好算法。雖然有向基因組的移位排序已經(jīng)有一些多項式時間算法，但是許多基因組數(shù)據(jù)并未給出基因方向，因此研究無向移位排序算法也具有十分重要的價值。 本文主要研究無向基因組的移位排序問題，即給定兩個無向基因組，求最少次數(shù)的移位操作序列，將其中一個基因組轉(zhuǎn)換為另一個。移位操作是將兩條染色體分別斷開，再重

5、新連接成兩條新的染色體。移位操作又可分為前前移位和前后移位兩種，前前移位不改變基因的符號，而前后移位可能會將基因的符號取反。目前該問題的最好算法是由Kececioglu和Ravi給出的近似度為2的貪心算法，將無向基因組移位問題轉(zhuǎn)化為交換字符串的前綴和后綴。本文應(yīng)用最大匹配算法及斷點(diǎn)圖圈分解的一些特性，先后給出了近似度為1.75和1.5的O(n2)多項式時間近似算法。 斷點(diǎn)圖是基因組重組排序算法研究的基本工具。與有向斷點(diǎn)圖只有唯一

6、的圈分解不同，無向斷點(diǎn)圖可以有多種圈分解，一個圈分解實(shí)際是給每個基因指定一個符號。求無向基因組移位距離的一個方法是：嘗試各種可能的圈分解，為每個基因指定符號，然后計算各個圈分解對應(yīng)的有向基因組的移位距離，選取其中的最小值。顯然，該枚舉方法并不適用于給定基因組包含較多基因的情況。 如果對無向基因組給出一個較好的圈分解，則可以獲得一個移位距離的較好近似解。本文算法的主要思想是給出無向斷點(diǎn)圖一個較優(yōu)的圈分解，包含最多的長度為1的圈及足

7、夠多長度為2的圈。最小子排列是斷點(diǎn)圖中的一種特殊結(jié)構(gòu)，根據(jù)有向移位距離公式，較多的圈數(shù)和較少的最小子排列數(shù)目都有助于求得更小的移位距離，本文提出了可消減最小子排列概念，應(yīng)用于圈分解算法中，在增加圈分解數(shù)目的同時，盡量不產(chǎn)生新的最小子排列，從而保證了所給無向移位排序算法的近似度。 本文可分為三個部分：在第一章中概述基因組重組排序的基本概念及算法，包括反轉(zhuǎn)、移位和轉(zhuǎn)位排序及多種操作排序。在第二章中給出了近似度為1.75的近似算法。我

8、們的算法使用最大匹配方法找一個斷點(diǎn)圖圈分解，包含足夠多的長度為2的圈；根據(jù)圈分解算法為每一個無符號基因指定符號，從而把無向基因組移位重組的排序問題，轉(zhuǎn)化為有向基因組重組排序的移位問題，可以應(yīng)用已存在的有向基因組多項式算法求解。最小子排列數(shù)目是有向基因組移位距離公式中的一個重要參數(shù)。為了證明了算法的近似度，本章提出了可消除最小子排列的概念，對最優(yōu)圈分解中的候選最小子排列進(jìn)行消除處理，從而證明了該算法具有1.75倍的近似度。在第三章中，我們

9、給出了一個近似度為(1.5+ε)的近似算法，此處ε≥0是任意小的常數(shù)。我們的新算法在可消除最小子排列的概念基礎(chǔ)上，在圈分解算法中對短RS-MSP(短的可消除的簡單最小子排列)作了特別處理，這導(dǎo)致了一個較好的近似比。 無向基因組移位排序的關(guān)鍵在于確定斷點(diǎn)圖的圈分解，根據(jù)有向移位排序距離計算公式，圈數(shù)較多的圈分解和較少的最小子排列數(shù)目都有可能幫助求得更小的移位距離。對無向斷點(diǎn)圖進(jìn)行圈分解的過程中，當(dāng)涉及到候選最小子排列時，分解出較多

10、的圈數(shù)經(jīng)常使得更多的候選最小子排列變成最小子排列，而通過改變基因符號減少最小子排列的數(shù)目，往往會同時減少可能分解出的圈數(shù)，這都無益于求移位距離。本文指出，在候選最小子排列滿足一定條件下，通過改變基因符號消除一個最小子排列后，可保持圈數(shù)不變，即可以在不減少圈數(shù)的同時減少最小子排列的數(shù)目，從而獲得一個較好的圈分解。 在1.75倍的近似算法設(shè)計中，通過對基因指定符號，先分解出最多數(shù)目的長度為1的圈，再應(yīng)用最大匹配方法求得不少于最大可能

11、數(shù)目一半的長度為2的圈，最后對其余的無符號基因任意指定符號而得到近似的圈分解。為了證明算法的近似度，首先假定一個最優(yōu)圈分解，在改變基因符號分解出最多數(shù)目的長度為1的圈后，處理其中可消除的候選簡單最小子排列。對有向移位距離公式中保留參數(shù)f如何處理，也是近似度證明的一個難點(diǎn)，因為f的取值與最小子排列的數(shù)目奇偶性及是否構(gòu)成偶數(shù)孤立排列相關(guān)。本文對和f取值相關(guān)的斷點(diǎn)圖情形進(jìn)行枚舉分析，從而完成1.75倍的近似度證明。 在(1.5+ε)倍

12、的近似算法設(shè)計中，如何處理1-2型最小子排列(包含的所有圈的長度為1或2)是算法設(shè)計的關(guān)鍵，因此定義了一種短的可消除簡單最小子排列(短RS-MSP)。消除一個短RS-MSP，斷點(diǎn)圖中長度為i(i≥1)的圈的數(shù)目保持不變，從而可以減少1-2型最小子排列的數(shù)目。在應(yīng)用最大匹配求解可能的長度為2的圈后，進(jìn)一步選擇孤立圈來構(gòu)造短RS-MSP。與1.75倍近似算法中的情形不同，構(gòu)造短RS-MSP可能使得最大匹配求解的某些長度為2的圈無法被選擇。該

13、算法采用了更優(yōu)化的圈分解算法法，保證了(1.5+ε)的近似度。 本文的創(chuàng)新點(diǎn)主要有三個：(1)對于無向基因組的移位問題，本文設(shè)計了近似度為1.75的多項式時間近似算法，好于當(dāng)前最好的近似度為2的算法。該算法應(yīng)用最大匹配方法，給出了無向斷點(diǎn)圖一個較優(yōu)的圈分解，包含最多1-cycle及足夠多2-cycle；(2)本文提出了可消減最小子排列的概念。在斷點(diǎn)圖中，消除一個可消減最小子排列，圈數(shù)保持不變，最小子排列數(shù)不會增加。根據(jù)有向移位距