基于距離的進化樹構建算法研究.pdf

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

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

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