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

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

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

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