零抽樣斷點距離的一個改進算法.pdf

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

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

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