通常用系統(tǒng)樹來表示一組分類單元的進化關系，這一模式有利于假設的討論和檢驗。然而當描述更復雜的進化關系時，系統(tǒng)樹的功能則略顯不足。隨著研究的逐漸深入，科學家們發(fā)現有些物種在進化過程中發(fā)生了網狀進化事件，如反轉（reversal）、移位（translocation）和轉位（transposition）、重組（recombination）、水平基因轉移（horizontalgenetransfer，HGT）、雜交（hybridization）、基因轉移或者基因重復和丟失[1-6]等，則此時生物的父代即不止一個，系統(tǒng)樹不能描述各代之間的進化關系，因此促動了系統(tǒng)發(fā)生網絡（phylogeneticnetwork）的出現。系統(tǒng)發(fā)生網絡構建方法及理論分析的研究是計算生物學的一個重要方向。系統(tǒng)發(fā)生網絡是系統(tǒng)樹的一般形式，又可譯作系統(tǒng)演化網絡、系統(tǒng)進化網絡、進化網絡。該種網絡更適合那些發(fā)生了網狀進化事件的數據，而且，對于樹式進化模式（堿基的替代、插入、刪除等）進化而來的數據，系統(tǒng)發(fā)生網絡也可以實現數據中沖突信息的清晰表達，如由于不完全譜系分類機制或者是由于進化模型假設的不足引起的沖突信息[7]。系統(tǒng)發(fā)生網絡是一個無環(huán)圖，圖中有些節(jié)點的父節(jié)點個數≥2（這種節(jié)點也被稱為網絡節(jié)點），如果圖中沒有網絡節(jié)點，那么這時的系統(tǒng)發(fā)生網絡就是一棵樹。

　　摘要：物種的進化史通常被描述成一棵有根系統(tǒng)樹，但是當物種進化過程中發(fā)生網狀進化事件（如，雜交、重組和水平基因轉移）時，物種的進化史不再適合被描述成系統(tǒng)樹。系統(tǒng)發(fā)生網絡是系統(tǒng)樹的一般化，也是被用來描述物種的進化史，并可以描述物種的網狀進化事件。而且系統(tǒng)發(fā)生網絡也可以可視化沖突數據集，如由不同的基因得到的物種樹。因此，系統(tǒng)發(fā)生網絡的研究是生物信息的一個重要領域。介紹了系統(tǒng)發(fā)生網絡的概念、發(fā)展、研究現狀，總結了現有的系統(tǒng)發(fā)生網絡構建算法。

　　關鍵詞：系統(tǒng)發(fā)生網絡,網狀進化事件,隱式網絡,顯式網絡

　　0引言

　　系統(tǒng)發(fā)生網絡根據拓撲結構分為無根（unrooted）網絡和有根（rooted）網絡；根據功能分為隱式（implicit）和顯式（explicit）網絡[8]。隱式網絡（例如分割網絡和準中位數網絡）則可用來表示沖突信息，這些沖突信息可能來自各種原因，如模型誤設（modelmisspecification）；而顯式網絡則是盡力捕獲生物進化過程中的網絡進化事件，如雜交（hybridization）[9-10]、重組（recombination）[11-15]及水平基因轉移（horizontalgenetransfer，簡稱HGT）[7，16-18]。顯式網絡中的內部節(jié)點表示祖先物種，且其中的網絡節(jié)點對應所考慮的生物進化過程[14-16]，而隱式網絡中網絡節(jié)點沒有任何生物解釋。顯式網絡通常是有根的，因為生物進化過程本質上是有向的。然而有根系統(tǒng)發(fā)生網絡可能是隱式網絡，這取決于對相應網絡進行構建和解釋的具體方式[8]。

　　1無根系統(tǒng)發(fā)生網絡構建算法

　　無根系統(tǒng)發(fā)生網絡是無根樹的一般化。無根系統(tǒng)發(fā)生網絡都是隱式網絡，主要包括兩類：分割網絡（Splitnetwork）和準中位數網絡（Quasi-mediannetwork）。在無根系統(tǒng)發(fā)生網絡方面，分割（Split）的概念起了重要作用。下面將詳細給出分割的定義。

