無(wú)向基因組的移位排序算法.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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