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

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

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