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

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

　　關(guān)鍵詞：系統(tǒng)發(fā)生網(wǎng)絡(luò),網(wǎng)狀進(jìn)化事件,隱式網(wǎng)絡(luò),顯式網(wǎng)絡(luò)

　　0引言

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

　　1無(wú)根系統(tǒng)發(fā)生網(wǎng)絡(luò)構(gòu)建算法

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

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

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

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

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

　　2有根系統(tǒng)發(fā)生網(wǎng)絡(luò)構(gòu)建算法

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

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

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

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

　　3結(jié)論與展望

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

　　參考文獻(xiàn)：

　　[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.

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiyingyonglw/33183.html