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

1、第六章 系統(tǒng)發(fā)生分析 主講人：孫 嘯 制作人：劉志華東南大學 吳健雄實驗室第六章 系統(tǒng)發(fā)生分析 主講人：孫 嘯東南大學 吳健雄實驗 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）是指生物形成或進化的歷史系統(tǒng)發(fā)生學(phylogenetics)研究物種之間的進化關系 系統(tǒng)發(fā)生樹（phylogenetic tree）表示形式，描述物種之間進化關系 第一節(jié) 系統(tǒng)發(fā)生與系統(tǒng)發(fā)生樹 基本概念：系統(tǒng)發(fā)生分析匯總課件Wi

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

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

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

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

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

7、先）重新計算這個新的對象與其它序列的距離。單連鎖聚類: 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代表任意其它對象。2、連鎖聚類方法選擇距離最小的一對序列單連鎖聚類: d系統(tǒng)發(fā)生分析匯總課件3、非加權分組平均法（Unweighted Pair Group Method with Arithmetic mean, UPGMA） 在平均連鎖聚類過程中，一個新類到其它類之間的距離就是簡單的原距離平均值。 如果類中分類單元個數(shù)不一樣，原距離矩陣

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

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

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

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

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

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

14、節(jié)點v賦予一個集合Sv：如果v是葉節(jié)點 ，則Sv =vc；如果v是內(nèi)部節(jié)點，并且u、w是其子節(jié)點，如果SuSw ，則Sv =SuSw；否則 S(v)=SuSw 。這個過程是從葉節(jié)點開始，直至處理到根節(jié)點。如果用遞歸算法，則應該按后序遍歷方式處理每個節(jié)點。（2）給定集合Sv，為每個內(nèi)部節(jié)點v的特征c賦予值vc。如果v有一個父節(jié)點u滿足ucSv,則將uc賦予vc，否則任取一個tSv賦予vc。這個過程的執(zhí)行方向剛好與上一個過程相反，即從樹根出發(fā)，直至葉節(jié)點為止，最后得到完全標定的樹。應按前序遍歷方式依次處理每個節(jié)點。 單特征Fitch算法：系統(tǒng)發(fā)生分析匯總課件2、最大似然法 最大似然法目標是尋找能夠

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

16、，則稱該特征與系統(tǒng)發(fā)生樹T是相容的。 0 0 1 1 1 0 0 1 * * * （a） (b)具有4個分類單元的系統(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ù)特征值組合表構造的系統(tǒng)發(fā)生樹系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生樹的可靠性對于所構建的系統(tǒng)發(fā)生樹，統(tǒng)計分析的誤差可能會影響所建樹的可靠性。 問題： 整棵樹和它的組成部分（分支）的置信度是多少？ 這樣得到正確的樹的可能性比隨機選出一棵是正確的樹的可能性大多少？ 自舉檢驗參數(shù)檢驗 系統(tǒng)

17、發(fā)生樹的可靠性系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析匯總課件系統(tǒng)發(fā)生分析中可能存在的問題 序列的選擇 基因的水平轉(zhuǎn)移 不同的序列，不同的結果全基因組的系統(tǒng)發(fā)生分析 基于多棵系統(tǒng)發(fā)生樹的方法 基于基因內(nèi)容的方法 基于蛋白質(zhì)折疊結構的方法基于基因次序的方法 基于連接的直向同源蛋白的方法基于代謝途徑（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ā)生分析實例分析的對象13條來自不同物種的同源蛋白質(zhì)（1）多重序列比對 （2）構建系統(tǒng)發(fā)生樹系統(tǒng)發(fā)生分析實例分析的對象系統(tǒng)發(fā)生分析匯總課件根據(jù)序列比對結果計算序列之間的距離，生成距離矩陣。然后分別利用聚類方法和拓撲學方法建立系統(tǒng)發(fā)生樹