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

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

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

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

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