基于距離的進(jìn)化樹(shù)構(gòu)建算法研究.pdf

1、進(jìn)化樹(shù)是描述物種進(jìn)化順序和進(jìn)化關(guān)系的一種拓?fù)浣Y(jié)構(gòu)。構(gòu)建進(jìn)化樹(shù)在生物學(xué)中有重要的應(yīng)用，研究高效準(zhǔn)確的構(gòu)建進(jìn)化樹(shù)算法有實(shí)際的應(yīng)用價(jià)值。
　　本文針對(duì)進(jìn)化樹(shù)構(gòu)建問(wèn)題進(jìn)行研究。進(jìn)化樹(shù)構(gòu)建問(wèn)題是一個(gè)NP完全問(wèn)題，因而構(gòu)建算法都是啟發(fā)式的。通常使用的方法分為三大類(lèi)：(1)距離法，(2)最大簡(jiǎn)約法，(3)最大似然法。本文使用基于最大似然法的距離法構(gòu)建進(jìn)化樹(shù)，主要分為兩個(gè)階段：首先估計(jì)所有分類(lèi)群之間的進(jìn)化距離，只有序列進(jìn)化距離越精確，構(gòu)建的進(jìn)化樹(shù)

2、才會(huì)越準(zhǔn)確；然后基于這些距離值之間的關(guān)系構(gòu)建進(jìn)化樹(shù)。本文工作主要包括以下兩個(gè)階段：
　　在第一階段，對(duì)距離估計(jì)方法和最大似然法進(jìn)行了研究，改變了傳統(tǒng)的進(jìn)化距離估計(jì)方法，把序列比對(duì)由兩個(gè)序列比對(duì)擴(kuò)大到多重序列比對(duì)；利用基于quartet的最大似然法對(duì)進(jìn)化模型進(jìn)行優(yōu)化并使用最小二乘法快速重構(gòu)所有可能的quartet拓?fù)浣Y(jié)構(gòu)，并優(yōu)化其分支長(zhǎng)度，對(duì)兩兩序列間距離進(jìn)行估計(jì)，為進(jìn)化樹(shù)的構(gòu)建提供了更加準(zhǔn)確的距離矩陣。在第二階段，主要對(duì)鄰接法構(gòu)建

3、進(jìn)化樹(shù)進(jìn)行改進(jìn)，改進(jìn)工作分為兩部分：一是針對(duì)在第一階段得到的距離矩陣并不總是滿足可加性的問(wèn)題，引入了距離的方差和協(xié)方差，采用加權(quán)的計(jì)算公式更新距離矩陣，使算法構(gòu)建的拓?fù)浣Y(jié)構(gòu)更加準(zhǔn)確。二是改進(jìn)了鄰接法的貪心特性，由于鄰接法每次只聚合速率校正距離最小的兩個(gè)分類(lèi)單元，進(jìn)而導(dǎo)致整個(gè)體系的偏差，實(shí)驗(yàn)證明速率校正距離最小的配對(duì)并不一定是在真實(shí)的進(jìn)化樹(shù)中進(jìn)化距離最近的，基于此，改進(jìn)算法每次聚合速率校正距離滿足“neighbor”的兩個(gè)分類(lèi)單元，使算法