生物信息學(xué)分子系統(tǒng)發(fā)育分析課件

1、分子系統(tǒng)發(fā)育分析毛理凱分子系統(tǒng)發(fā)育分析毛理凱本課目錄總括多序列比對(duì)構(gòu)建系統(tǒng)樹(shù)系統(tǒng)發(fā)生軟件2本課目錄總括2一、總括3一、總括3系統(tǒng)發(fā)生學(xué)(phylogenetics)亦稱(chēng)系統(tǒng)學(xué),種系發(fā)生學(xué),種系發(fā)生系統(tǒng)學(xué)(phylogenetic systematics)在希臘文中phylon = tribe, race(種系)genesis = birth研究生物群體(如:物種,種群)之間的進(jìn)化關(guān)系4系統(tǒng)發(fā)生學(xué)(phylogenetics)亦稱(chēng)系統(tǒng)學(xué),種系發(fā)生相關(guān)概念phylogenetic taxonomy(系統(tǒng)發(fā)生分類(lèi)學(xué))是系統(tǒng)學(xué)的一個(gè)分支根據(jù)進(jìn)化相關(guān)度對(duì)生物群體分類(lèi)phylogeny (=phyloge

2、nesis系統(tǒng)發(fā)生)生物群體的產(chǎn)生和進(jìn)化分子系統(tǒng)學(xué)(molecular phylogenetics)將核酸,氨基酸序列作為進(jìn)化特征5相關(guān)概念phylogenetic taxonomy(系統(tǒng)發(fā)生系統(tǒng)發(fā)生樹(shù)(phylogenetic tree)也叫系統(tǒng)樹(shù),進(jìn)化樹(shù)(evolutionary tree),生命樹(shù)(tree of life)對(duì)物種之間的進(jìn)化關(guān)系的一種描述,這些物種被認(rèn)為有共同祖先葉,節(jié)點(diǎn)關(guān)系,時(shí)間6系統(tǒng)發(fā)生樹(shù)(phylogenetic tree)也叫系統(tǒng)樹(shù),有根樹(shù)和無(wú)根樹(shù)有根樹(shù)(rooted tree)有共同祖先無(wú)根樹(shù)(unrooted tree)樹(shù)空間(tree space)從已知序列

3、可以產(chǎn)生許多系統(tǒng)樹(shù)來(lái)自幾何7有根樹(shù)和無(wú)根樹(shù)有根樹(shù)(rooted tree)7無(wú)根樹(shù)和有根樹(shù)的關(guān)系(1)從一棵有根樹(shù)總可以產(chǎn)生一棵無(wú)根樹(shù)而從無(wú)根樹(shù)產(chǎn)生有根樹(shù)需要額外的數(shù)據(jù)8無(wú)根樹(shù)和有根樹(shù)的關(guān)系(1)從一棵有根樹(shù)總可以產(chǎn)生一棵無(wú)根樹(shù)8無(wú)根樹(shù)和有根樹(shù)的關(guān)系(2)一棵無(wú)根樹(shù)可以產(chǎn)生多棵有根樹(shù)9無(wú)根樹(shù)和有根樹(shù)的關(guān)系(2)一棵無(wú)根樹(shù)可以產(chǎn)生多棵有根樹(shù)9Willi Hennig (1913-1976)德國(guó)生物學(xué)家,被認(rèn)為是系統(tǒng)發(fā)生學(xué)和分類(lèi)學(xué)(cladistics; 也叫cladogram)的奠基人據(jù)已知資料來(lái)看,他的觀點(diǎn)并不是最早被闡述屬達(dá)爾文學(xué)派;類(lèi)似的觀點(diǎn)另一學(xué)派的Lamarck和Rosa也有闡述可以認(rèn)

4、為是系統(tǒng)發(fā)生學(xué)的集大成者10Willi Hennig (1913-1976)德國(guó)生物學(xué)家歷史上的系統(tǒng)樹(shù)?？藸?Ernst Haeckel)首次制成了當(dāng)時(shí)所有已知生物的系統(tǒng)樹(shù)(1834-1919)著名的德國(guó)生物學(xué)家,哲學(xué)家,醫(yī)生,教授,藝術(shù)家創(chuàng)建了重演論(recapitulation theory)命名了許多生物學(xué)術(shù)語(yǔ)(如:門(mén),系統(tǒng)發(fā)生,生態(tài)學(xué),原生生物)和幾千物種出版了著名的Kunstformen der Natur (Artforms of Nature)11歷史上的系統(tǒng)樹(shù)海克爾(Ernst Haeckel)首次制成了可能是最早的系統(tǒng)樹(shù)C. Darwin,183712可能是最早的系統(tǒng)樹(shù)C.

