24113.基于三參數模型的進化樹算法研究

1、基于三參數模型的進化樹算法研究重慶大學碩士學位論文學生姓名：陳桂芳指導教師：郭平教授專業(yè)：計算機應用技術學科門類：工學重慶大學計算機學院二O一一年四月重慶大學碩士學位論文中文摘要I摘要多種生物克隆實驗結果說明，存在于細胞核染色體中的DNA序列包含了該生命體的全部信息。生物序列進行序列比對后，所得結果包含了序列之間的關系和進化的信息，利用這些信息可以得到各個序列在進化過程中的親疏、遠近關系[1]。進化樹就是用來描述序列間進化關系的一種樹狀

2、拓撲結構。其中，樹的葉子結點代表各種生物序列，樹枝的長度表示生物間的進化距離。構建一個可靠的進化樹不僅可以推測出生物的進化過程，估計現(xiàn)存的各類生物間的進化關系，并且對于生物醫(yī)藥學、基因組學和病毒學等其他領域的研究也具有重要意義。目前常見的進化樹構建方法有三類：基于距離的方法、基于特征的方法和基于概率論的方法。距離矩陣法具有較為完善的統(tǒng)計理論基礎，算法簡單，目前應用最為廣泛。其中，鄰接法又因其具有較小的時間復雜度，且所獲得的進化樹總是替代

3、總數為最小的樹而優(yōu)于其他的距離矩陣算法。距離矩陣的構造是距離矩陣法的基礎，序列間的進化距離估計越精確，構建的進化樹才會更準確。因此選擇正確的進化模型來構建距離矩陣成了進化樹研究的重要內容之一。UPGMA算法[2]和鄰接法[3]都是傳統(tǒng)距離矩陣法，兩者都采用了JukesCant單參數模型來估算序列間的進化距離，該模型認為4種核苷酸ATC和G間的相互替換的速率相等。但在大多數DNA序列中，通常核苷酸轉換的比率要高于顛換的比率，而且真實的核苷

4、酸替代模型要比Jukes—Cant單參數模型復雜得多。因此在實際應用中，用JukesCant單參數模型來估計序列間的進化距離并不理想。鄰接法除了進化距離的估計影響其準確性外，它的聚類過程也是影響其準確性的一個重要方面。由進化模型估計得到距離矩陣后，鄰接法對其進行聚類計算來完成進化樹的構建，它要求在每一次聚類時盡量使得當前樹的所有分支長度之和最小。這個聚類過程是一個貪心過程，它求得的僅是局部最優(yōu)解，并非整體最優(yōu)解，求得的鄰居不一定是真正的

5、鄰居。也就是說鄰接法所構建的進化樹并不總是真實的進化樹，而有可能只是真實進化樹相近似的拓撲結構。為提高鄰接法構建進化樹的準確性，本文在基于三參數模型的進化樹構建算法（KTPMPT）中采用了Kimura三參數模型[4]來計算序列之間的進化距離，并給出了新的改進算法。論文中通過計算機模擬法，對KTPMPT算法、UPGMA算法和鄰接法的準確性進行了對比分析，實驗結果表明KTPMPT算法明顯優(yōu)于UPGMA算法和鄰接法。在基于最小生成樹的進化樹構