　　定義1設X是一物種集合，A和B是X的非空子集，且A∩B=和A∪B=X，則S=A|B稱為X的一個分割。

　　有時將分割A|B記為AB或者BA。分割S的大小記為size（S）=min{|A|，|B|}。大小為1的分割稱為是平凡的（trivial）分割，否則稱為非平凡的（non-trivial）分割。設T是X上的一棵無根系統(tǒng)樹，那么T上的每一邊定義了X的一個分割。

　　分割網絡可以從很多不同的數據集（如距離矩陣、無根系統(tǒng)樹集、序列及四分體）構建得到。從這些數據構建分割網絡時，大部分算法都是首先計算出一個加權分割集（這里的權重可能表示的是距離或者特征變化量等），然后再由此加權分割集得到分割網絡。由加權的分割集構建分割網絡主要有兩種方法：凸包算法（convexhull）[19]和圓形網絡算法（circularnetwork）[20]。對于任何一分割集，凸包算法都能為S構建一個無根系統(tǒng)發(fā)生網絡，且最壞情況是此網絡包含指數級的節(jié)點數和邊數。而圓形網絡算法構建的網絡僅包含平方級的節(jié)點數和邊數。

　　從距離矩陣得到加權分割集的方法主要有Neighbor-Net方法[21]和分割分解方法[22]。從無根系統(tǒng)樹構建加權分割集的主要方法有一致分割網絡（consensussplitnetwork）方法[23-24]和Z-閉包（Z-closure）算法[25-26]。軟件SpitlTree4[27]是一個用來推導無根系統(tǒng)發(fā)生網絡的非常方便的工具，此軟件可以從序列、距離、樹或者是分割來推導得出無根系統(tǒng)發(fā)生網絡，軟件中收集了很多方法，如Neighbor-net方法以及Z-閉包算法。第1期王娟，等：系統(tǒng)發(fā)生網絡構建算法綜述智能計算機與應用第4卷

　　2有根系統(tǒng)發(fā)生網絡構建算法

　　有根系統(tǒng)發(fā)生網絡分為顯式網絡和隱式網絡。顯式網絡理論上能很好地反映分類單元間的網狀進化事件，由于進化是有向的，所以顯式網絡是有根的。Maddison基于rSPR（rootedSubtreePruneandRegraft）距離構建了系統(tǒng)發(fā)生網絡[28]。Nakhleh等[29]對Maddison的算法作了改進，提出了構建含有一個網絡節(jié)點的系統(tǒng)發(fā)生網絡的多項式算法，且此算法通過對基因樹壓縮的方式考慮了基因樹中所帶有的誤差，使得此算法更具有實際應用價值。Wang等[30]及Gusfield等[31]提出了從序列特征構建重組系統(tǒng)發(fā)生網絡的算法。Hein[32]首次對構建系統(tǒng)樹的最大簡約法延伸到構建系統(tǒng)發(fā)生網絡上。此后，Nakhleh等[33]旨在促進系統(tǒng)發(fā)生網絡的構建和評估，而為每個網絡定義了最簡標準。文獻[33]中提出的算法Net2Trees可用來計算網絡的最簡值，Net2Trees算法的時間復雜度是指數級的。之后，Jin等[34]改進了這一Net2Trees算法，并提出了解決此問題的線性時間算法[35]。以上介紹的最大簡約法都是用相同的方式定義網絡的最簡值，都是將網絡包含的所有樹的最簡值的最小值作為此網絡的最簡值。Kannan等[36]提出了另一種網絡最簡值的定義，即可定義為網絡所有邊的替換代價之和，并將計算系統(tǒng)樹最優(yōu)簡約值（optimumparsimonyscore）的Sankoff等[37-38]方法延伸到系統(tǒng)網絡上。

