生物信息學(xué)第六章系統(tǒng)發(fā)生分析

第一節(jié)系統(tǒng)發(fā)１、系統(tǒng)發(fā)生分析系統(tǒng)發(fā)生（phylgny）是指生物形成或進(jìn)化的歷史，系統(tǒng)發(fā)生學(xué)(phylgnecs)研究物種之間的進(jìn)化關(guān)系，其基本思想是比較物種的特征，并認(rèn)為特征相似的物種在遺傳學(xué)上接近。系統(tǒng)發(fā)生研究的結(jié)果往往以系統(tǒng)發(fā)生樹（phylgneicree）表示，用它描述物種之間進(jìn)化關(guān)系。系統(tǒng)發(fā)生分析早在時(shí)代就已經(jīng)開始，經(jīng)典系統(tǒng)發(fā)生學(xué)涉及的特征主要是物理或表型特征，如生物的大核酸序列或蛋白質(zhì)分子。現(xiàn)今世界上存在的核酸和蛋白質(zhì)分子都是從共同的祖先經(jīng)過大量的細(xì)微改變進(jìn)化而來，這些生物分子的序列中隱藏著大量關(guān)于物種進(jìn)化的信息?，F(xiàn)代系統(tǒng)發(fā)生分析通過比較生物分子序列，分析序列之間的關(guān)系，構(gòu)造系統(tǒng)發(fā)生樹，進(jìn)而闡明各個(gè)物種的進(jìn)化關(guān)系(FtchndMrolah,16)。在現(xiàn)代分子進(jìn)化研究中，根據(jù)現(xiàn)有生物或物種多樣性來重建生物的進(jìn)化史是一個(gè)非常重要的問題。一個(gè)可靠的系統(tǒng)發(fā)生的推斷，將揭示出有關(guān)生物進(jìn)化過程的順序，有助于了解生物進(jìn)化的歷史和進(jìn)化機(jī)制。根據(jù)核酸和蛋白質(zhì)的序列信息，可以推斷物種之間的系統(tǒng)。其基本原理非分析，一般假設(shè)序列變化的速率相對恒定。關(guān)于地球上現(xiàn)代人的研究是一個(gè)典型而有趣的例子，科學(xué)家分析了取自世界不同地區(qū)許多人的線粒體DNA。線粒體DNA非常適合于系統(tǒng)發(fā)生分析，因?yàn)榫€粒體DNA從完全傳到子代，不與父代DNA重組。分析結(jié)果表明，所有現(xiàn)代人都是一個(gè)非洲女性的后代。由于ＤＮＡ分子非常穩(wěn)定，所以可以通過ＤＮＡ分析活著的生物，也可以分析死去的生物（Hermanandumel,194，甚至分析已經(jīng)絕種的生物。當(dāng)然用細(xì)胞核來研究系統(tǒng)發(fā)生關(guān)系時(shí)，遇到的一個(gè)嚴(yán)重的問題是，常常會(huì)被，導(dǎo)致在組中，一個(gè)可能有若干個(gè)拷貝。在進(jìn)化過程中，這些拷貝各自演變，形成兩個(gè)或的相似。在對不同物種的進(jìn)行比較時(shí)，如果選擇這類，其分析結(jié)果將存在問題。所有的生物都可以追溯到共同的祖先，生物的產(chǎn)生和分化就象樹一樣地生長、分叉，以樹的形式來表示生物之間的進(jìn)化關(guān)系是非常自然的事。可以用樹中的各個(gè)分枝點(diǎn)代表一類生物的相對時(shí)間，兩個(gè)分枝點(diǎn)靠得越近，則對應(yīng)的兩群生物進(jìn)化關(guān)系越密切。對生物學(xué)家來說，重要的是知道某些物種或種群的歷史及在每一次后趨異時(shí)間，當(dāng)這些歷史事件以系統(tǒng)發(fā)生樹的形式表現(xiàn)時(shí)，此時(shí)的系統(tǒng)發(fā)生樹稱為物種（或種群）樹。對任何一類生物，要想知道確切的物種（或種群）樹是非常的，但可以檢測這類生物所包含的一些的進(jìn)化關(guān)系來推斷物種（或種群樹(常青等,1998)。如果系統(tǒng)發(fā)生樹是基于一個(gè)的核酸或氨基酸序所立，此的統(tǒng)發(fā)樹稱為個(gè)樹樹時(shí)物種（或種群樹并不一致，特別是在基因組中存在２個(gè)或的同樣的拷貝時(shí)。但是，無論是物種（或種群）樹還是樹，都是用樹一類的拓?fù)浣Y(jié)構(gòu)表示出來。２、系一般來說，系統(tǒng)發(fā)生樹是一種二叉樹。所謂樹是一個(gè)無向非循環(huán)圖。系統(tǒng)發(fā)生樹由一系列節(jié)點(diǎn)和分支組成，其中每個(gè)節(jié)點(diǎn)代表一個(gè)分類單元（物種或序列，而節(jié)點(diǎn)之間的連線代表物種之間的進(jìn)化關(guān)系。樹的節(jié)又分為外部節(jié)點(diǎn)和節(jié)點(diǎn)。在一般情況下，外部點(diǎn)代表實(shí)際觀察到的分類單元。節(jié)點(diǎn)又稱為分支點(diǎn)，它代表了進(jìn)化事件發(fā)生的位置，或代表分類單元進(jìn)化歷程中的祖先。分類單元亦稱為運(yùn)籌分類單位（opertonlaoomcnts，簡稱OTU，是一種由研究者選定的基本單位，在一項(xiàng)研究中分類單元一般應(yīng)當(dāng)一致。在下面的中，大多以序列（蛋白質(zhì)、DNA）作為分類單位。樹節(jié)點(diǎn)間的連線稱為分支，其中一端與葉節(jié)點(diǎn)相連的為外支，不與葉節(jié)點(diǎn)相連的為內(nèi)支。系統(tǒng)發(fā)生樹有許多形式：可能是有根樹，也可能是無根樹；可能是一般的樹，也可能是二叉樹；可能是值的樹（樹中標(biāo)明分支的長度，也可能是無權(quán)值樹。在一棵有根樹中，有一個(gè)唯一的根節(jié)點(diǎn)，代表所有其它節(jié)點(diǎn)的共同祖先，這樣的樹能夠反應(yīng)進(jìn)化層次，而無根樹則沒有層次結(jié)構(gòu)。二叉樹是一種特殊的樹，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。在值的樹中，分支的長度（或權(quán)值）一般與物種之間的變化成正比，它是關(guān)于生物進(jìn)化時(shí)間或者遺傳距離的一種度量形式。一般假設(shè)存在一個(gè)分子鐘，進(jìn)化的速率恒定。系統(tǒng)發(fā)生樹具圖6.1(a)所示的是一棵有根樹，而圖6.1(b)顯示的是一棵無根樹，圖中的A、B、C、D為所研究對于給定的分類單元數(shù)，有很多棵可能的系統(tǒng)發(fā)生樹，但是只有一棵樹是正確的，分析的目標(biāo)就是要尋找這棵正確的樹。樹112112 3ABC21B1321B13 6.1a)有根樹；(b)３、系統(tǒng)發(fā)生分析步系統(tǒng)發(fā)生分析的目的是探討物種之間的進(jìn)化關(guān)系，其分析的對象往往是一組同源的序列。這些序列取自于不同生物組的共同位點(diǎn)。序列比對是進(jìn)行同源分析的一種基本，是進(jìn)行系統(tǒng)發(fā)生分析的基礎(chǔ)，一般采用基于兩兩比對漸進(jìn)的多重序列比對方法（FengandDoolittle，1996；Hein，，如無論是DNA序列，還是蛋白質(zhì)序列，都是由特定字母表中的字符組成的，計(jì)算序列之間距離的一個(gè)前提條件是要有一個(gè)字符替換模型。替換模型影響序列多重對比排列的結(jié)果，影響系統(tǒng)發(fā)生樹的構(gòu)造結(jié)果。在具體的分析過程中，需要選擇一個(gè)合理的字符替換模型，參見第三章的各種打分模型或代價(jià)、距離模型。（或者相似度是反映序列之間關(guān)系的一種度量，是建立系統(tǒng)發(fā)生樹時(shí)所常用的一類數(shù)據(jù)。在計(jì)算距離之前，首先進(jìn)行序列比對，然后累加每個(gè)比對位置的得分。可以應(yīng)用第三章介紹的關(guān)于序列比較方法，直接計(jì)算序列之間的距離。如果在進(jìn)行序列比較時(shí)使用的是相似性度量函數(shù)，則需要將相似度（或者得分）轉(zhuǎn)換成距離。令S(i,j)是序列i和序列j比對位置得分的和，一種歸一化的距離計(jì)算公式為：d(i,j)1S(i,j)Sr(i,Smax(i,j)Sr(i,

（6-其中Sr(i,j)是序列i和j隨機(jī)化之后的比對得分的和，Smax(i,j)是可能的最大值（當(dāng)兩條序列相同時(shí)取最大值。兩個(gè)序列歸一化距離的值處于0和1之間，當(dāng)兩個(gè)序列完全一致時(shí)，距離為0，當(dāng)兩個(gè)序列差異很大時(shí)，距離接近于1。如果在上式中令Sr(i,j)=0，則計(jì)算公式變?yōu)椋篸(i,j)1 S(i,

（6-為了適合于處理相似性較小的序列，可以進(jìn)一步修改距離計(jì)算公式：d(i,j) S(i,Smax(i,

（6-序列比對得分和可以根據(jù)常用的打分矩陣獲得。如果待處理的序列是蛋白質(zhì)，則用PAM矩陣、BLOSUM矩陣等，如果待處理的序列是DNA或者RNA，則用等價(jià)矩陣、核苷酸轉(zhuǎn)換矩陣或者其它具有距離是系統(tǒng)發(fā)生分析時(shí)所使用的一類數(shù)據(jù)，另一類數(shù)據(jù)是所謂的離散特征數(shù)據(jù)。離散特征數(shù)據(jù)可分為二態(tài)特征與多態(tài)特征。二態(tài)的離散特征只有2種可能的狀況，即具有與不具有某種特征，通常用“0”或“1”表示。例如，DNA序列上的某個(gè)位置如果是剪切位點(diǎn)，其特征值為1，否則為0。多態(tài)離散特征具有兩種以上可能的狀態(tài)，如核酸的序列信息，對序列中某一位置來說，其可能的核苷酸堿基有Ａ、Ｔ、Ｇ或Ｃ4種。系統(tǒng)發(fā)生樹的構(gòu)建方法很多種（Pennyetal192.;Flestin196；Aise994Swfordeta.，196；i197；Bociei2001。根據(jù)所處理數(shù)據(jù)的類型，可以將系統(tǒng)發(fā)生樹的構(gòu)建方法分為兩大類。一類是基于距離的構(gòu)建方法，利用所有物種或運(yùn)籌分類單位間的進(jìn)化距離，依據(jù)一定的原則及算法構(gòu)建系統(tǒng)發(fā)生樹。基本思路是列出所有可能的序列對，計(jì)算序列之間的遺傳距離，選出相似程度比較大或非常相關(guān)的序列對，利用遺傳距離進(jìn)化關(guān)系。這類方法有非組平均法（unwigtdarrupmthdwiharthmeticmas、鄰近歸并法（neihorjinngmehd、Fitrglash法、最小進(jìn)化方法（minmmvouion）等。另一類方法是基于離散特征的構(gòu)建方法，利用的是具有離散特征狀態(tài)的數(shù)據(jù)，如DNA序列中的特定位點(diǎn)的核苷酸。建樹時(shí)著重分析運(yùn)籌分類單位或序列間每個(gè)特征（如核苷酸位點(diǎn)）的進(jìn)化關(guān)系等。屬于這一類的方法有最大簡約法（umarionymethod、最大似然法（umlklihoodmethod、進(jìn)化簡約法（evluinayarioymthod、相容性方法（comptbiiy）等。對相似性和距離數(shù)據(jù)，在重建系統(tǒng)發(fā)生樹時(shí)只能利用距離法。離散特征數(shù)據(jù)通過適當(dāng)?shù)姆椒赊D(zhuǎn)換成距離數(shù)據(jù)，因此，對于這類數(shù)據(jù)在重建系統(tǒng)發(fā)生樹時(shí)既可以用距離法，亦可以采用離散特征法。根據(jù)建樹算法在執(zhí)行過程中采用的搜索方式，系統(tǒng)發(fā)生樹的構(gòu)建方法也可以分為以下3類。第一類是窮盡搜索方法：即產(chǎn)生所有可能的樹，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。需要注意的是，系統(tǒng)發(fā)生樹可能的個(gè)數(shù)隨序列的個(gè)數(shù)急劇增加，假設(shè)要為n個(gè)物種建立系統(tǒng)發(fā)生樹，則不同拓?fù)浣Y(jié)構(gòu)的樹有(2n-3)!!棵。如果n為20，則大約有1021棵可能的樹。假設(shè)序列的個(gè)數(shù)為7，則所有可能的有根樹的個(gè)數(shù)為10,395，所有可能的無根樹的個(gè)數(shù)為795。當(dāng)序列的數(shù)目超過7時(shí)，由于樹的個(gè)數(shù)太多，不可能采用窮盡搜索的方式來求取最優(yōu)樹。由于可能的樹非常多，從計(jì)算量來看，這種方法只能處理很少的物種。第二類方法是分支約束方法：即根據(jù)一定的約束條件將搜索空間限制在一定范圍內(nèi)，產(chǎn)生可能的樹，然后擇優(yōu)。這是人工智能技術(shù)中的一種空間搜索策略，這種搜索方式不需要搜索整個(gè)樹空間，可大大提高搜索效率。第三類是啟發(fā)式或經(jīng)驗(yàn)性方法：根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間，提高計(jì)算速度。這種方法能夠處理大量的分類單元，雖然不能保證所構(gòu)建的樹是最優(yōu)的，但實(shí)際結(jié)果往往接近于最優(yōu)解。當(dāng)待分析的對象個(gè)數(shù)比較多時(shí)，必須采用分支約束方法或者啟發(fā)式的方法。在構(gòu)造系統(tǒng)發(fā)生樹時(shí)需要考慮進(jìn)化假設(shè)和進(jìn)化模型(SwofordadOlen1990,Liandraur191)。系統(tǒng)發(fā)生樹的類型可能是有根樹，這意味著其中的一個(gè)序列代表其他所有序列共同的祖先，到達(dá)該序列的分支是樹的最底層分支。另一方面，系統(tǒng)發(fā)生樹可能是無根樹，意味著沒有共同的祖先。一般認(rèn)為樣本序列是隨機(jī)進(jìn)化的，序列中的所有位點(diǎn)的進(jìn)化也是隨機(jī)的而且是獨(dú)立的。在進(jìn)行具體的系統(tǒng)發(fā)生分析時(shí)，一般還要作一些假設(shè)（BaxeaisandFrancis，1998：序列必須是正確源（或平行進(jìn)化）序列，序列之間的系統(tǒng)發(fā)育史是相同的，在序列比對中，不同序列的同一個(gè)位點(diǎn)都是同源的。另外，當(dāng)兩個(gè)物種在系統(tǒng)發(fā)生樹上分化后，各自獨(dú)立進(jìn)化發(fā)展。對系統(tǒng)分析的樣本也有一定的要求，要求樣本足以反映感的問題，樣本序列之間的差異包含了足以解決感的問題的系統(tǒng)發(fā)生信號(hào)。通過某種算法構(gòu)造好一棵系統(tǒng)發(fā)生樹之后，需要對樹的合理性和可靠性進(jìn)行分析。對于若干個(gè)序列，如果利用多種不同的分析方法進(jìn)行系統(tǒng)發(fā)生分析，并且得到相似的進(jìn)化關(guān)系，那么分析結(jié)果具有較高的度。系統(tǒng)發(fā)生分析一般是建立在“分子鐘”基礎(chǔ)上的。生物隨著時(shí)間的推進(jìn)而演化，進(jìn)化的速率被視為進(jìn)化研究中的基本問題之一（等，2000。進(jìn)化速率就是在某一段時(shí)間內(nèi)的遺傳改變量。分子進(jìn)化速率相關(guān)的分子鐘的概念源于對蛋白質(zhì)序列的研究。科學(xué)家們在比較幾種動(dòng)物的血紅蛋白、細(xì)胞色素C的序列后注意到：這些蛋白質(zhì)的氨基酸取代速率在不同的種系間大致相同，即分子水平的進(jìn)化存在恒速現(xiàn)象（ZuckrnlandPaulig，162，95;rwntl.,1972。于是提出了進(jìn)化在分子水平存在“時(shí)加?，F(xiàn)在已知道不僅是氨基酸序列，ＤＮＡ序列也存在這種規(guī)律。Kimura進(jìn)一步提出了具體的分子進(jìn)化觀點(diǎn)（Kimura983：對于各物種的每個(gè)蛋白質(zhì)，如果用每個(gè)位點(diǎn)每年發(fā)生的氨基酸替換次數(shù)作為衡量分子進(jìn)化的速率，則該速率是大致恒定的；功能上次要的分子（或者分子部分）的進(jìn)化速率比功能重要的分子（或者分子部分）進(jìn)化速率快；對現(xiàn)有分子結(jié)構(gòu)或者功能破壞小的氨基酸替換比破壞力大的氨基酸替換發(fā)生得更加頻繁。第二節(jié)基于距離的系統(tǒng)發(fā)生樹構(gòu)建立系統(tǒng)發(fā)生樹的基本任務(wù)是：在給定的條件下（包括物種、物種的特征值或者序列，構(gòu)造一棵最優(yōu)的系統(tǒng)發(fā)生樹。這里重點(diǎn)針對DNA序列或者蛋白質(zhì)序列構(gòu)建系統(tǒng)發(fā)生樹?；诰嚯x的系統(tǒng)發(fā)生樹構(gòu)建方法的基本思路是：給定一種序列之間距離的測度，在該距離測度下構(gòu)建一棵系統(tǒng)發(fā)生樹，使得該樹能夠最好地反映已知序列之間的距離。這種方法采用兩兩距離，建立一個(gè)距離矩陣，如表6.1所示。6.110(Saitou,1996)12345678923456789這里的距離代表兩條序列之間各位點(diǎn)核苷酸替換數(shù)的（代價(jià)，也可DNADNA序列，可以采用等價(jià)矩陣（Li1997，也可以采用核苷酸轉(zhuǎn)換矩陣（MichnerandSkl197或者采用其他具有非對稱置換頻率的矩陣（Felsesen，188；aoetl.，195）。對于蛋白質(zhì)序列，一般采用PAM矩陣比較合適，因?yàn)樵摼仃嚲褪轻槍ρ芯康鞍踪|(zhì)序列之間的進(jìn)化距離而設(shè)計(jì)的。為了便于分析，首先定義續(xù)加和距離函數(shù)，在該函數(shù)下，兩個(gè)物種之間的距離與系統(tǒng)發(fā)生樹中連接這兩個(gè)物種的分支總長度成正比。這樣，如果物種a和物種b由經(jīng)過中間節(jié)點(diǎn)v的兩條邊相連，兩條邊的長度分別為dav和dbv，則它們之間的距離為dav+dv。這樣，可以在系統(tǒng)發(fā)生樹中確定a和b的相對位置。進(jìn)一步，假設(shè)三個(gè)物種之間的距離分別為dabdacdc,可以通過求解線性方程計(jì)算出系統(tǒng)發(fā)生樹的距離dav、dv和dcv。例，如果有三個(gè)物種，其兩兩距dab=dac=dbc=通過求解方程，得到如圖6.2所示的u v ba圖6.2根據(jù)方程求解結(jié)果構(gòu)造系圖6.2是一個(gè)簡單的例子，在實(shí)際工作中，所處理的物種可能很多，因而需要求解的線性方程也很多，難以求解，或者方程組的求解過程存在著不確定性，因此需要采用數(shù)學(xué)近的方法。1、最小二乘法統(tǒng)計(jì)學(xué)上近的方法之一是最小二乘法。的目標(biāo)是構(gòu)造一棵樹T，該樹的葉節(jié)點(diǎn)代表物種，用該樹物種之間的距離。通過優(yōu)化，使下式最小化：nSSQ(T)Wij(Dijdij)i1

（6-這里，Dij為物ij的實(shí)際觀察距離（或序列之間的計(jì)算距離）dij是物種i和j在系統(tǒng)發(fā)生樹T中的距離，Wij是與物種i和j相關(guān)的權(quán)值。SSQ（T）是樹T所有值與實(shí)際觀察值偏差的累加和。權(quán)值Wij一般為1，或

=1/D （6-一般來說，尋找一棵最小方差樹是一個(gè)NP-完全問題（DayWHE，1986），需要采用近似的算法。下面幾種計(jì)算復(fù)雜度為多項(xiàng)式的啟發(fā)式方法，即連鎖聚類方inkageclustering、非組平均法（UPGMA）和鄰近歸并法（NeighborJoining2、連鎖聚n個(gè)葉節(jié)點(diǎn)表示n個(gè)物種（序列，然后將進(jìn)化過程中的祖先賦予樹的節(jié)點(diǎn)。假設(shè)若干個(gè)序列是從一個(gè)共同的祖先進(jìn)化而來，則系統(tǒng)S代表一個(gè)物種集合，定義在該集合上的距離測度d(x,y)（x,yS）滿>0for（6-=0for（6-=（6- （6-6.3連鎖聚類結(jié)果超距離測度d(x,y)滿足下述條件： （6-給定序列，通過序列之間的兩兩對比排列，計(jì)算序列之間的進(jìn)化距離，并假設(shè)得到的距離矩陣是一種滿足超距離測度條件，則系統(tǒng)發(fā)生樹的聚類構(gòu)造過程如下：首先從距離矩陣中選擇距離最小的一對序列，然后將這兩個(gè)序列合二為一，形成一個(gè)新的對象（代表這兩個(gè)序列的祖先，并重新計(jì)算這個(gè)新的對象與其它序列的距離。不同的實(shí)現(xiàn)方案采用不同的計(jì)算公式：單連鎖（6-最大連（6-平均連（6-其中x代表y和z的合并，u代表任意其它對象。重復(fù)上述過程，直到所有的物種都被合并到一類為止。圖6.3就是一個(gè)通過平均連鎖聚類分析的結(jié)果。其一般過程如為：首先計(jì)算所有序列的兩兩比對，得到距離值，然后利用連鎖聚類算法構(gòu)造樹，采多重比對問題轉(zhuǎn)化為序列兩兩比對問題，3、非分組平均法（UnweightedPairGroupMethod,非分組平均法是一種較為常用的聚類分析方法(MichnerndSkal,15)，最早是用來（即若干個(gè)分類單元形成的集合）之間距離的計(jì)算公式不一樣。當(dāng)用來構(gòu)建系統(tǒng)發(fā)生樹時(shí)，其假定的前提條件是：在進(jìn)化過程中，每一世系發(fā)生趨異的次數(shù)相同，即核苷酸或氨基酸的替換速率是均等且恒定的。通過非組平均法所產(chǎn)生的系統(tǒng)發(fā)生樹可以說是物種樹的簡單體現(xiàn)，在每一次趨異發(fā)生后，從共同祖節(jié)點(diǎn)到兩個(gè)分類單元間的分支長度一樣。因此，這種方法較多地用于物種樹的重建。非加權(quán)分組平均法在算法上較簡單。在聚類之前，令所有的分類單元各自成為一類；然后反復(fù)將最鄰近（距離最?。┑膬蓚€(gè)類形成一個(gè)新的聚類，其分支點(diǎn)位于原來2個(gè)分類距離的1/2處，計(jì)算新的分類與分類間的平均距離；如此反復(fù)，直到所有的分類單元都聚為一類，最終得到一個(gè)完整的系統(tǒng)發(fā)生樹。系統(tǒng)發(fā)生樹的結(jié)構(gòu)與分類過程相對應(yīng)。設(shè)d是物種之間的距離函數(shù)，對于兩個(gè)分類Ci和Cj，定義它們之間的距離DijD d(p,ni ni

（6-這里，ni=|Ci|,nj=|Cj|,分別為兩個(gè)分類中分類單元的個(gè)為了給樹中的每個(gè)分支賦予分支長度，使SSQ(T)最小，UPGMA通常能夠獲得滿意的結(jié)果。該算初始化：使每個(gè)物種自成一類，如果有n個(gè)物種，則開始時(shí)共有n個(gè)類，每個(gè)類的大小為1，n個(gè)葉節(jié)點(diǎn)代表每個(gè)類；尋找具有最小距離Dij的兩i、建立一個(gè)新的聚類（ij),該聚類i和類j的合ij(ij)，生長兩個(gè)新的分支，將i和j連接到(ijDij/2；計(jì)算新的分類到其它類的距離，計(jì)算公式為下列的平均距離，

nin

nnin

（6-在距離矩陣中刪除與類i和類j相應(yīng)的行和列，為類(ij)加入新的行和列，其值按上述公運(yùn)用UPGMA算法，得到一棵有根的系統(tǒng)發(fā)生樹，從樹根到任何葉節(jié)點(diǎn)的分支長度全都一樣。也起點(diǎn)）出發(fā)，踏著同樣的節(jié)律，沿不同的路徑，演化成為當(dāng)前的形式。而任意兩個(gè)物種之間的距離是連接這兩個(gè)物種所在葉節(jié)點(diǎn)路徑上的距離和。在解決實(shí)際問題時(shí)，如果確實(shí)存在分子鐘，則UPGMA能夠保證找到最優(yōu)的答案。該算法的示例見圖6.4。圖6.5是針對表6.1中的距離矩陣而構(gòu)建系統(tǒng)發(fā)生樹。 圖6.4UPGMA和鄰近歸并法(NJ)分析結(jié)果(Shamir 圖6.5UPGMA所構(gòu)造的系統(tǒng)鄰歸并法是一種快速的類方法，方法Saitou和Nei于1987年首次(SitouandNei,197)。在構(gòu)建系統(tǒng)發(fā)生樹時(shí)，它取消了非分組平均法所作的假定，不需要關(guān)于分子鐘的假設(shè)，在進(jìn)化分支上，發(fā)生趨異的次數(shù)可以不同。最近的計(jì)算機(jī)模擬已表明它是最有效的基于距離數(shù)據(jù)重建系統(tǒng)發(fā)生樹的方法之一。與非分組平均法相比，鄰近歸并法在算法上相對較復(fù)雜，它的是樹上的節(jié)點(diǎn)而不是分類單元。這種方法的基本思想是：在進(jìn)行類的合并時(shí)，不僅要求待合并的類是相近的，同時(shí)還要求待合并的類遠(yuǎn)離其它的類。在聚類過程中，根據(jù)原始距離矩陣，根據(jù)所有節(jié)點(diǎn)間的平均趨異程度對每兩個(gè)節(jié)點(diǎn)間的距離進(jìn)行調(diào)整，即將每個(gè)分類單元的趨異程度標(biāo)準(zhǔn)化，從而形成一個(gè)新的距離矩陣。重建時(shí)將距離最小的兩個(gè)葉節(jié)點(diǎn)連接起來，合并這兩個(gè)葉節(jié)點(diǎn)所代表的分類，形成一個(gè)新的分類。在樹中增加一個(gè)父節(jié)點(diǎn)，并在距離矩陣中加入新的分類，同時(shí)刪除原來的兩個(gè)分類。隨后，新增加的父節(jié)點(diǎn)被看成為葉節(jié)點(diǎn)，重復(fù)上一次循環(huán)。在每一次循環(huán)過程中，都有兩個(gè)葉節(jié)點(diǎn)被一個(gè)新的父節(jié)點(diǎn)所取代,兩個(gè)類被為一個(gè)新類。整個(gè)循環(huán)直到只剩一個(gè)類為止。從所得到的系統(tǒng)發(fā)生樹來看，兩個(gè)聚在一起的分類單元其所在的葉節(jié)點(diǎn)到父節(jié)點(diǎn)的距離并不一定相同。在每一次的循環(huán)中，在樹中尋找兩個(gè)物種的直接祖先。對于節(jié)點(diǎn)i，到其它節(jié)點(diǎn)的距離ui按下ui=ki(Dik/(n- （6-這里Dik是分i和分類k之間的距離，是動(dòng)態(tài)更新的距離矩陣D中的元素。為了使所有分所示。新分支的長度dk,(ij)用求解線性方程的方法進(jìn)行計(jì)算（6.2j圖 尋找一對節(jié)點(diǎn)，使這兩個(gè)節(jié)點(diǎn)靠近，但同時(shí)遠(yuǎn)離其它節(jié)算法如初始化（UPGMA一樣循對于所有的分類單元iuiki(Dik/(n-選擇一對分類單元i和j，使Dij-ui-uji和j歸并為新的類(ij)，在樹中添加一個(gè)新的節(jié)點(diǎn)，代表新生成的分類，計(jì)算從idi,(ij）=1/2Di,j+1/2(ui-uj),dj,(ij）=1/2Di,j+1/2(uj-D(ij）,k=1/2(Di,k+Dj,k-刪除聚類ijDi,j的分支連接剩余的兩個(gè)類。鄰近歸并法的處理示意如圖6.4所示，針對表6.1中距離矩陣的實(shí)際計(jì)算結(jié)果見表6.2，構(gòu)造的系統(tǒng)發(fā)生樹如圖6.7所示。詳細(xì)的鄰近歸并算法見（等，1997。6.2鄰近歸并算法計(jì)算結(jié)果(OUT9=14.632(4.530E-10(1.407E-OUT2=-0.065(-2.011E-3(3.311E-Node12=4.463(1.382E-4(8.339E-Node13=4.281(1.325E-5(3.575E-OUT8= (1.680E-=(2.820E-OUT7= (5.932E-=(3.822E-Node14=5.102(1.580E-6(1.646E-(Last1.675(5.186E-0.907(2.808E-1.410(4.364E-Node或OUT后面的數(shù)字代表節(jié)點(diǎn)（或分類單元）與節(jié)點(diǎn)之間分支的長度，該長度對應(yīng)于序列比較區(qū)域的核苷酸替換（括號(hào)里的數(shù)字對應(yīng)每個(gè)位點(diǎn)的替換。2 45 9 圖6.7利用鄰近歸并算法構(gòu)造的系統(tǒng)在基于距離的建樹方法中還有Fitargoliash法（FM,FitchandMrglash,97，該方將樹中的序列兩兩距離的合適度極大化。另法是最小進(jìn)化方法（ME,MinimumEvolution最小進(jìn)化概念首先由Cavalli-Sforza等人用于鄰近歸并方法（Cavalli-SforzaandEdwards1967小進(jìn)化方法先使用Fitch和Margoliash方法估計(jì)系統(tǒng)發(fā)生樹上的分支長度，然后進(jìn)行優(yōu)化，求出所有分支長度和最小的樹。利用最小二乘法進(jìn)行優(yōu)化，將觀察到的距離相對于進(jìn)化樹距離的偏差的平方最小化（RzhetskyandNei,1992;Swoffordetal.,1996a;Felsenstein,1997FM方法不同，ME方法并不使用所有可能的序列兩兩距離和所有可能的相關(guān)路徑長度，而是先根據(jù)樹中的節(jié)點(diǎn)到葉節(jié)點(diǎn)之間的距離固定進(jìn)化樹節(jié)點(diǎn)的位置，然后根據(jù)這些觀察點(diǎn)之間的最小計(jì)算誤差，對的樹枝長度進(jìn)行優(yōu)化。最小進(jìn)化方法的具體求解過程是：首先利用鄰近歸并法構(gòu)造出候選的樹，再搜索與候選樹具有6.1ME-REE進(jìn)行計(jì)算，其結(jié)果如表6.3所示。所形成的系統(tǒng)發(fā)生樹與圖6-7相似，但是略有不同，優(yōu)化以后的樹的分支長度總和比圖6.7中的系統(tǒng)發(fā)生樹的分支長度總和短分分支長度置信度1—2—-3—4—5—6—7—8—9—10—11—12—13—14—15—16—17—第三節(jié)基于特征的系基于特征的系統(tǒng)發(fā)生分析的一般問題是：給定n個(gè)物種，m個(gè)用以描述物種的特征，以及每個(gè)物種所對應(yīng)的特征值，構(gòu)建一棵系統(tǒng)發(fā)生樹，使得某個(gè)目標(biāo)函數(shù)最大。輸入一般為n×m的矩陣M，其中Mij代表第i物種之第j個(gè)特征的取值，如表6.4所示。在構(gòu)建系統(tǒng)發(fā)生樹假設(shè)特征是相互獨(dú)立的，6.4分類單甲CAGGTA乙CAGACA丙CGGGTA丁TGCACT戊TGCGTA對于給定的條件，要在很多可能的樹中找一個(gè)最佳的樹。在實(shí)際應(yīng)用中，不可能窮盡搜索所有可能的樹，必須按照一定的方法、一定的策略在較短的時(shí)間內(nèi)得到比較好的結(jié)果。1、最大簡約法(um最大簡約法最早是基于形態(tài)特征分類的需要而發(fā)展起來的，因使用的算法不同而有著許多版本，其中有些已被廣泛地用于分子進(jìn)化研究中根據(jù)離散特征數(shù)據(jù)構(gòu)建系統(tǒng)發(fā)生樹，如對DNA序列數(shù)據(jù)分析。最大簡約法的目標(biāo)是構(gòu)造一棵反映分類單元之間最小變化的系統(tǒng)發(fā)生樹。最大簡約法利用的只是對簡約分析能提供信息的特征，如在DNA序列數(shù)據(jù)中，利用的只是存在于核苷酸序列差異（至少有兩種不同類型的核苷酸）的位點(diǎn)，這些位點(diǎn)稱為簡約信息位點(diǎn)（parsmonyifomtiesie對于系統(tǒng)發(fā)生樹最直觀的代價(jià)計(jì)算就是沿著各個(gè)分支累加特征變化的數(shù)目，而所謂簡約就是使代價(jià)最小。利用最大簡約方法構(gòu)建系統(tǒng)發(fā)生樹，實(shí)際上是一個(gè)對給定分類單元所有可能的樹進(jìn)行比較的過程，針對某一個(gè)可能的樹，首先對每個(gè)位點(diǎn)祖先序列的核苷酸組成做出推斷，然后統(tǒng)計(jì)每個(gè)位點(diǎn)用來闡明差異的核苷酸最小替換數(shù)目。在整個(gè)樹中，所有簡約信息位點(diǎn)最小核苷酸替換數(shù)的總和稱為樹的長度。通過比較所有可能樹，選擇其中長度最小的樹作為最終的系統(tǒng)發(fā)生樹，即最大簡約樹（umparsimonytree假設(shè)圖6.8是根據(jù)表6.4所建立的一棵系統(tǒng)發(fā)生樹。對于位點(diǎn)1，由于甲、乙、丙都取“C”值，邊上有一個(gè)變化（左分支T變?yōu)镃，或者右分支C變?yōu)門），就能解釋各個(gè)分類單元在該位點(diǎn)的數(shù)據(jù)。對于位點(diǎn)2，甲、乙取“A”值，而丙、丁、戊取“G”值，通過“節(jié)點(diǎn)2”可以將它們分開，因此，“節(jié)點(diǎn)2”所連接的左分支上的一個(gè)變化（G變?yōu)锳）就能解釋各個(gè)分類單元在該位點(diǎn)的差異。位AGAG需要在“節(jié)點(diǎn)1”和“節(jié)點(diǎn)3”所連接的邊上分別設(shè)置一個(gè)變換。因此位點(diǎn)4需要兩個(gè)變的分支。總的來說，對于圖6.8所示的整個(gè)系統(tǒng)發(fā)生樹，共需要8個(gè)變節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn) 節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn)對于表6.4中所列出的5個(gè)分類單元，還可以形成其它拓?fù)浣Y(jié)構(gòu)的系統(tǒng)發(fā)生樹，這些樹為解釋表6.4中各個(gè)位點(diǎn)的數(shù)據(jù)，可能需要或者更少的變化。而最大簡約法就是要尋找一棵最小變化的系統(tǒng)發(fā)生樹。最大簡約法的針對待比較的物種，選擇核酸或蛋白質(zhì)序列。有些分子比其它分子變化慢，適合于進(jìn)行距離分析，例如哺乳類的線粒體DNA、管家蛋白質(zhì)等；根據(jù)每個(gè)序列比對的位置（即多重對比排列的每一列，確定相應(yīng)的系統(tǒng)發(fā)生樹，該樹用最少的進(jìn)化動(dòng)作產(chǎn)生序列的差異，最終生成完整的樹。對于一棵系統(tǒng)發(fā)生樹T，假設(shè)樹中的節(jié)點(diǎn)用V(T)表示，樹的E(T)，以u(píng)j、vj分別表u和v的第j個(gè)特征，則樹T的代價(jià)為S(T) {j|vjuj(u,v)E(T

給定一棵有根的系統(tǒng)發(fā)生樹，所關(guān)心的是：如何計(jì)算該樹的最小變化？如何標(biāo)定樹的節(jié)點(diǎn)？假設(shè)以vc代表v節(jié)點(diǎn)特征c的值，單特征（即每個(gè)物種所對應(yīng)的序列僅含一個(gè)字符，作為單個(gè)特征的值）Fitch算法（itch，971v，其值vc取對應(yīng)物種的特征值。然后執(zhí)行下面兩步：給每個(gè)節(jié)點(diǎn)v賦予一個(gè)集合Sv：如果v是葉節(jié)點(diǎn)，則Sv={vc}；如果v是節(jié)點(diǎn)，并且u、w是其子節(jié)點(diǎn)，如果SuSw，則Sv=SuSw；否則S(v)=SuSw。這個(gè)過程是從葉節(jié)點(diǎn)開始，直給定集合Sv，為每個(gè)節(jié)點(diǎn)v的特征c賦予值vc。如果v有一個(gè)父節(jié)點(diǎn)u滿足ucSv,則將uc賦予vc，否則任取一個(gè)tSv賦予vc。這個(gè)過程的執(zhí)行方向剛好與上一個(gè)過程相反，即從樹根出發(fā)，直至葉節(jié)點(diǎn)為止，最后得到完全標(biāo)定的樹。應(yīng)按前序遍歷方式依次處理每個(gè)節(jié)點(diǎn)。最后樹中變化的個(gè)數(shù)等于第一步計(jì)算得到空交集SuSw的個(gè)數(shù)。圖6.9是對5個(gè)序列（每個(gè)序列僅含一個(gè)字符，作為物種特征）執(zhí)行過程（1）的結(jié)果，最小的總代價(jià)為3，圖點(diǎn)標(biāo)注‘*’表明該節(jié)點(diǎn)的子節(jié)點(diǎn)交集SuSw的為空。 {CG6.9最大簡約法處理結(jié)果示意（Shamir.上述算法對特征值之間變換的代價(jià)處理，不考慮其中的差別。其實(shí)各種特征值之間變換的代價(jià)是不一樣的，在建立數(shù)學(xué)模型時(shí)應(yīng)該區(qū)分這些差別。C

c代表特征c的特征值從i變化為j的代價(jià)。將上述算法改進(jìn)為求最大簡約樹，這就比Fitch算法更一般化的Sakof（Snkf,17)算法。該算法可以處理多個(gè)特征，并考慮不同特征值變換代價(jià)的差異。計(jì)算過程如下：cv和特征t，計(jì)算St(v)，它代表樹根為v的子vc=t的情況下最小代價(jià)值。Fitch算法中的第一步一樣，后序遍歷。對每個(gè)葉節(jié)點(diǎn)v：ccSc(v) v （6-c 對于每個(gè)節(jié)點(diǎn)v，設(shè)其兩個(gè)子節(jié)點(diǎn)分別為 和w，則Sc(v)min{CcSc(u)}min{CcSc （6- 樹根r的最小總代價(jià)等于S(T)minSct

（6-這里，m為特根據(jù)第一步的計(jì)算，確定每個(gè)特征在節(jié)點(diǎn)的最佳值對于根節(jié)點(diǎn)rrargminSc （6- 對于其他節(jié)點(diǎn)v，假設(shè)其父節(jié)點(diǎn)為u，vargmin(CcSc （6- 前面的工作實(shí)際上是針對已知拓?fù)浣Y(jié)構(gòu)的系統(tǒng)發(fā)生樹，確定其中的節(jié)點(diǎn)標(biāo)記，即確定樹的節(jié)點(diǎn)特征取值。這僅僅是解決問題的一個(gè)步驟，或者是后面的一個(gè)步驟。關(guān)鍵的問題是系統(tǒng)發(fā)生樹的拓?fù)浣Y(jié)構(gòu)又是如何確定的呢？實(shí)際上是要在眾多可能的拓?fù)浣Y(jié)構(gòu)中選擇一棵與給定數(shù)據(jù)相一致的樹。這是一個(gè)典型的搜索問題，而且搜索空間非常大。分支約束（BranhndBundB&B）技術(shù)可用于解決這個(gè)問題(HenyandPeny,182)。分支約束是在一個(gè)復(fù)雜的空間中進(jìn)行搜索的通用技術(shù)，搜索空間以從一個(gè)分層樹的根節(jié)點(diǎn)至葉節(jié)點(diǎn)的一系列路徑表示。該技術(shù)由Hendy和Peny首先引入到簡約法之中(yd在的情況下，該算法的時(shí)間復(fù)雜度與窮盡搜索相近。最簡單的算法形式是按照一定的順序遍歷搜索樹，保存到目前為止到達(dá)葉節(jié)點(diǎn)路徑的最小的代價(jià)，并作為代價(jià)的上限，記為B。在后續(xù)搜索過程中，如果到達(dá)搜索樹的某個(gè)節(jié)點(diǎn)，并且到達(dá)該節(jié)點(diǎn)路徑的代價(jià)大于B，則不再搜索以該節(jié)點(diǎn)為樹根的子樹，搜索樹在此節(jié)點(diǎn)處不再繼續(xù)擴(kuò)展，因?yàn)榧词顾阉髟摴?jié)點(diǎn)的子樹，也不會(huì)得到比B更好的結(jié)果。上述行為稱為搜索樹在某個(gè)節(jié)點(diǎn)剪枝。在開始搜索之前，可以根據(jù)期望值，或根據(jù)其他線索設(shè)定初始的上限值B。考慮這樣一棵搜索樹，以搜索樹的節(jié)點(diǎn)代表相應(yīng)的系統(tǒng)發(fā)生樹。在搜索樹的第k層上的節(jié)點(diǎn)代表具有k個(gè)葉節(jié)點(diǎn)，對應(yīng)于前k個(gè)物種的所有可能的系統(tǒng)發(fā)生樹，第k層上的節(jié)點(diǎn)的子節(jié)點(diǎn)將代表在上述系統(tǒng)發(fā)生樹中加入第k+1個(gè)物種而形成的新系統(tǒng)發(fā)生樹。搜索樹的樹根代表空系統(tǒng)發(fā)生樹。由于在一棵系統(tǒng)發(fā)生樹上增加一個(gè)新節(jié)點(diǎn)不會(huì)減小簡約代價(jià)，所以搜索樹滿足單調(diào)條件，分支約束技術(shù)可以幫助對搜索樹進(jìn)行剪枝，從而壓縮搜索空間，提高搜索效率。另一種優(yōu)化方法技術(shù)是局部搜索，其基本思想是對于一個(gè)搜索空間定義鄰近關(guān)系，在搜索空間遍歷時(shí)，從一個(gè)點(diǎn)轉(zhuǎn)移到它的鄰近點(diǎn)。這樣可以使用許多啟發(fā)式算法，如貪婪算法、模擬退火算法等?？傊?，最終得到的是一個(gè)局部最優(yōu)結(jié)果，并且接近于全局最優(yōu)結(jié)果，或者就是全局最優(yōu)結(jié)果。有許多定義鄰近關(guān)系的方法,例如，在對于一棵系統(tǒng)發(fā)生樹，分解它的任何子樹，并重新拼裝成與原樹不同的樹，那么這些新樹都是原樹的鄰近樹。2、最大似然法（um前面介紹的系統(tǒng)發(fā)生分析方法隱含地使用了各種概率模型，說明生物分子序列是如何進(jìn)化的，通過系統(tǒng)發(fā)生樹研究序列之間的進(jìn)化關(guān)系。最大似然法（Felsesen981;Toreetl.19;etal.95;ulenekndanla97）明確地使用概率模型，其目標(biāo)是尋找能夠以較高概率產(chǎn)生觀察數(shù)據(jù)的系統(tǒng)發(fā)生樹。最大似然法的基本模型有兩個(gè)部分：一是分支過程，它描述物種在進(jìn)化歷程上是如何的；二是采樣模型，它描述生物學(xué)家是如何選擇一組的物種進(jìn)行研究的。采樣模型比分支過程更難形式化，因此常常被忽略。一般的采樣模型假設(shè)待分析的物種是被隨機(jī)、獨(dú)立地選中的。在生物學(xué)研究的許多領(lǐng)域，最大似然法常被用來檢驗(yàn)一些假設(shè)，目前較多地用在遺傳作圖與臨床檢驗(yàn)上。因該法是建立在許多假定的基礎(chǔ)上，并且獲得最大似然估計(jì)的解較復(fù)雜，因此限制了它的推廣應(yīng)用。在DNA分子標(biāo)記研究中，該技術(shù)已被用來重建由DNA序列數(shù)據(jù)及限制性位點(diǎn)數(shù)據(jù)產(chǎn)生的系統(tǒng)發(fā)生樹。利用最大似然法來推斷一組序列的系統(tǒng)發(fā)生樹，需首先確定序列進(jìn)化的模型。然后基于一定的模型考慮兩個(gè)物種序列間的關(guān)系，計(jì)算分支的長度。這個(gè)過程需要尋找在某一進(jìn)化距離上由第一種序列真正轉(zhuǎn)換成第二種序列的可能性，并確定在最大可能下的進(jìn)化距離。接著生成多個(gè)物種所構(gòu)對于一棵給定的樹，希望有一種評(píng)價(jià)的方法（KisinoandHaegaa，189。可以用可能性得分評(píng)估所作出的假設(shè)，即評(píng)價(jià)所得到的系統(tǒng)發(fā)生樹T。對于給定的一組物種，假設(shè)它們的觀察值為（M為向量，可以選擇一棵樹，使得P(M|T)最大，即最大似然法。在下面的中假定已經(jīng)知道樹的拓?fù)浣Y(jié)構(gòu)，目標(biāo)是尋找最優(yōu)的分支長度。在基于DNA或蛋白質(zhì)序列的系統(tǒng)發(fā)生分析方面，與最大簡約法相似，最大似然法首先依賴于一個(gè)合理可靠的多重序列的比對，然后檢測每一列的變化。對于每一個(gè)可能的樹，計(jì)算在每一列發(fā)現(xiàn)真實(shí)序列變化的可能性，將每個(gè)排列位置的概率相乘，其結(jié)果作為每棵樹的可能性。具有最大似然值的樹就是最可能的樹。假設(shè)特征是兩兩獨(dú)立的，分支是一個(gè)Markov過程，即節(jié)點(diǎn)擁有一個(gè)給定標(biāo)識(shí)的概率僅僅是其父節(jié)即在時(shí)間tvu內(nèi)，從狀態(tài)x轉(zhuǎn)換到狀態(tài)y的概率，其中v、u代表系統(tǒng)發(fā)生樹中的節(jié)點(diǎn)。假設(shè)在進(jìn)化過程中特征的出現(xiàn)頻率是恒定的，其值P(x)。假設(shè)有一個(gè)矩陣M，它是關(guān)于n個(gè)物種實(shí)際觀察值，M描述每個(gè)物種m個(gè)特征的具體取值。同時(shí)假設(shè)存在一棵樹T，其葉節(jié)點(diǎn)（如vu對應(yīng)于這些物種，而樹中的分支代表物種之間的距離tvu，求該樹的似然值L=PM|T)。首先處理最簡單的情況，即每個(gè)物種僅有一個(gè)特征。由于樹種節(jié)點(diǎn)的標(biāo)記未知，需要考慮所有可能的樹，并加和對應(yīng)的結(jié)果。例如，對于圖6.10所示的樹，可以寫出公式：LP(M|T)P(r)Prs(trs)Prv(trv)Pvu(tvu)Pvw(tvw 其中r、v是節(jié)點(diǎn)可能的標(biāo)識(shí)r v wu圖6.10系統(tǒng)發(fā)生樹似然值的計(jì)算將上述計(jì)算公式推廣到多個(gè)特征，只需分別對每個(gè)特征進(jìn)行反復(fù)的計(jì)算，然后將結(jié)果相乘（因?yàn)榧俣ㄌ卣鲀蓛瑟?dú)立。推廣的計(jì)算公式為：LP(M|T) P(Mj|Tcharacter P(Mj,R|Tcharacterjreconstruction P(root)Puv(tuv （6-characterjreconstruction 利用最大似然法得到樹一般是有根樹，然而如果特征替換是可逆的，即Pxy(tPyx(t)，則所對于一個(gè)特征j，定Cj(x,v)P(根為vCj(x,v)是關(guān)于子樹節(jié)點(diǎn)v的條件概率，即節(jié)點(diǎn)v的第j個(gè)特征具有標(biāo)識(shí)x成為子樹的可能性。下首先進(jìn)行初始化工作，對于所有的葉節(jié)點(diǎn)v和標(biāo)識(shí)符號(hào)xC(x,v)

if(vj （6-u和w，x計(jì)算 Cj(x,v)Cj(y,u)Pxy(tvu)Cj(y,w)Pxy(tvw （6- 最終結(jié)m LCj(x,root)P( （6-j1 下面如何根據(jù)給定的樹的拓?fù)浣Y(jié)構(gòu)尋找最優(yōu)分支長度。首先假設(shè)除trv之外，所有的分支長度已知。如果r根節(jié)點(diǎn)，則 logLlogP(x)Cj(x,r)Pxy(trv)Cj(y, （6-j x, 可以采用許多不同的方法使logL最大，如Newton-Raphson方法，或者最大期望EM算法。如果r不是樹根，也可以應(yīng)用相似的方法。如果對于所有x、y、t，Pxy(t)=Pyx(t),則樹根可以被賦予任何節(jié)點(diǎn)，而不影響L的值。換句話說，為了尋找節(jié)點(diǎn)r和v之間最優(yōu)的分支長度，僅需要處理來自r接下來的一步是在沒有任何關(guān)于分支長度先驗(yàn)信息的情況下，尋找最優(yōu)的分支長度。主要的問題是，如果某個(gè)分支的長度發(fā)生變化，不能保證其它分支依然是最優(yōu)的長度。在實(shí)際處理中，可以采用局部處理方式，在某個(gè)時(shí)刻僅優(yōu)化一條邊，通過遍歷樹，逐步處理所有的邊，其最終結(jié)果與最優(yōu)的系統(tǒng)發(fā)生樹接近。3、相容性方法在解決系統(tǒng)發(fā)生問題時(shí)，定義目標(biāo)函數(shù)考慮的另一方面是相容性(comatiilt)，即與一棵樹相一致的特征個(gè)數(shù)。很顯然，相容的特征數(shù)越多越好。相容性方法實(shí)際上是簡約方法的一種簡化，在所有的特征都是二值的情況下，這種方法非常有用。假設(shè)一個(gè)二值特征有兩個(gè)可能的取值“0”和“1S代表一組分類單元，T是關(guān)于S的系統(tǒng)發(fā)生樹。如果在解釋葉節(jié)點(diǎn)中分類單元的特征數(shù)據(jù)時(shí)，只需要沿T的一條邊變化，則稱該特征與系統(tǒng)發(fā)生樹T是相容的。圖6.11是一棵具有4個(gè)分類單元的系統(tǒng)發(fā)生樹，其中在圖6.1(a)中特征是相容的，只需要一條邊變化即可（標(biāo)記星號(hào)的邊；而在圖6.11(b)中，特征是不相容的，因?yàn)樾枰獌蓷l邊發(fā)生變化。*** *** 圖6.11具有4個(gè)分類單元的系統(tǒng)發(fā)生樹：(a)相容特征；(b)不相容定義：對于一個(gè)具有k個(gè)值的特征c，稱c與樹T相容，當(dāng)且僅當(dāng)T的節(jié)點(diǎn)存在一種標(biāo)記方式，使得c變化總數(shù)為k-1。在簡約方法中，力求找到最少的分支變化的系統(tǒng)發(fā)生樹，使之與給定的各個(gè)分類單元特征值匹配。如果某個(gè)特征值在各個(gè)葉節(jié)點(diǎn)中出現(xiàn)n種狀態(tài)，則至少需要有n-1次分支變化。相容性方法將樹分成兩種類型，即只需要最小變化的樹和其它樹，而最大簡約法要區(qū)分各種不同的樹。相比之下，相容性方法僅需要維護(hù)一小部分關(guān)于樹相對性能的信息。給定一個(gè)DNA單堿基位點(diǎn)，如果所有物種在此位點(diǎn)或T‘C’,則該特征的取值數(shù)為2，而不是4。在下面的中，假設(shè)所有特征的取值都是二態(tài)的，即只有兩種取值，分別用0和1可以證明，在二態(tài)的情況下，相容性是簡約性的一種特例。只要在最大簡約法中，對于每個(gè)變化至少兩次的特征，規(guī)定其代價(jià)為2。對于一棵樹Tni代表變化i次的特征個(gè)數(shù)，n0是葉節(jié)點(diǎn)中值恒定的特征個(gè)數(shù)，n1是需要發(fā)生一次變化的特征個(gè)數(shù)，則樹T的總代價(jià)S(T)=n1+2(n-n0-n1)=2n-2n0- （6-其中n是總的特征個(gè)數(shù)，n和n0是固定不變的。于是代價(jià)最小化等價(jià)于使n1最大，而1征的個(gè)數(shù)。這樣給出了一種計(jì)算最優(yōu)相容樹的思路，但這需要解決復(fù)雜的簡約問題，而簡約問題又是一個(gè)NP-完全問題，所以必須考慮其他的方法。處理相容問題的第一步與最大簡約法相似。給定一棵葉節(jié)點(diǎn)已標(biāo)記的樹T，搜索最佳的相容代用Fitch算法M的情況下，尋找最佳的系統(tǒng)發(fā)生樹。Sc1c2c1、c2相容的系統(tǒng)發(fā)生樹？假設(shè)有兩個(gè)特征c1c2,如果存在一棵樹T，使得c1和c2各自與T相容，則稱特征c1c2是兩兩相PC(c1,c2kc1、c2、…、ckT，使得c1、c2、…、ck都分別與Tc1、c2、…、ck是連帶（jointlycompatible）6.1（兩兩相容性檢Wilson,1965）M是分類單元特征取值矩陣，對于特征i,j，定義集合Sij, ={(x,y)|存在分類單元k使得Mki=x并且Mkj=y} 則當(dāng)且僅當(dāng)S{0,1}2，PC(c,c’)成立（PC(c,c’)代表c和c’兩兩相容。這里 014 證明：假設(shè)S{0,1}2，集合S最多有3元素。在第一種情況下，S僅有一個(gè)元素，則特征c和c’各自有一個(gè)單獨(dú)的狀態(tài)，但是這不可能，因?yàn)樗奶卣鞫际嵌堤卣?。在第二種情況下，Scc’有兩個(gè)元素，則實(shí)際上可以將上述兩個(gè)特征視為一個(gè)二值特征。 S有三個(gè)元素，可以假設(shè){0,1}2-

={(x,y)}，即集合

中不包括特征值對(x,y)。圖6.12與兩個(gè)特征相容的樹的基本結(jié)構(gòu)，其特征組合值為（x,y）,(x,y),(x,y)。這里符號(hào)“”代表“取反”操作。圖6.12中每個(gè)三角形表示一棵子樹，每棵子樹中兩個(gè)特征的值不變。沿粗線段標(biāo)記的y圖6.12一棵與兩個(gè)特征相容的樹，有三個(gè)組合值舉例說明定理6.1。假設(shè)有5個(gè)種屬A、B、C、D、E，兩個(gè)特征c1和2，各個(gè)種屬特征取值情況見表6.(Flentin,198)。為c1和2建立一個(gè)22的特征值組合表（相當(dāng)于定理6.1中的），表元素（i，j）的值反應(yīng)兩個(gè)特征取值的組合情況。如果某個(gè)種屬的兩個(gè)特征值分別為i和j，則特征值組合表元素（ij的值為“1”；如果找不到這樣的組合，則表元素（ij的值為“0（如表6.6所示）。對于這樣的特征值組合表，特征c1和c2是兩兩相容的當(dāng)且僅當(dāng)特征值組合表至少存在一個(gè)“0”元素。表6.5ABCDE1011000110表6.6c1=c1=c2=11c2=01假設(shè)特征值組合表中存在“0”元素，那么在所有4種特征取值組合中，有的組合沒有出現(xiàn)。（i，j）T，c1=1-iT1下，而將所有特征值c1=i的種屬放在其它子樹中。令c1=i，c2=1-j為T的祖先節(jié)點(diǎn)。顯然，c1T因?yàn)橹恍枰谶B接子樹T1根節(jié)點(diǎn)的分支上一個(gè)變化即可。另外，當(dāng)c1=1-i時(shí)，對于特征c2只T16.5T1A、C、D。Tc1=0，c2=1-1=0。很顯然，Tc1的取值分為左右兩個(gè)部分，c1TT1c2的取值也分為兩個(gè)部分，因此c2與T也是相容的。 A(1,0) 6.136.2（兩兩相容性定理,Estabrook,1976）在一個(gè)二值特征集合C中，所有特征是連帶相容的，c,c’C,PC(c,c’)成立。利用數(shù)學(xué)歸納證明。如果特征數(shù)為2，存在兩個(gè)特征c1和c2，則定理6.1和上面的例子已經(jīng)說明可以構(gòu)造一棵樹T，使得c1、c2分別與T相容。這表明歸納基礎(chǔ)成立。假設(shè)定理6.2對于所有特征數(shù)m<n皆成立，則對于n個(gè)特征，任意選擇一個(gè)特征c，根據(jù)c的取值將所有物種分為兩個(gè)部分。根據(jù)條件，每個(gè)特征c’與c都是兩兩相容的，由定理6.1可知，特c’與c的某種取值組合一定不會(huì)在S中的物種出現(xiàn)。令這樣的取值組合為（c=i，c’=j），于是對于所有特征c值等i的種屬，它們的特征c’值只能為1-j。這樣根據(jù)c將特征C分為兩個(gè)集合，C0C1。C0包含所有滿足下列條件的特征：如果c=0，這些特征將取多個(gè)值。C1包含所有滿足下列條件的特征：如果c=1，這些特征將取多個(gè)值。顯然，屬于C0的特征在c=1的情況下只能取C1c=0的情況下也只能取一個(gè)值。S0S1c=0c=1v0v1C0的（或C1）的特征c’，v0（或者v1）的特征c’的取單個(gè)值，其值等于所有c=1（c=0）的種屬的c’值。由于所有C0v0的狀態(tài)與集合S1中的其它種屬相符合，因此C0中的特征在種屬集合S0{v0}中是兩兩相容的。同樣，C1中的特征在種屬集合S1{v1}中是兩兩相容的。由于C0和C1的特征個(gè)數(shù)小于n，根據(jù)歸納假設(shè)，C0、C1中特征是連帶相容的。令T0（T1）是定義在S0{v0}（S1{v1}）的樹，在這樣的樹中，屬于C0（C1）的特征是連帶相容的。為了構(gòu)造一棵樹T，使所有屬于C的特征連帶相容，在T0T1中尋找種屬v0v1的位置，然后用一條公共的邊eT0和T1e替代原來連接到v0和v1的邊。通過上述操作形成樹T，Tc相容，ceC0c’，T1中的所有種屬與v0具有同樣的值，因此如果v0T1替換，不需要額外的變化。這樣，如果c’與T0相容，c’也與T相容。對于屬于C1的特征也有同樣的結(jié)論。由此可以斷定，每個(gè)屬于C的特征與T是相容，集合C中的特征是連帶相容的。根據(jù)上述定理，解決“最大相容”的問題被簡化為尋找最大的特征連帶相容集合，歸結(jié)為在兩兩相容圖中尋找最大完全子圖。兩兩相容圖G定義如下:G=(V,E);V={v1,v2,…,vm}; （6-這里，V代表圖中頂點(diǎn)的集合，而E代表分支或者邊的集合。圖論中有許多尋找最大完全子圖的有效算法，比如基于分支約束的尋找最大完全子圖算法。一般而言，對于相同的數(shù)據(jù)，相容性方法運(yùn)算速度快于簡約法。i*在相容圖中找到最大完全子圖，意味著找到最大的連帶相容特征集合C*，接下來的任務(wù)是構(gòu)造系統(tǒng)發(fā)生樹。只要按照C*中的每個(gè)特征相繼分割物種集合。在下面的算法中，給定矩陣M和特征集合C*，反復(fù)構(gòu)造無根樹。在每一步，利用C*中的一個(gè)特征擴(kuò)展樹T。集合C保存到目前為止尚未用到的特征。T的每個(gè)節(jié)點(diǎn)或者是沒有標(biāo)記，或者標(biāo)記為Lv{1,2,…,n}，代表種屬。對每個(gè)特征c和標(biāo)記的節(jié)點(diǎn)v,令Lv()L{|k=i}，k代表特征c的取值。算法過程如下：i*初始初始T，使T僅有一個(gè)節(jié)點(diǎn)r，標(biāo)記為循C中選擇一個(gè)特征

r={1,2,…,n}，并C=Cn為種屬的對于V(T)vLv元素的個(gè)數(shù)超過1，則 如果|Lvi(c)|0（i=0,1），則在T中增加兩個(gè)新v0v1，分別標(biāo)L0(c)、L1(c)，v0和v1到v 修改C,使得C=C重復(fù)執(zhí)行上述循環(huán)過程，直到C為空算法執(zhí)行的結(jié)果是產(chǎn)生無根節(jié)點(diǎn)的系統(tǒng)發(fā)生樹，葉節(jié)點(diǎn)全部被標(biāo)記，至于節(jié)點(diǎn)的標(biāo)記工作相對簡單，可以用Fitch算法。第四節(jié)１、各種方法比較在距離法中，連鎖聚類方法比較簡單，非分組平均法比較實(shí)用，當(dāng)使用的距離數(shù)據(jù)是來源于多個(gè)的分析結(jié)果時(shí)，利用非分組平均法能得到可靠的系統(tǒng)發(fā)生樹。對于離散特征分析方法，在不同世系間進(jìn)化速率相差較大，并且進(jìn)化速率恒定而樹的分支很短的情況下，最大簡約法并不能對一個(gè)真正的系統(tǒng)發(fā)生樹作出始終一致的判斷。即使有時(shí)最大簡約法能得到一個(gè)始終一致的判斷，但它獲得一個(gè)正確樹的效率通常要比鄰近和最大似然法低(常青等,1998)。但在序列趨異程度較小、核苷酸替換的速率或多或少的恒定、沒有很高的轉(zhuǎn)換與顛換比及很強(qiáng)的Ｇ＋Ｃ含量偏差、所分析的核苷酸數(shù)量較多（大于幾千）的情況下，最大簡約法仍是一種較好的系統(tǒng)發(fā)生樹構(gòu)建法。另一方面，與距離法和最大似然法不同，最大簡約法能利用序列中堿基的與缺失信息。在實(shí)際使用最大簡約法和最大似然法構(gòu)建系統(tǒng)發(fā)生樹時(shí)，當(dāng)給定的分類單元數(shù)量m（比如m<10可通過計(jì)算機(jī)對所有可能的樹作窮盡搜索，確定最理想的樹。這樣做雖然非常耗時(shí)，但還是有可能的。當(dāng)m大于10時(shí)，就不1)分支約束法，從一組具有潛在可能的樹中確定優(yōu)化的系統(tǒng)發(fā)生樹。該方法能保證獲得很好的結(jié)果，但當(dāng)m大于或等于20時(shí)計(jì)算量仍然很大；(2)啟發(fā)式搜索法，該法在分析中只對少部分的可能樹進(jìn)行比較，故m可取較大值，但此法不能保證發(fā)現(xiàn)最好的樹。２、系統(tǒng)發(fā)生在系統(tǒng)發(fā)生推斷中，統(tǒng)計(jì)分析的系統(tǒng)誤差和隨機(jī)誤差均影響所建樹的可靠性。對隨機(jī)誤差的影響，常采用一定的統(tǒng)計(jì)檢驗(yàn)來分析獲得的系統(tǒng)發(fā)生樹的可靠性。一種是利用某一參量來對所獲得樹及其相近樹進(jìn)行結(jié)構(gòu)差異檢驗(yàn)。在最大似然法中常利用似然值。這種方法是一種保守檢驗(yàn)，而且檢驗(yàn)的程序非常復(fù)雜，需要很大的計(jì)算機(jī)內(nèi)存。另一種類型是分析每個(gè)分支可靠性，其中常用的方法有(常青等,198)：（confidenceprobabilityCP，CP值越高，分支的長度也就越可靠。通常，當(dāng)≥0.95或0.99時(shí)，可認(rèn)為該分支的長度在統(tǒng)計(jì)上有效自舉檢驗(yàn)，這是一種重抽樣技術(shù)，可用來估計(jì)在取樣分布不知道或難以分析得到的情況下分支與統(tǒng)計(jì)有關(guān)的變異性。通過自舉檢驗(yàn)，可得到一個(gè)自舉置信水平（boottapcnieneleel，簡稱BL。計(jì)算機(jī)模擬已表明當(dāng)BCL＞09時(shí)，CP值與BCL值二者是非常相近的。與自舉檢驗(yàn)相近的另一種重抽樣方法是棄半檢驗(yàn)。有研究表明，在研究的核苷酸數(shù)量較少的情況下，即使CP或BCL值達(dá)到9%，所獲得的結(jié)果仍然不十分。因此，在研究中應(yīng)從不同的中盡可能分析較多數(shù)量的核苷酸，特別在研究不同生物間進(jìn)化關(guān)系時(shí)，因?yàn)椴煌馐艿倪M(jìn)化壓力不同。對系統(tǒng)誤差，需要降低它們對系統(tǒng)發(fā)生分析影響，增加所建系統(tǒng)發(fā)生樹的可靠性。通常采用的（1）重新考慮分析時(shí)的假定，變換分析方法；（2）除去樹中的長分支，因?yàn)橐豢脴渲腥绻哂性S多長分支，將會(huì)使分析中的誤差復(fù)雜化；（3）（4）對某些特征或某一特征狀態(tài)進(jìn)行處理等。第五節(jié)本節(jié)通過實(shí)例說明系統(tǒng)發(fā)生分析的過程。這里使用莫斯科國立大學(xué)的系統(tǒng)發(fā)生樹分析的對象是13條來自不同物種的同源蛋白質(zhì)。對這些蛋白質(zhì)序列進(jìn)行多重序列比對，其結(jié)果見圖6.14所示。根據(jù)序列比對結(jié)果計(jì)算序列之間的距離，生成距離矩陣。然后分別利用聚類方法和拓?fù)鋵W(xué)方法建立系統(tǒng)發(fā)生樹。拓?fù)鋵W(xué)算法首先優(yōu)化系統(tǒng)發(fā)生樹的結(jié)構(gòu)，確定樹節(jié)點(diǎn)之間的分支連接，然后再計(jì)算分支的長度。該算法的基礎(chǔ)是拓?fù)湎嗨圃?。圖6.15是通過聚類分析得到的系統(tǒng)發(fā)生樹，用Phylip格式表示如下：HumanHumanFLRTPKIVSGKDYNVTANSKLVIITAGARQChickenFLKTPKITSGKDYSVTAHSKLVIVTAGARQDogfishFLHTAKIVSGKDYSVSAGSKLVVITAGARQLampreyFLKTAKIVADKDYSVTAGSRLVVVTAGARQBarleyFLPRVRI-SGTDAAVTKNSDLVIVTAGARQMaizeyFLPRTRLVSGTDMSVTRGSDLVIVTAGARQLacto_caseiFTSPKKIYSA-EYSDAKDADLVVITAGAPQBacillus_steaFAPKPVDIWHGDYDDCRDADLVVICAGANQLacto_plantFTAPKKIYSG-EYSDCKDADLVVITAGAPQTherma_mariFTRRANIYAG-DYADLKGSDVVIVAAGVPQBifidoFYPTVSIDGSDDPEICRDADMVVITAGPRQThermus_aquaFAHPVWVRSGW-YEDLEGARVVIVAAGVAQMycoplasmaSLPFPISVSRYEYKDLKDADFIVITAGRPQ6.14|||||||||||||||||||||||||||||||| 6.156.14||

||||||||||||||||||||||| |||||||6.166.14156):0.049009):0.024465)。圖6.16是利用拓?fù)浞椒?gòu)造的系統(tǒng)發(fā)生樹，用Phylip格式表示如下：0.000500,Human:0.000500)參考文獻(xiàn)常青,,1998.分子進(jìn)化研究中系統(tǒng)發(fā)生樹的重建.生物多樣性,6(1):55-，，姜成林.1997.構(gòu)建微生物分子分類系統(tǒng)進(jìn)化樹的快速運(yùn)算法與數(shù)據(jù)結(jié)構(gòu).微生，張.2000.分子鐘及其存在的問題.人類學(xué)學(xué)報(bào)，19（2）：151-AdachiJ,HasegamaM.1996.MOLPHYVersion2.3.ProgramsforMolecularphylogeneticsbasedonumlikelihood.Tokyo:InstituteofStatusticalMathematics.AviseJC.1994.MolecularMarkers,NaturalandEvolution.NewYork:Chapman&BaxevanisAD,FrancisBF.1998.Bioinformatics:Apracticalguidetotheysisofgnesandproteins.JohnWiley&Sons,NewYork.BrocchieriL.2001.Phylogeneticinferencesfrommolecularsequences:reviewandcritique.Theor.Popul.Biol.59(1):27-40.BrownRH,etal.1972.Theaminoacidsequenceofcytochromecfromhelixaspersa.Biochem.J.,128:971-974.Cavalli-SforzaLL,EdwardsAW.1967.Phylogeneticysis.Modelsandestimationprocedures.AmJHumGenet1967May;19(3):Suppl19:233.DayWHE.1986.Computationalcomplexityofinferringphylogeniesfromdissimilaritymatrices.BulletinofMathematicalBiology,49:461–467.FengDF,DoolittleRF.1996.Progressivealignmentofaminoacidsequencesandconstructionofphylogenetictreesfromthem.MethodsEnzymoi.266:368-382.FelsensteinJ.1981.EvolutionarytreesfromDNAsequences:aumlikelihoodapproach.J.Mol.Evol.,17:368-376.FelsensteinJ.1988.Phylogeniesfrommolecularsequences:inferenceandreliability.AnnualsRev.Genetics,22:521-565.FelsensteinJ.1996.Inferringphylogeniesfromproteinsequencesbyparsimony,distance,andlikelihoodmethods.MethodsEnzymol1996;266:418-27.FelsensteinJ.1997.ternativeleast-approachtoinferringphylogeniesfrompairwisedistances.Syst.Biol.46：101-111.FelsensteinJ.1998.InferringPhylogenies.ASUWPublishing,Seattle,FelsensteinJ.1998.Phylogeny,II:CompatibilityandumFitchWM,MargoliashE.1967.Constructionofphylogenetictrees.Science,155:279-FitchWM,MargoliashE.1967.Amethodforestimatingthenumberofinvariantaminoacidcodingpositionsinageneusingcytochromecasamodelcase.BiochemGenet.,1(1):65-71.FitchWM.1976.Towarddefiningthecourseofevolution:minimumchangeforaspecifiedtreetopology.SystematicZoology,20:406–416.HarverPH,PagelMD.1991.ThecomparativeMethodinEvolutionaryBiology.OxfordUniversitypress.HeinJ.1990.Unifiedapproachtoalignmentandphylogenies.MethodsEnzymol.183：trees.MathematicalBiosciences,60:133–142.HermannB,HummelS,editors.1994.AncientDNA.Springer-Verlag,NewHuelsenbeckJP,RannalaB.1997.Phylogeneticmethodscomeofage:testinghypothesesinanevolutionarycontext.Science1997Apr11;276(5310):227-32.KimuraM.(ed.)1983.Theneutraltheoryofmolecularevolution.CambridgeUniversityKishinoH,HasegawaM.1989.Evaluationofthe umlikelihoodestimateoftheevolutionarytreetopologies.Comput.Appl.Biosci.，10：189-191.LiW,GraurD.1991.Fundamentalsofmolecularevolution.SinauerAssociates,106-LiWH.1997.MolecularEvolution.Sunderland,MA:SinauerLockhartPJ,SteelMA,HendyMD,PennyD.1994.Recoveringevolutionarytreesunderamorerealisticmodelofsequenceevolution.Mol.Biol.Evol.，11：605-612.MaddisonDR.1991.Thediscoveryandimportanceofm