基于DNA序列的進化樹構(gòu)建算法的研究.pdf

1、進化樹又稱為系統(tǒng)發(fā)生樹，是一種用來描述各種生命實體之間進化關(guān)系的樹型結(jié)構(gòu)。一個可靠的進化樹推斷不僅有助于了解生物的進化歷史和進化機制，而且對生物醫(yī)藥學(xué)、計算分子生物學(xué)其他分支的研究具有重要意義。
　　目前常見的進化樹構(gòu)建方法有距離法、最大簡約法和最大似然法三種。其中，最大似然法被認(rèn)為比其他兩種方法更為準(zhǔn)確，但是其計算復(fù)雜度非常高。為了提高最大似然法，本文從以下4個方面展開了深入研究：
　　(1)提出了一個快速高效的分支交換操

2、作
　　由于計算復(fù)雜度非常高，實際應(yīng)用中的最大似然法都是基于啟發(fā)式的。雖然不同的啟發(fā)式算法具有不同的搜索策略，但是其基本思路都是通過一系列的分支交換操作來提高起始進化樹。并且，啟發(fā)式算法的性能在一定程度上取決于其所采用的分支交換操作的搜索能力。目前常見的分支交換操作有NNI(Nearest Neighbor Interchange)， SPR(Subtree Prune and Regraft)和TBR(Tree Bisectio

3、n and Reconnection)，其中TBR的搜索空間最廣。但研究表明，TBR的搜索空間還不夠廣，容易陷入局部極優(yōu)。另一種分支交換操作p-ECR(p-Edge Contraction and Refinement)具有更廣的搜索空間，能夠在一定程度上避免局部極優(yōu)。但是由于計算復(fù)雜度非常高，p-ECR很少被使用。本文結(jié)合鄰接法和 p-ECR提出了一個分支交換操作 p-ECRNJ。p-ECRNJ的基本思想是利用鄰接法分解 p-ECR中

4、產(chǎn)生的未分解節(jié)點。這樣，每一次p-ECRNJ操作只需要O(p3)去分解未分解節(jié)點，而無須花費大量的時間去嘗試所有的可能(最多(2p＋1)!!)，從而大大降低了時間復(fù)雜度。對12組真實數(shù)據(jù)的測試結(jié)果表明基于 p-ECRNJ的進化樹構(gòu)建算法能夠在合理的時間內(nèi)找到比其他流行的算法更好的進化樹。并且，p-ECRNJ還可以有效地提高其他分支交換操作，如NNI。從而，證明了p-ECRNJ的有效性。
　　(2)提出了一種PSO的進化樹構(gòu)建算法<

5、br>　　爬山算法在進化樹重構(gòu)中得到了廣泛應(yīng)用并取得了一定的成功。但是由于進化樹的似然函數(shù)通常含有多個局部極優(yōu)解，而爬山算法沒有逃離局部極優(yōu)的能力，因此基于爬山算法的進化樹構(gòu)建算法很容易陷入局部極優(yōu)。從本質(zhì)上講，粒子群優(yōu)化算法(Particle Swarm Optimization,簡稱PSO)是一種并行的、動態(tài)的爬山算法，具有一定的逃離局部極優(yōu)的能力。本文提出了一個基于 PSO的進化樹構(gòu)建算法 PSOML。該算法采用 PSO的基本框架

6、，利用 p-ECRNJ完成粒子狀態(tài)的更新，其中p值是根據(jù)粒子的速度確定的。對真實數(shù)據(jù)的測試結(jié)果表明雖然要花費較長的時間，PSOML的準(zhǔn)確性要明顯優(yōu)于基于爬山算法的PHYML和RAxML。并且，PSOML可以在合理的時間內(nèi)找到比基于遺傳算法GARLI更好的進化樹。
　　(3)結(jié)合Quartet puzzling和鄰接法提出了一種進化樹構(gòu)建方法
　　由于最大似然法的時間復(fù)雜度非常高，基于分治思想的最大似然法——quartet方法

7、得到了人們的關(guān)注。最流行的 quartet方法是 Quartet Puzzling(簡稱QP)。它首先利用最大似然法估計quartet拓撲結(jié)構(gòu)集合Q，然后利用一個貪心算法將 Q進行重組構(gòu)成一個包含所有序列的進化樹。研究表明，QP的準(zhǔn)確性不夠高，甚至比鄰接法還要低。如何快速有效地將 Q進行重組是 QP所面臨的一個難題。另一方面，鄰接法具有很好的理論特性，但其準(zhǔn)確性取決于作為輸入的距離矩陣的質(zhì)量。長分支一直是困擾鄰接法的一個問題。本文結(jié)合鄰

8、接法和 QP提出了一個進化樹構(gòu)建算法 QPNJ。QPNJ的基本思想是首先用最大似然法估計 quartet拓撲結(jié)構(gòu)集合 Q，然后根據(jù) Q估計序列之間的進化距離，構(gòu)成距離矩陣 M，最后利用鄰接法根據(jù) M構(gòu)建進化樹。QP和鄰接法的這種結(jié)合會達到取長補短的效果。一方面利用更有理論依據(jù)的鄰接法完成 Q的重組可以提高 QP的準(zhǔn)確性，另一方面利用 quartet估計序列之間的進化距離可以在一定程度上避免鄰接法所面臨的長分支問題。理論上， QPNJ與Q

9、P具有相同的時間復(fù)雜度。需要指出的是，鄰接法和QP的結(jié)合不是唯一的，任意類似于鄰接法的聚類過程如Weightor都可以按照QPNJ的思想代替鄰接法與 QP相結(jié)合。模擬實驗表明，QPNJ和 QPWNJ(結(jié)合了Weightor與 QP)比 QP更加準(zhǔn)確，甚至比鄰接法和 Weightor還準(zhǔn)確。并且， QPNJ和 QPWNJ的準(zhǔn)確性不像 QP一樣依賴于模型樹的結(jié)構(gòu)。從而證明了QP與聚類算法如鄰接法和Weighbor的結(jié)合是有效的。
　　

10、(4)結(jié)合同倫方法和SEM提出了一種進化樹構(gòu)建算法
　　根據(jù)當(dāng)前物種構(gòu)建進化樹是一個典型的從非完全數(shù)據(jù)學(xué)習(xí)的問題。結(jié)構(gòu)期望最大化(Structural Expectation Maximization，簡稱 SEM)算法是一個根據(jù)不完全數(shù)據(jù)求解模型結(jié)構(gòu)的有效方法，它通過迭代交替搜索的簡單方式能夠簡化最大似然估計問題。但是，由于 SEM算法直接采用貝葉斯公式計算隱變量的條件概率，使得每次迭代的結(jié)果都是上次迭代中期望似然值的最優(yōu)解，因

11、此算法對于初始點的選擇具有很強的依賴性。尤其是進化樹的似然函數(shù)往往具有多個局部極優(yōu)解，所以直接利用 SEM構(gòu)建進化樹很容易陷入局部極優(yōu)。同倫方法是一個全局方法，其基本思想是構(gòu)造一個同倫函數(shù)將一個已知解的問題與待解問題聯(lián)系起來，然后從已知解的問題開始，利用同倫參數(shù)的變化，最終求得待解問題的最優(yōu)解。本文結(jié)合同倫方法和 SEM提出了一種進化樹構(gòu)建算法HSEMPHY。HSEMPHY首先利用最大熵原理計算隱變量的條件概率，引入同倫參數(shù)β，然后借鑒