零抽樣斷點(diǎn)距離的一個(gè)改進(jìn)算法.pdf

1、基因組學(xué)出現(xiàn)于1980年，隨著幾個(gè)物種基因組計(jì)劃的啟動(dòng)，基因組學(xué)得到了很好的發(fā)展。近年來(lái)，隨著各種新技術(shù)的出現(xiàn)，基因組學(xué)更是進(jìn)一步的發(fā)展。海量的基因組數(shù)據(jù)從這些新技術(shù)中不斷的出現(xiàn)，面對(duì)爆炸性增長(zhǎng)的數(shù)據(jù)，我們急需要一種新方法來(lái)對(duì)這些數(shù)據(jù)進(jìn)行處理，比較基因組學(xué)應(yīng)運(yùn)而生。
　　比較基因組學(xué)中最重要的問(wèn)題之一就是抽樣斷點(diǎn)距離問(wèn)題。該問(wèn)題在文獻(xiàn)中已經(jīng)被廣泛的研究。抽樣斷點(diǎn)距離問(wèn)題描述為:對(duì)于兩個(gè)輸入基因組，找到它們各自的抽樣序列，使這兩個(gè)抽

2、樣的斷點(diǎn)距離最小。抽樣斷點(diǎn)距離問(wèn)題的特殊版本為:兩個(gè)輸入基因組中每一個(gè)基因家族至多出現(xiàn)兩次，并且判定它們是否存在斷點(diǎn)距離是零的抽樣序列，即是否能歸約成相同的基因組。我們把這樣的問(wèn)題稱為零抽樣斷點(diǎn)距離問(wèn)題，簡(jiǎn)稱為ZEBD(2，2)問(wèn)題。 Blin等人已經(jīng)證明零抽樣斷點(diǎn)距離問(wèn)題是NP-Hard的，并且不存在任何參數(shù)化的算法，即使每一個(gè)基因家族在一個(gè)基因組中至多出現(xiàn)兩次。
　　目前存在的判定ZEBD(2，2)問(wèn)題的算法中，時(shí)間復(fù)雜度最好

3、為O(n21.86121n)。在本文中，我們改進(jìn)了該算法，將時(shí)間復(fù)雜度提高到了O(n21.84931n)。如果抽樣圖中每一個(gè)基因家族構(gòu)成的子圖至多有兩條邊，可以在多項(xiàng)式時(shí)間內(nèi)判定出這兩個(gè)基因組是否存在斷點(diǎn)距離為零的抽樣。我們算法首先就是把兩個(gè)輸入基因組構(gòu)成的抽樣圖經(jīng)過(guò)處理，使其滿足每一個(gè)基因家族構(gòu)成的子圖至多有兩條邊。我們通過(guò)窮舉達(dá)到這樣的目的。我們算法就是通過(guò)減少窮舉的次數(shù)，提高了時(shí)間復(fù)雜度。具體方法為:我們同時(shí)分析兩個(gè)基因家族構(gòu)成的