種系發(fā)生樹構建算法的研究.pdf

1、系統(tǒng)發(fā)生樹是描述物種進化順序和進化關系的一種拓撲結(jié)構。一個可靠的系統(tǒng)發(fā)生的推斷,將揭示出有關生物進化過程的順序,有助于我們了解生物進化的歷史和進化機制。
　　發(fā)生樹的構建問題是一個NP完全問題，因此，研究構造發(fā)生樹的近似最優(yōu)算法有著重要意義。目前常用的構建發(fā)生樹的方法有三種，即距離法、最大簡約法和最大似然法。
　　本文對距離法中的鄰接法進行了三點改進：1.使用更精確的進化模型來度量序列之間的距離，降低因模型而帶來的誤差；2.

2、通過隊列產(chǎn)生多個拓撲結(jié)構，解決了鄰接法只能產(chǎn)生一個拓撲結(jié)構的缺陷；3.引入回退機制，消除了距離法中負枝長的產(chǎn)生，得到的樹更準確。
　　對最大簡約法，引入遺傳算法的思想，提出了一種新的建樹算法，即遺傳簡約法，以簡約樹長作為適應值函數(shù)，隨機生成多個初始樹，逐步收斂到所要搜尋的解，即最大簡約樹。
　　對最大似然法，改進了一種新的啟發(fā)式搜索：隨機建立一棵初始樹，然后通過查看與當前最優(yōu)樹拓撲最近的樹，從中尋找更優(yōu)樹，不斷地更新當前最優(yōu)