系統(tǒng)發(fā)生分析匯總課件

1、第六章 系統(tǒng)發(fā)生分析 主講人：孫 嘯 制作人：劉志華東南大學(xué) 吳健雄實(shí)驗(yàn)室第六章 系統(tǒng)發(fā)生分析 主講人：孫 嘯東南大學(xué) 吳健雄實(shí)驗(yàn) Charles Darwin (1809-1882) Charles Darwin (1809-1882)系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析匯總課件第一節(jié) 系統(tǒng)發(fā)生與系統(tǒng)發(fā)生樹 基本概念：系統(tǒng)發(fā)生（phylogeny）是指生物形成或進(jìn)化的歷史系統(tǒng)發(fā)生學(xué)(phylogenetics)研究物種之間的進(jìn)化關(guān)系 系統(tǒng)發(fā)生樹（phylogenetic tree）表示形式，描述物種之間進(jìn)化關(guān)系 第一節(jié) 系統(tǒng)發(fā)生與系統(tǒng)發(fā)生樹 基本概念：系統(tǒng)發(fā)生分析匯總課件Wi

2、lli Hennig (1913-1976)系統(tǒng)發(fā)生學(xué)（分支學(xué)）創(chuàng)始人Willi Hennig (1913-1976) 經(jīng)典系統(tǒng)發(fā)生學(xué)主要是物理或表型特征如生物體的大小、顏色、觸角個(gè)數(shù) 現(xiàn)代系統(tǒng)發(fā)生學(xué)利用從遺傳物質(zhì)中提取的信息作為物種特征具體地說就是核酸序列或蛋白質(zhì)分子 關(guān)于現(xiàn)代人起源的研究:線粒體DNA所有現(xiàn)代人都是一個(gè)非洲女性的后代 經(jīng)典系統(tǒng)發(fā)生學(xué)分類單元（物種或序列）物種之間的進(jìn)化關(guān)系 分類單元物種之間的進(jìn)化關(guān)系 系統(tǒng)發(fā)生樹性質(zhì)： （1）如果是一棵有根樹，則樹根代表在進(jìn)化歷史上是最早的、并且與其它所有分類單元都有聯(lián)系的分類單元； （2）如果找不到可以作為樹根的單元，則系統(tǒng)發(fā)生樹是無根樹；

3、 （3）從根節(jié)點(diǎn)出發(fā)到任何一個(gè)節(jié)點(diǎn)的路徑指明進(jìn)化時(shí)間或者進(jìn)化距離。 系統(tǒng)發(fā)生樹性質(zhì)：對(duì)于給定的分類單元數(shù)，有很多棵可能的系統(tǒng)發(fā)生樹，但是只有一棵樹是正確的。系統(tǒng)發(fā)生分析的目標(biāo)尋找這棵正確的樹對(duì)于給定的分類單元數(shù)，有很多棵可能的系統(tǒng)發(fā)生樹，但是只有一棵、系統(tǒng)發(fā)生分析步驟（1）序列比對(duì)（2）確定替換模型（3）構(gòu)建系統(tǒng)發(fā)生樹（4）評(píng)價(jià)所建立的樹、系統(tǒng)發(fā)生分析步驟（1）序列比對(duì)計(jì)算序列之間距離 令S(i,j)是序列i和序列j比對(duì)位置得分的加權(quán)和 歸一化的距離： 其中Sr(i,j)是序列i和j隨機(jī)化之后的比對(duì)得分的加權(quán)和，Smax(i,j)是可能的最大值令Sr(i,j)=0 為了適合于處理相似性較小的序

