基于最近鄰交換樹操作的基因復(fù)制與丟失算法研究.pdf

1、現(xiàn)存的物種間由于遺傳因素，存在基因上的聯(lián)系，可以根據(jù)這些關(guān)聯(lián)信息構(gòu)建一棵物種樹，用來反映它們之間的進(jìn)化關(guān)系。隨著現(xiàn)代科技的發(fā)展，發(fā)現(xiàn)了越來越多的基因組序列的信息。這些基因組序列信息可以為我們研究物種演化史提供大量的、潛在的數(shù)據(jù)。根據(jù)從物種中得到的基因組序列信息而構(gòu)建的一組樹，稱之為基因樹。其中基因組序列的演化史模擬了物種的演化史。在進(jìn)化過程中，有大量的基因復(fù)制和丟失現(xiàn)象，所以根據(jù)基因信息所構(gòu)建的進(jìn)化樹可能并不能正確的表達(dá)與之對應(yīng)的物種之

2、間的進(jìn)化歷史，在構(gòu)造實際的最優(yōu)物種樹時需要根據(jù)一定的標(biāo)準(zhǔn)考慮這些因素所造成的影響。
　　 構(gòu)建物種樹的問題是一個基礎(chǔ)科學(xué)問題，而這個問題已被Ma Bin等人證明為NP-hard問題，所以為了有效地解決這個問題，在實際應(yīng)用中，需要采用一些啟發(fā)式算法來找到一棵較優(yōu)的物種樹，現(xiàn)存的啟發(fā)式都是通過執(zhí)行一些局部搜索算法來實現(xiàn)的。
　　 基因復(fù)制與丟失問題都是基于M. Goodman等人提出的模型的，在此基礎(chǔ)上，M.S．Bansal

3、等人設(shè)計了一系列的啟發(fā)式算法，以便能夠應(yīng)用到實際物種進(jìn)化研究中。這些啟發(fā)式都是通過對一棵物種樹執(zhí)行某個樹操作得到一個樹空間集合，然后計算這個集合里的每一棵樹的特征值，最后在這個樹空間集合里執(zhí)行局部搜索來找到局部最優(yōu)解。目前常見的樹操作有三種：NNI(the rooted nearestneighbour interchange),SPR(the rooted subtree pruning and regrafting)和TBR(the

4、rooted tree bisection and reconnection)。基于NNI，SPR和TBR的基因復(fù)制問題的算法已分別被優(yōu)化到O(kmn)，O(kmn)和O(kmnlogm)，而基于SPR,TBR的基因丟失算法也已被優(yōu)化到O(kmn)和O(kmn2)。
　　 本文在原有研究的基礎(chǔ)上，主要優(yōu)化了兩個問題。
　　 (1)提出了一個解決1-NNI基因復(fù)制問題的新算法，通過對基因樹中的節(jié)點進(jìn)行分類與分析，消除了許多