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

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

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

3、等人設計了一系列的啟發(fā)式算法，以便能夠應用到實際物種進化研究中。這些啟發(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)?；贜NI，SPR和TBR的基因復制問題的算法已分別被優(yōu)化到O(kmn)，O(kmn)和O(kmnlogm)，而基于SPR,TBR的基因丟失算法也已被優(yōu)化到O(kmn)和O(kmn2)。
　　 本文在原有研究的基礎上，主要優(yōu)化了兩個問題。
　　 (1)提出了一個解決1-NNI基因復制問題的新算法，通過對基因樹中的節(jié)點進行分類與分析，消除了許多