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

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

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

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