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

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

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

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

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

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