5、Darwin,183712特征選取的變遷經(jīng)典系統(tǒng)發(fā)生學(xué)主要是比較大的物理或表型特征如生物體的大小,顏色,牙齒個(gè)數(shù),行為特征缺點(diǎn): 不易量化(連續(xù)), 難以選取合適特征現(xiàn)代系統(tǒng)發(fā)生學(xué)分子水平: 核酸或氨基酸序列優(yōu)點(diǎn): 易量化(離散),易獲取,適于自動(dòng)化,更本質(zhì)例子: (現(xiàn)代人起源) 通過(guò)對(duì)線(xiàn)粒體DNA的研究,認(rèn)為所有現(xiàn)代人都是一個(gè)非洲女性的后代(“夏娃”)13特征選取的變遷經(jīng)典系統(tǒng)發(fā)生學(xué)13系統(tǒng)發(fā)生學(xué)研究方法目的在樹(shù)空間中尋找正確的系統(tǒng)樹(shù)分析步驟多(重)序列比對(duì)(multiple sequence alignment, MSA)構(gòu)建系統(tǒng)樹(shù)評(píng)價(jià)結(jié)果14系統(tǒng)發(fā)生學(xué)研究方法目的14三種構(gòu)建系統(tǒng)樹(shù)中使用

6、的搜索算法窮盡法搜索整個(gè)空間(所有可能的樹(shù)),然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹(shù)分支約束方法根據(jù)一定的約束條件將搜索空間限制在一定范圍內(nèi)啟發(fā)式或經(jīng)驗(yàn)性方法(heuristic)根據(jù)目前的搜索情況指導(dǎo)下一步的搜索方向根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間15三種構(gòu)建系統(tǒng)樹(shù)中使用的搜索算法窮盡法15兩類(lèi)數(shù)據(jù): 距離和離散特征距離描述序列之間的差別 (遺傳距離)一般用距離矩陣(distance matrix)表示距離往往由序列比對(duì)產(chǎn)生(如錯(cuò)配的比例)離散特征二態(tài)特征 (如: DNA序列上的某個(gè)位點(diǎn)是否剪切位點(diǎn))多態(tài)特征 (如: 某一位點(diǎn)可能的堿基有A,T,G,C)16兩類(lèi)數(shù)據(jù): 距離和離散特征距離