　　Jin等[39]提出了構建系統(tǒng)發(fā)生網絡的最大似然法，首先，基于樹的似然值給出此網絡的似然值計算公式，且設計了啟發(fā)式算法來計算此值，然后利用分支定界啟發(fā)式算法及EM算法搜索最優(yōu)網絡，并且對真菌和質體中的15種生物及古細菌中的14種生物分別構建了水平基因轉移網絡。Snir等[40-41]為構建和分析系統(tǒng)發(fā)生網絡提出了一個新的概率模型NET-HMM。模型中結合了最大似然法及馬爾科夫模型，且假設DNA序列或者核苷酸序列上的相鄰位點的進化是相互依賴的，這一假設與生物實際過程更為相符。在此模型中，隱狀態(tài)是系統(tǒng)發(fā)生網絡所包含的樹。

　　隱式網絡方面，Huson等提出的clusternetwork方法是利用網絡彈出算法（network-poppingalgorithm）來構建有根隱式網絡方法[42]。此方法首先構建哈塞圖（Hassediagram），然后在此基礎上以添加邊的方式構建網絡節(jié)點。其后Huson等[43]提出了gallednetwork方法，這是首先利用種子增長算法（seed-growingalgorithm）找出輸入樹集合的RMCS問題的解，即，去掉一些物種后的樹集是不沖突的，這時可以為不沖突的樹集構建一棵系統(tǒng)樹T，最后再將去掉的物種添加到T上，從而得到系統(tǒng)發(fā)生網絡。VanIersel等又提出了CASS方法[7]，此方法所構建的網絡與實際生物網絡更加相符，但是當所構建的網絡很大時，該方法速度較慢，運行時間也長，不利于使用者在較短時間內得到結果網絡。

　　程序Dendroscope[44]主要可用來計算有根系統(tǒng)發(fā)生網絡，其中包含一些構建隱式網絡的方法，如CASS方法、gallednetwork方法及clusternetwork方法；程序中還包括一些構建顯式網絡的方法，如雜交網絡方法。

　　3結論與展望

　　本文對現有的系統(tǒng)發(fā)生網絡構建方法進行概述。系統(tǒng)發(fā)生網絡主要用于兩種方式：描述發(fā)生了網狀進化事件的物種進化史、表示沖突的進化信息。隨著數據量的增加，提出快速有效的構建系統(tǒng)發(fā)生網絡的方法則已成為刻不容緩的研究任務。將系統(tǒng)發(fā)生網絡應用到實際生物研究必將成為下一步的發(fā)展趨勢。

　　參考文獻：

　　[1]DELWICHECF，PALMERJD.Rampanthorizontaltransferandduplicationofrubiscogenesineubacteriaandplastids[J].MolecularBiologyandEvolution，1996，13（6）：873–882.

　　[2]DOOLITTLEWF.Phylogeneticclassificationandtheuniversaltree[J].Science，1999，284（5423）：2124–2128.

　　[3]GRIFFITHSRC，MARJORAMP.AncestralinferencefromsamplesofDNAsequenceswithrecombination[J].JournalofComputationalBiology，1996，3（4）：479–502.

　　[4]RIESEBERGLH.Hybridoriginsofplantspecies[J].AnnualreviewofEcologyandSystematics，1997：359–389.

　　[5]SNEATHP.Cladisticrepresentationofreticulateevolution[J].SystematicZoology，1975，24（3）：360–368.

　　[6]SYVANENM.Cross-speciesgenetransfer；implicationsforanewtheoryofevolution[J].JournaloftheoreticalBiology，1985，112（2）：333–343.

　　[7]VANIERSELL，KELKS，RUPPR，etal.Phylogeneticnetworksdonotneedtobecomplex：usingfewerreticulationstorepresentconflictingclusters[J].Bioinformatics，2010，26（12）：i124–i131.

　　[8]HUSONDH，SCORNAVACCAC.Asurveyofcombinatorialmethodsforphylogeneticnetworks[J].GenomeBiologyandEvolution，2011，3：23.[9]MADDISONWP.Genetreesinspeciestrees.[J].SystematicBiology，1997，46（3）：523–536.

　　[10]LINDERCR，RIESEBERGLH.Reconstructingpatternsofreticulateevolutioninplants[J].AmericanJournalofBotany，2004，91（10）：1700–1708.

轉載請注明來自：http://www.jinnzone.com/jisuanjiyingyonglw/33183.html