4、列，可以進(jìn)一步修改距離計(jì)算公式 計(jì)算序列之間距離 歸一化的距離：兩類數(shù)據(jù)：距離離散特征 離散特征數(shù)據(jù)可分為 二態(tài)特征例如：DNA序列上的某個(gè)位置如果是剪切位點(diǎn) 多態(tài)特征例如：某一位置可能的堿基有、或 兩類數(shù)據(jù)：系統(tǒng)發(fā)生樹的構(gòu)建方法分為兩大類：基于距離的構(gòu)建方法非加權(quán)組平均法 鄰近歸并法 Fitch-Margoliash法 最小進(jìn)化方法 基于離散特征的構(gòu)建方法最大簡約法 最大似然法 進(jìn)化簡約法 相容性方法 系統(tǒng)發(fā)生樹的構(gòu)建方法分為兩大類：根據(jù)建樹算法在執(zhí)行過程中采用的搜索方式，系統(tǒng)發(fā)生樹的構(gòu)建方法也可以分為以下3類。 （1）窮盡搜索方法 即產(chǎn)生所有可能的樹，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。 （

5、2）分支約束方法 即根據(jù)一定的約束條件將搜索空間限制在一定范圍內(nèi)，產(chǎn)生可能的樹，然后擇優(yōu)。 （3）啟發(fā)式或經(jīng)驗(yàn)性方法 根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間，提高計(jì)算速度。 根據(jù)建樹算法在執(zhí)行過程中采用的搜索方式，系統(tǒng)發(fā)生樹的構(gòu)建方法 第二節(jié) 基于距離的系統(tǒng)發(fā)生樹構(gòu)建方法基本思路是：給定一種序列之間距離的測度，在該距離測度下構(gòu)建一棵系統(tǒng)發(fā)生樹，使得該樹能夠最好地反映已知序列之間的距離。 第二節(jié) 基于距離的系統(tǒng)發(fā)生樹構(gòu)建方法基本思路是：10條核酸序列的距離矩陣 10條核酸序列的距離矩陣 例，如果有三個(gè)物種，其兩兩距離如下： dab = 0.08 dac = 0.45 dbc = 0.43通過

6、求解方程，得到如圖6.2所示的一棵樹。 例，如果有三個(gè)物種，其兩兩距離如下：通過求解方程，得到1、最小二乘法目標(biāo)是構(gòu)造一棵樹T，該樹的葉節(jié)點(diǎn)代表物種，用該樹預(yù)測物種之間的距離。通過優(yōu)化，使下式最小化： 這里，Dij為物種i和j的實(shí)際觀察距離（或序列之間的計(jì)算距離），dij是物種i和j在系統(tǒng)發(fā)生樹T 中的距離，Wij是與物種i和j相關(guān)的權(quán)值。SSQ（T）是樹T所有預(yù)測值與實(shí)際觀察值偏差的累加和。權(quán)值Wij一般為1，或 Wij =1/ Dij21、最小二乘法目標(biāo)是構(gòu)造一棵樹T，該樹的葉節(jié)點(diǎn)代表物種，用該2、連鎖聚類方法選擇距離最小的一對(duì)序列將這兩個(gè)序列合二為一，形成一個(gè)新的對(duì)象（代表這兩個(gè)序列的祖