7、16兩大類(lèi)構(gòu)建系統(tǒng)樹(shù)的算法基于距離的構(gòu)建方法 (distance-matrix methods)鄰近歸并法 (或稱(chēng)鄰接法,neighbor-joining)非加權(quán)組平均法 (UPGMA)Fitch-Margoliash法 最小進(jìn)化方法基于離散特征的構(gòu)建方法最大簡(jiǎn)約法 (MP)進(jìn)化簡(jiǎn)約法 (EP)最大似然法 (ML)相容性方法 17兩大類(lèi)構(gòu)建系統(tǒng)樹(shù)的算法基于距離的構(gòu)建方法 (distance注意: 系統(tǒng)樹(shù)的限制有人認(rèn)為生物的系統(tǒng)關(guān)系不一定是樹(shù)狀的系統(tǒng)樹(shù)不一定代表進(jìn)化歷史有很多干擾分析的因素噪音(noisy)水平基因轉(zhuǎn)移(horizontal gene transfer;網(wǎng)狀)雜交,重組等 (網(wǎng)狀

8、)用不同基因或蛋白產(chǎn)生的樹(shù)往往不同已經(jīng)滅絕的物種只能作為葉節(jié)點(diǎn)18注意: 系統(tǒng)樹(shù)的限制有人認(rèn)為生物的系統(tǒng)關(guān)系不一定是樹(shù)狀的18二、多序列比對(duì)19二、多序列比對(duì)19例子多物種核糖體Rplp0蛋白比對(duì)ClustalW生成(顏色表示氨基酸保守性)20例子多物種核糖體Rplp0蛋白比對(duì)ClustalW生成(顏色多序列比對(duì)方法動(dòng)態(tài)規(guī)劃(dynamic programming)慢,耗內(nèi)存改進(jìn): 使用“sum of pairs”目標(biāo)函數(shù)漸進(jìn)法(progressive method;或稱(chēng)分級(jí)法hierarchical,建樹(shù)法tree)迭代法(iterative method)基序法(motif finding

9、;或稱(chēng)輪廓分析法profile analysis)來(lái)自計(jì)算科學(xué)的算法HMM, GA, SA星形比對(duì),樹(shù)形比對(duì)21多序列比對(duì)方法動(dòng)態(tài)規(guī)劃(dynamic programmin動(dòng)態(tài)規(guī)劃法是兩兩比對(duì)所用動(dòng)態(tài)規(guī)劃方法的直接擴(kuò)展步驟用兩兩比對(duì)的方法比對(duì)所有的序列對(duì)建立n維矩陣(n為序列個(gè)數(shù))產(chǎn)生多序列比對(duì)優(yōu)點(diǎn)理論上適用于任意多個(gè)序列保證能得到較好結(jié)果缺點(diǎn)耗費(fèi)大量時(shí)間,內(nèi)存實(shí)際上很少用于多于3個(gè)序列的比對(duì)22動(dòng)態(tài)規(guī)劃法是兩兩比對(duì)所用動(dòng)態(tài)規(guī)劃方法的直接擴(kuò)展22逐對(duì)加和法(sum of pairs, SP)步驟進(jìn)行所有兩兩比對(duì),并給每個(gè)比對(duì)打分將所有的得分相加找到最優(yōu)多序列比對(duì),使得總得分(目標(biāo)函數(shù)objec

10、tive function)最高例子對(duì)于這個(gè)蛋白多序列(3個(gè))比對(duì),求總分已知得分(K,R)=3,間隔罰分為-12KR(-12)+(-12)+3=-2123逐對(duì)加和法(sum of pairs, SP)步驟K(-12Clustal可能是使用最廣的多序列比對(duì)軟件算法用Needleman-Wunsch全局算法做所有兩兩比對(duì)得到距離矩陣,從而產(chǎn)生引導(dǎo)樹(shù) (guide tree; 利用UPGMA,見(jiàn)后; 得到dnd文件)漸進(jìn)式比對(duì) (先處理距離最近的2個(gè)序列,再加次最近的; 得到aln文件)兩個(gè)主要形式ClustalW (命令行)ClustalX (圖形用戶(hù)界面GUI)適用于Windows,Mac O

11、S,Unix/Linux24Clustal可能是使用最廣的多序列比對(duì)軟件24Clustal的輸入輸出文件格式輸出PHYLIPClustalNBRF/PIRGCG/MSFGDENEXUS輸入FASTAClustalNBRF/PIRGCC/MSFGDEEMBL/SwissprotGCG9 RSF25Clustal的輸入輸出文件格式輸出輸入25ClustalW比對(duì)多序列(1) 主頁(yè)http:/www.ebi.ac.uk/clustalw/這里將輸入比對(duì)的多個(gè)序列26ClustalW比對(duì)多序列(1) 主頁(yè)http:/wwClustalW (2) 獲取FASTA格式的序列拷貝這些部分選擇格式拷貝這些部分

12、拷貝這些部分或?qū)⑦@里改為T(mén)ext,更易拷貝27ClustalW (2) 獲取FASTA格式的序列拷貝這ClustalW (3) 將多個(gè)序列輸入將多個(gè)序列粘貼到此點(diǎn)此比對(duì)28ClustalW (3) 將多個(gè)序列輸入將多個(gè)序列粘貼到ClustalW (4) 比對(duì)結(jié)果(1) 基本信息引導(dǎo)樹(shù)文件多序列比對(duì)文件29ClustalW (4) 比對(duì)結(jié)果(1) 基本信息引導(dǎo)樹(shù)ClustalW (5) 比對(duì)結(jié)果(2) 比對(duì)圖30ClustalW (5) 比對(duì)結(jié)果(2) 比對(duì)圖30ClustalW (6) 比對(duì)結(jié)果(3)引導(dǎo)樹(shù)31ClustalW (6) 比對(duì)結(jié)果(3)引導(dǎo)樹(shù)31MSA數(shù)據(jù)庫(kù)Pfam (profi

13、le HMM library)SMARTCDD (HMM; NCBI DART; =Pfam+SMART)BLOCKS (HMM)PRINTSPROSITEPopSetDOMO (Gapped MSA)PRODOM (PSI-BLAST)MetaFAMINTERPROiProClass32MSA數(shù)據(jù)庫(kù)Pfam (profile HMM librarMSA軟件(維基的列表)NAMEDescriptionSequence TypeAlignment TypeLinkAuthorYearMSADynamic programmingBothLocal or GlobaldownloadD.J. Lip

14、man et al.1989 (modified 1995)MultAlinDynamic programming/clusteringBothLocal or GlobalserverF. Corpet1988PSAlignAlignment preserving non-heuristicBothLocal or GlobaldownloadS.H. Sze, Y. Lu, Q. Yang.2006ClustalWProgressive alignmentBothLocal or GlobalEBI PBIL EMBNet GenomeNetThompson et al.1994Kalig

15、nProgressive alignmentBothGlobalserverT. Lassmann2005T-CoffeeMore sensitive progressive alignmentBothLocal or GlobalserverC. Notredame et al.2000AMAPSequence annealingBothGlobalserverA. Schwartz and L. Pachter2006MAVIDProgressive alignmentBothGlobalserverN. Bray and L. Pachter2004Multi-LAGANProgress

16、ive dynamic programming alignmentBothGlobalserverM. Brudno et al.2003MUSCLEProgressive/iterative alignmentBothLocal or GlobalserverR. Edgar2004MAFFTProgressive/iterative alignmentBothLocal or GlobalGenomeNet MAFFTK. Katoh et al.2005GeneiousProgressive/Iterative alignment; ClustalW pluginBothLocal or

17、 GlobaldownloadA.J. Drummond et al.2005 / 2006CHAOS/DIALIGNIterative alignmentBothLocal (preferred)serverM. Brudno and B. Morgenstern2003PRRN/PRRPIterative alignment (especially refinement)ProteinLocal or GlobalPRRP PRRNY. Totoki (based on O. Gotoh)1991 and laterPOAPartial order/hidden Markov modelP

18、roteinLocal or GlobaldownloadC. Lee2002SAMHidden Markov modelProteinLocal or GlobalserverA. Krogh et al.1994 (most recent 2002)ProbConsProbabilistic/consistencyProteinLocal or GlobalserverC. Do et al.2005SAGASequence alignment by genetic algorithmProteinLocal or GlobaldownloadC. Notredame et al.1996

19、 (new version 1998)EdNimbusSeeded filtrationNucleotidesLocalserverP. Peterlongo et al.2006RevTransCombines DNA and Protein alignment, by back translating the protein alignment to DNA.DNA/Protein (special)Local or GlobalserverWernersson and Pedersen2003 (newest version 2005)33MSA軟件(維基的列表)NAMEDescript

20、ionSeq其他MSA軟件Opal (Bioinformatics 23(13);2007/7/1;免費(fèi))aligning alignmentsMurlet (Bioinformatics 23(13);2007/7/1;開(kāi)源)for RNASQUINT (Bioinformatics 23(12);2007/6/1)Probalign (Bioinformatics 22(22)PileUp (全局漸進(jìn))PIMA (局部漸進(jìn))BaliBase (比較MSA算法)AMASCINEMAHMMTMatch-BoxMusca34其他MSA軟件Opal (Bioinformatics 23MSA算法比

21、較全局(global)算法往往優(yōu)于局部(local)算法迭代(iterative)算法(如PRRP, SAGA)往往優(yōu)于漸進(jìn)式(progressive)算法(如Clustal)(a recent review) Recent Evolutions of Multiple Sequence Alignment Algorithms. Cdric Notredame. PLoS Computational Biology. 3(8). 200735MSA算法比較全局(global)算法往往優(yōu)于局部(loca三、構(gòu)建系統(tǒng)樹(shù)36三、構(gòu)建系統(tǒng)樹(shù)36非加權(quán)分組平均法UPGMA (Unweighted Pa

22、ir Group Method with Arithmetic mean)算法(基于距離)使每個(gè)物種自成一類(lèi)執(zhí)行下列循環(huán)尋找最小距離的兩個(gè)類(lèi),建立一個(gè)新的聚類(lèi)連接這兩個(gè)類(lèi)形成新節(jié)點(diǎn)在距離矩陣中刪除這兩個(gè)類(lèi)相應(yīng)的行和列,為新類(lèi)加入新的行和列(非加權(quán))重復(fù)循環(huán),直到僅剩一個(gè)類(lèi)思想跟連鎖聚類(lèi)方法、漸進(jìn)法類(lèi)似是一種改進(jìn)了的鄰近歸并法37非加權(quán)分組平均法UPGMA (Unweighted Pair最大簡(jiǎn)約法(1)Maximum Parsimony (MP)思想：最好的樹(shù)應(yīng)該用最少的進(jìn)化上的變化來(lái)解釋數(shù)據(jù)基于離散特征的方法枝長(zhǎng)來(lái)自該枝進(jìn)化上變化的數(shù)目有時(shí)會(huì)存在多棵最大簡(jiǎn)約樹(shù)38最大簡(jiǎn)約法(1)Maximu

23、m Parsimony (MP)最大簡(jiǎn)約法(2)計(jì)算量太大 考慮部分位點(diǎn)信息位點(diǎn) (informative sites)若在某個(gè)位點(diǎn)上至少有兩個(gè)等位基因，而每個(gè)等位基因至少存在于兩條序列，該位點(diǎn)稱(chēng)為信息位點(diǎn) 序列 1 2 3 4 5 6 7 8 9 1 A A G A G T G C A 2 A G C C G T G C G 3 A G A T A T C C A 4 A G A G A T C C G * * *位點(diǎn)39最大簡(jiǎn)約法(2)計(jì)算量太大 考慮部分位點(diǎn) 序列 最大簡(jiǎn)約法(3) “長(zhǎng)枝吸引”Long Branch Attraction (LBA)若兩個(gè)物種的變異率較大，導(dǎo)致：長(zhǎng)枝可能

24、存在共同變異結(jié)果：若這些變異多于那些能區(qū)別它們共同祖先的變異，MP將產(chǎn)生錯(cuò)誤的樹(shù)真實(shí)樹(shù)MP重建的樹(shù)真實(shí)樹(shù)MP重建的樹(shù)40最大簡(jiǎn)約法(3) “長(zhǎng)枝吸引”Long Branch A評(píng)價(jià)結(jié)果問(wèn)題整棵樹(shù)和它的組成部分(分支)的置信度是多少?這樣得到正確的樹(shù)的可能性比隨機(jī)選出一棵是正確的樹(shù)的可能性大多少?方法自舉檢驗(yàn) (bootstrap)參數(shù)檢驗(yàn)41評(píng)價(jià)結(jié)果問(wèn)題41全基因組的系統(tǒng)發(fā)生分析基于多棵系統(tǒng)發(fā)生樹(shù)的方法基于基因內(nèi)容的方法基于蛋白質(zhì)折疊結(jié)構(gòu)的方法基于基因次序的方法基于連接的直向同源蛋白的方法基于代謝途徑(pathway)的方法42全基因組的系統(tǒng)發(fā)生分析基于多棵系統(tǒng)發(fā)生樹(shù)的方法42四、系統(tǒng)發(fā)生軟件

25、43四、系統(tǒng)發(fā)生軟件43Joe Felsensteins list of Phylogeny Programs (最全的列表)/phylip/software.html44Joe Felsensteins list of PhylJFs list (簡(jiǎn)介;包含309種軟件)三種分類(lèi)依據(jù)軟件所使用的方法軟件使用的系統(tǒng)軟件所分析的數(shù)據(jù)其他列表最近加入的軟件最近更新的軟件以前列出但已經(jīng)不再發(fā)行的軟件等待加入的軟件不被列出的軟件其他系統(tǒng)發(fā)生軟件的列表45JFs list (簡(jiǎn)介;包含309種軟件)三種分類(lèi)依據(jù)4JFs list (所有軟件按方法分類(lèi))General-purpose packages 一

26、般目的 11Parsimony programs 簡(jiǎn)約法 37Distance matrix methods 距離矩陣 65Computation of distances 計(jì)算距離 58Maximum likelihood and Bayesian methods 最大似然、貝葉斯 77Quartets methods 四重奏 11Artificial-intelligence and genetic algorithms methods 人工智能、遺傳算法 4Invariants (or Evolutionary Parsimony) methods 不變量/進(jìn)化簡(jiǎn)約 4Interacti

27、ve tree manipulation 24Looking for hybridization or recombination events 19Bootstrapping and other measures of support 63Compatibility analysis 9Consensus trees, subtrees, supertrees, distances between trees 22Tree-based alignment 20Gene duplication and genomic analysis 6Biogeographic analysis and h

28、ost-parasite comparison 8Comparative method analysis 26Simulation of trees or data 21Examination of shapes of trees 13Clocks, dating and stratigraphy 32Model Selection 12Description or prediction of data from trees 9Tree plotting/drawing 38Sequence management/job submission 20Teaching about phylogen

29、ies 4(方法后數(shù)字為該分類(lèi)的軟件個(gè)數(shù))46JFs list (所有軟件按方法分類(lèi))General-pJFs list (一般目的軟件)PHYLIP PAUP* MEGA Phylo_win ARB DAMBE PAL Bionumerics Mesquite PaupUp BIRCH 47JFs list (一般目的軟件)PHYLIP 47JFs list (軟件按數(shù)據(jù)分類(lèi))Microsatellite dataRSTCALC POPTREE Microsat Populations MSA YCDMA Network IM 48JFs list (軟件按數(shù)據(jù)分類(lèi))MicrosatellJ

30、Fs list (按數(shù)據(jù)分類(lèi))RAPDs, RFLPs, or AFLPstfpga RAPDistance Fingerprinting II Informatix Software GelCompar II Bionumerics Winboot REAP RESTSITE MVSP DENDRON Phyltools Network BIRCH 49JFs list (按數(shù)據(jù)分類(lèi))RAPDs, RFLPs,JFs list (按數(shù)據(jù)分類(lèi))Continuous quantitative charactersPHYLIP Mesquite ANCML COMPARE CMAP PDAP AC

31、AP Phylogenetic Independence APE CAIC TreeScan PHYLOGR IDC CoMET OUCH Brownie BayesTraits TNT PHYSIG 50JFs list (按數(shù)據(jù)分類(lèi))Continuous quJFs list (按數(shù)據(jù)分類(lèi))Gene frequencies (aside from microsatellite loci)PHYLIP DAMBE DISPAN GDA POPGENE YCDMA FSTAT Arlequin DnaSP APE DIVAGE GeneStrut POPTREE Genepop SPAGeDi

32、 51JFs list (按數(shù)據(jù)分類(lèi))Gene frequenc免費(fèi)開(kāi)源軟件/ (Digital Taxonomy)還包括systematics(分類(lèi)學(xué)/系統(tǒng)學(xué))、morphometrics(形態(tài)測(cè)定學(xué))方面的軟件52免費(fèi)開(kāi)源軟件http:/digitaltaxonomy.i維基(Wiki)的列表NAMEDescriptionMethodsLinkAuthorPHYLIPPhylogenetic inference packageMaximum parsimony, distance matrix, maximum likelihooddownloadJ. FelsensteinPAUPPhy

33、logenetic analysis using parsimonyMaximum parsimony, distance matrix, maximum likelihoodpurchaseD. SwoffordPAMLPhylogenetic analysis by maximum likelihoodMaximum likelihooddownloadZ. YangClustalWProgressive multiple sequence alignmentDistance matrix/nearest neighborEBI PBIL EMBNet GenomeNetThompson et al.QuickTreeTree construction optimized for efficiencyNeighbo