7、先）重新計(jì)算這個(gè)新的對(duì)象與其它序列的距離。單連鎖聚類: d(x,u)=min(d(y,u),d(z,u)最大連鎖聚類： d(x,u)=max(d(y,u),d(z,u)平均連鎖聚類： d(x,u)=1/2(d(y,u)+d(z,u)其中x代表y和z的合并，u代表任意其它對(duì)象。2、連鎖聚類方法選擇距離最小的一對(duì)序列單連鎖聚類: d系統(tǒng)發(fā)生分析匯總課件3、非加權(quán)分組平均法（Unweighted Pair Group Method with Arithmetic mean, UPGMA） 在平均連鎖聚類過程中，一個(gè)新類到其它類之間的距離就是簡單的原距離平均值。 如果類中分類單元個(gè)數(shù)不一樣，原距離矩陣

8、中各個(gè)距離值對(duì)新距離計(jì)算的貢獻(xiàn)就不一樣，或者說是經(jīng)過“加權(quán)”的，稱這樣的聚類為加權(quán)分組平均。 在非加權(quán)分組平均法中，在計(jì)算新分類到其它分類之間的平均距離時(shí)按照各分類中分類單元的數(shù)目進(jìn)行加權(quán)處理。 3、非加權(quán)分組平均法（Unweighted Pair GrUPGMA算法的執(zhí)行過程如下：(1) 初始化：使每個(gè)物種自成一類，如果有n個(gè)物種，則開始時(shí)共有n個(gè)類，每個(gè)類的大小為1，分別用n個(gè)葉節(jié)點(diǎn)代表每個(gè)類； (2)執(zhí)行下列循環(huán)：l尋找具有最小距離Dij的兩個(gè)類i、j；建立一個(gè)新的聚類（ij)l 連接i和j形成新節(jié)點(diǎn) (ij)，生長兩個(gè)新的分支，將i 和j 連接到(ij)，分支的長度為Dij/2；l計(jì)算

9、新分類到其它類的距離其中ni、nj、(ni+nj)分別為i類、j類、(ij)類的元素個(gè)數(shù)；l 在距離矩陣中刪除與類i和類j相應(yīng)的行和列，為類(ij)加入新的行和列； 重復(fù)循環(huán)，直到僅剩一個(gè)類為止。 UPGMA算法的執(zhí)行過程如下：系統(tǒng)發(fā)生分析匯總課件4、鄰近歸并法 基本思想：在進(jìn)行類的合并時(shí)，不僅要求待合并的類是相近的，同時(shí)還要求待合并的類遠(yuǎn)離其它的類。 重建時(shí)將距離最小的兩個(gè)葉節(jié)點(diǎn)連接起來，合并這兩個(gè)葉節(jié)點(diǎn)所代表的分類，形成一個(gè)新的分類。在樹中增加一個(gè)父節(jié)點(diǎn)，并在距離矩陣中加入新的分類，同時(shí)刪除原來的兩個(gè)分類。 重復(fù)上一次循環(huán), 直到只剩一個(gè)類為止。4、鄰近歸并法 基本思想：在每一次的循環(huán)中，

10、在樹中尋找兩個(gè)物種的直接祖先。對(duì)于節(jié)點(diǎn)i，到其它節(jié)點(diǎn)的距離ui 按下式進(jìn)行估算：ui = ki(Dik/(n-2)這里Dik是分類i和分類 k之間的距離選擇Dij-ui-uj最小的一對(duì)節(jié)點(diǎn)i 和節(jié)點(diǎn)j 進(jìn)行歸并在每一次的循環(huán)中，在樹中尋找兩個(gè)物種的直接祖先。對(duì)于節(jié)點(diǎn)i，系統(tǒng)發(fā)生分析匯總課件算法如下：（1）初始化（與UPGMA一樣）（2）循環(huán) 對(duì)于所有的分類單元i，計(jì)算ui = kI (Dik/(n-2)； 選擇一對(duì)分類單元i 和j ，使Dij-ui-uj最?。?將i和j歸并為新的類 (ij)，在樹中添加一個(gè)新的節(jié)點(diǎn)，代表新生成的分類，計(jì)算從i和j到新節(jié)點(diǎn)的分支長度； di,(ij） = 1/2

11、Di,j +1/2(ui-uj), dj,(ij） = 1/2Di,j +1/2(uj-ui) 計(jì)算新類與其它類的距離； D(ij）,k = 1/2(Di,k + Dj,k - Di,j) 刪除聚類i和j，添加新類 (ij)； 如果有兩個(gè)以上的分類存在，則繼續(xù)執(zhí)行循環(huán)；否則用長度為Di,j的分支連接剩余的兩個(gè)類 。算法如下：系統(tǒng)發(fā)生分析匯總課件圖6.7 利用鄰近歸并算法構(gòu)造的系統(tǒng)發(fā)生樹圖6.7 利用鄰近歸并算法構(gòu)造的系統(tǒng)發(fā)生樹圖6.8 利用鄰近歸并算法構(gòu)造的系統(tǒng)發(fā)生樹圖6.8 利用鄰近歸并算法構(gòu)造的系統(tǒng)發(fā)生樹第三節(jié) 基于特征的系統(tǒng)發(fā)生樹構(gòu)建方法一般問題：給定n個(gè)物種 m個(gè)用以描述物種的特征每個(gè)

12、物種所對(duì)應(yīng)的特征值構(gòu)建一棵系統(tǒng)發(fā)生樹，使得某個(gè)目標(biāo)函數(shù)最大。 第三節(jié) 基于特征的系統(tǒng)發(fā)生樹構(gòu)建方法一般問題：輸入一般為nm的特征矩陣M在構(gòu)建系統(tǒng)發(fā)生樹假設(shè)特征是相互獨(dú)立的，即一個(gè)特征的變化不影響另一個(gè)特征。另外，還假設(shè)在進(jìn)化過程中，兩個(gè)物種分叉后獨(dú)立進(jìn)化，互不影響。 輸入一般為nm的特征矩陣M1、最大簡約法目標(biāo)：構(gòu)造一棵反映分類單元之間最小變化的系統(tǒng)發(fā)生樹。所謂簡約就是使代價(jià)最小。對(duì)于系統(tǒng)發(fā)生樹最直觀的代價(jià)計(jì)算就是沿著各個(gè)分支累加特征變化的數(shù)目。1、最大簡約法目標(biāo)： 甲 乙 丙 丁 戊 節(jié)點(diǎn)1 節(jié)點(diǎn)3 節(jié)點(diǎn)2 根節(jié)點(diǎn)系統(tǒng)發(fā)生分析匯總課件最大簡約法的處理過程：（1）針對(duì)待比較的物種，選擇核酸或蛋

13、白質(zhì)序列。有些分子比其它分子變化慢，適合于進(jìn)行距離分析，例如哺乳類的線粒體DNA、管家蛋白質(zhì)等；（2）比較各個(gè)序列，產(chǎn)生序列的多重比對(duì)，確定各個(gè)序列符號(hào)的相對(duì)位置；（3）根據(jù)每個(gè)序列比對(duì)的位置（即多重對(duì)比排列的每一列），確定相應(yīng)的系統(tǒng)發(fā)生樹，該樹用最少的進(jìn)化動(dòng)作產(chǎn)生序列的差異，最終生成完整的樹。 最大簡約法的處理過程：對(duì)于一棵系統(tǒng)發(fā)生樹T 假設(shè)樹中的節(jié)點(diǎn)用V(T)表示，樹的邊用E(T)， 以u(píng)j、vj分別表示節(jié)點(diǎn)u和v的第j個(gè)特征， 則樹T的代價(jià)為：系統(tǒng)發(fā)生分析匯總課件單特征Fitch算法：首先對(duì)于每個(gè)待分析的物種，分配一個(gè)葉節(jié)點(diǎn)v，其值vc取對(duì)應(yīng)物種的特征值。然后執(zhí)行下面兩步：(1) 給每個(gè)

14、節(jié)點(diǎn)v賦予一個(gè)集合Sv：如果v是葉節(jié)點(diǎn) ，則Sv =vc；如果v是內(nèi)部節(jié)點(diǎn)，并且u、w是其子節(jié)點(diǎn)，如果SuSw ，則Sv =SuSw；否則 S(v)=SuSw 。這個(gè)過程是從葉節(jié)點(diǎn)開始，直至處理到根節(jié)點(diǎn)。如果用遞歸算法，則應(yīng)該按后序遍歷方式處理每個(gè)節(jié)點(diǎn)。（2）給定集合Sv，為每個(gè)內(nèi)部節(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)。 單特征Fitch算法：系統(tǒng)發(fā)生分析匯總課件2、最大似然法 最大似然法目標(biāo)是尋找能夠

15、以較高概率產(chǎn)生觀察數(shù)據(jù)的系統(tǒng)發(fā)生樹。 對(duì)于給定的一組物種，假設(shè)它們的觀察值為M（M為向量） 選擇一棵樹，使得P(M|T)最大， 2、最大似然法 最大似然法目標(biāo)是尋找能夠以較高概率產(chǎn)生觀察數(shù)系統(tǒng)發(fā)生分析匯總課件3、相容性方法 定義目標(biāo)函數(shù)考慮的另一方面是相容性(compatibility)，即與一棵樹相一致的特征個(gè)數(shù)。很顯然，相容的特征數(shù)越多越好。相容性方法實(shí)際上是簡約方法的一種簡化，在所有的特征都是二值的情況下，這種方法非常有用。 3、相容性方法 定義目標(biāo)函數(shù)考慮的另一方面是相容性(comp令S代表一組分類單元T是關(guān)于S的系統(tǒng)發(fā)生樹如果在解釋葉節(jié)點(diǎn)中分類單元的特征數(shù)據(jù)時(shí)，只需要沿T的一條邊變化

16、，則稱該特征與系統(tǒng)發(fā)生樹T是相容的。 0 0 1 1 1 0 0 1 * * * （a） (b)具有4個(gè)分類單元的系統(tǒng)發(fā)生樹：(a)相容特征；(b)不相容特征。令S代表一組分類單元 0 C(1,1) D(1,1) A(1,0) B(0,0) E(0,0) （T2 ：1,1） （T1 ：1,0） （T：0,0）圖6.13 根據(jù)特征值組合表構(gòu)造的系統(tǒng)發(fā)生樹系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生樹的可靠性對(duì)于所構(gòu)建的系統(tǒng)發(fā)生樹，統(tǒng)計(jì)分析的誤差可能會(huì)影響所建樹的可靠性。 問題： 整棵樹和它的組成部分（分支）的置信度是多少？ 這樣得到正確的樹的可能性比隨機(jī)選出一棵是正確的樹的可能性大多少？ 自舉檢驗(yàn)參數(shù)檢驗(yàn) 系統(tǒng)

17、發(fā)生樹的可靠性系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析中可能存在的問題 序列的選擇 基因的水平轉(zhuǎn)移 不同的序列，不同的結(jié)果全基因組的系統(tǒng)發(fā)生分析 基于多棵系統(tǒng)發(fā)生樹的方法 基于基因內(nèi)容的方法 基于蛋白質(zhì)折疊結(jié)構(gòu)的方法基于基因次序的方法 基于連接的直向同源蛋白的方法基于代謝途徑（pathway）的方法 系統(tǒng)發(fā)生分析中可能存在的問題系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析常用軟件(1) PHYLIP(2) PAUP(3) TREE-PUZZLE(4) MEGA(5) PAML(6) TreeView(7) VOSTORG (8) Fitch programs (9) Phylo_win (10) ARB (11) DAMBE (12) PAL (13) Bionumerics 其它程序見：/phylip/software.html系統(tǒng)發(fā)生分析常用軟件(1) PHYLIP系統(tǒng)發(fā)生分析實(shí)例分析的對(duì)象13條來自不同物種的同源蛋白質(zhì)（1）多重序列比對(duì) （2）構(gòu)建系統(tǒng)發(fā)生樹系統(tǒng)發(fā)生分析實(shí)例分析的對(duì)象系統(tǒng)發(fā)生分析匯總課件根據(jù)序列比對(duì)結(jié)果計(jì)算序列之間的距離，生成距離矩陣。然后分別利用聚類方法和拓?fù)鋵W(xué)方法建立系統(tǒng)發(fā)生樹