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

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

2、生分類學(xué))是系統(tǒng)學(xué)的一個(gè)分支根據(jù)進(jìn)化相關(guān)度對(duì)生物群體分類phylogeny (=phylogenesis系統(tǒng)發(fā)生)生物群體的產(chǎn)生和進(jìn)化分子系統(tǒng)學(xué)(molecular phylogenetics)將核酸,氨基酸序列作為進(jìn)化特征,6,系統(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)為有共同祖

3、先,,葉,節(jié)點(diǎn),關(guān)系,時(shí)間,7,有根樹(shù)和無(wú)根樹(shù),有根樹(shù)(rooted tree)有共同祖先無(wú)根樹(shù)(unrooted tree)樹(shù)空間(tree space)從已知序列可以產(chǎn)生許多系統(tǒng)樹(shù)來(lái)自幾何,8,無(wú)根樹(shù)和有根樹(shù)的關(guān)系(1),從一棵有根樹(shù)總可以產(chǎn)生一棵無(wú)根樹(shù)而從無(wú)根樹(shù)產(chǎn)生有根樹(shù)需要額外的數(shù)據(jù),9,無(wú)根樹(shù)和有根樹(shù)的關(guān)系(2),一棵無(wú)根樹(shù)可以產(chǎn)生多棵有根樹(shù),10,Willi Hennig (1913-1976),德國(guó)生物學(xué)家,被

4、認(rèn)為是系統(tǒng)發(fā)生學(xué)和分類學(xué)(cladistics; 也叫cladogram)的奠基人據(jù)已知資料來(lái)看,他的觀點(diǎn)并不是最早被闡述屬達(dá)爾文學(xué)派;類似的觀點(diǎn)另一學(xué)派的Lamarck和Rosa也有闡述可以認(rèn)為是系統(tǒng)發(fā)生學(xué)的集大成者,11,歷史上的系統(tǒng)樹(shù),?？藸?Ernst Haeckel)首次制成了當(dāng)時(shí)所有已知生物的系統(tǒng)樹(shù)(1834-1919)著名的德國(guó)生物學(xué)家,哲學(xué)家,醫(yī)生,教授,藝術(shù)家創(chuàng)建了重演論(recapitulation the

5、ory)命名了許多生物學(xué)術(shù)語(yǔ)(如:門(mén),系統(tǒng)發(fā)生,生態(tài)學(xué),原生生物)和幾千物種出版了著名的Kunstformen der Natur (Artforms of Nature),12,可能是最早的系統(tǒng)樹(shù),C. Darwin,1837,13,特征選取的變遷,經(jīng)典系統(tǒng)發(fā)生學(xué)主要是比較大的物理或表型特征如生物體的大小,顏色,牙齒個(gè)數(shù),行為特征缺點(diǎn): 不易量化(連續(xù)), 難以選取合適特征現(xiàn)代系統(tǒng)發(fā)生學(xué)分子水平: 核酸或氨基酸序列優(yōu)點(diǎn)

6、: 易量化(離散),易獲取,適于自動(dòng)化,更本質(zhì)例子: (現(xiàn)代人起源) 通過(guò)對(duì)線粒體DNA的研究,認(rèn)為所有現(xiàn)代人都是一個(gè)非洲女性的后代(“夏娃”),14,系統(tǒng)發(fā)生學(xué)研究方法,目的在樹(shù)空間中尋找正確的系統(tǒng)樹(shù)分析步驟多(重)序列比對(duì)(multiple sequence alignment, MSA)構(gòu)建系統(tǒng)樹(shù)評(píng)價(jià)結(jié)果,15,三種構(gòu)建系統(tǒng)樹(shù)中使用的搜索算法,窮盡法搜索整個(gè)空間(所有可能的樹(shù)),然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹(shù)分支

7、約束方法根據(jù)一定的約束條件將搜索空間限制在一定范圍內(nèi)啟發(fā)式或經(jīng)驗(yàn)性方法(heuristic)根據(jù)目前的搜索情況指導(dǎo)下一步的搜索方向根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間,16,兩類數(shù)據(jù): 距離和離散特征,距離描述序列之間的差別 (遺傳距離)一般用距離矩陣(distance matrix)表示距離往往由序列比對(duì)產(chǎn)生(如錯(cuò)配的比例)離散特征二態(tài)特征 (如: DNA序列上的某個(gè)位點(diǎn)是否剪切位點(diǎn))多態(tài)特征 (如: 某一位

8、點(diǎn)可能的堿基有A,T,G,C),17,兩大類構(gòu)建系統(tǒng)樹(shù)的算法,基于距離的構(gòu)建方法 (distance-matrix methods)鄰近歸并法 (或稱鄰接法,neighbor-joining)非加權(quán)組平均法 (UPGMA)Fitch-Margoliash法 最小進(jìn)化方法基于離散特征的構(gòu)建方法最大簡(jiǎn)約法 (MP)進(jìn)化簡(jiǎn)約法 (EP)最大似然法 (ML)相容性方法,18,注意: 系統(tǒng)樹(shù)的限制,有人認(rèn)為生物的系統(tǒng)關(guān)系不一定是

9、樹(shù)狀的系統(tǒng)樹(shù)不一定代表進(jìn)化歷史有很多干擾分析的因素噪音(noisy)水平基因轉(zhuǎn)移(horizontal gene transfer;網(wǎng)狀)雜交,重組等 (網(wǎng)狀)用不同基因或蛋白產(chǎn)生的樹(shù)往往不同已經(jīng)滅絕的物種只能作為葉節(jié)點(diǎn),19,二、多序列比對(duì),20,例子,多物種核糖體Rplp0蛋白比對(duì),ClustalW生成(顏色表示氨基酸保守性),21,多序列比對(duì)方法,動(dòng)態(tài)規(guī)劃(dynamic programming)慢,耗內(nèi)存改進(jìn):

10、 使用“sum of pairs”目標(biāo)函數(shù)漸進(jìn)法(progressive method;或稱分級(jí)法hierarchical,建樹(shù)法tree)迭代法(iterative method)基序法(motif finding;或稱輪廓分析法profile analysis)來(lái)自計(jì)算科學(xué)的算法HMM, GA, SA星形比對(duì),樹(shù)形比對(duì),22,動(dòng)態(tài)規(guī)劃法,是兩兩比對(duì)所用動(dòng)態(tài)規(guī)劃方法的直接擴(kuò)展步驟用兩兩比對(duì)的方法比對(duì)所有的序列對(duì)建立n

11、維矩陣(n為序列個(gè)數(shù))產(chǎn)生多序列比對(duì)優(yōu)點(diǎn)理論上適用于任意多個(gè)序列保證能得到較好結(jié)果缺點(diǎn)耗費(fèi)大量時(shí)間,內(nèi)存實(shí)際上很少用于多于3個(gè)序列的比對(duì),23,逐對(duì)加和法(sum of pairs, SP),步驟進(jìn)行所有兩兩比對(duì),并給每個(gè)比對(duì)打分將所有的得分相加找到最優(yōu)多序列比對(duì),使得總得分(目標(biāo)函數(shù)objective function)最高例子對(duì)于這個(gè)蛋白多序列(3個(gè))比對(duì),求總分已知得分(K,R)=3,間隔罰分為-12,K

12、–R,(-12)+(-12)+3=-21,24,Clustal,可能是使用最廣的多序列比對(duì)軟件算法用Needleman-Wunsch全局算法做所有兩兩比對(duì)得到距離矩陣,從而產(chǎn)生引導(dǎo)樹(shù) (guide tree; 利用UPGMA,見(jiàn)后; 得到dnd文件)漸進(jìn)式比對(duì) (先處理距離最近的2個(gè)序列,再加次最近的…; 得到aln文件)兩個(gè)主要形式ClustalW (命令行)ClustalX (圖形用戶界面GUI)適用于Windo

13、ws,Mac OS,Unix/Linux,25,Clustal的輸入輸出文件格式,輸出PHYLIPClustalNBRF/PIRGCG/MSFGDENEXUS,輸入FASTAClustalNBRF/PIRGCC/MSFGDEEMBL/SwissprotGCG9 RSF,26,ClustalW比對(duì)多序列(1) – 主頁(yè),http://www.ebi.ac.uk/clustalw/,這里將輸入比對(duì)的多個(gè)序列,,27

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

15、)引導(dǎo)樹(shù),32,MSA數(shù)據(jù)庫(kù),Pfam (profile HMM library)SMARTCDD (HMM; NCBI DART; =Pfam+SMART)BLOCKS (HMM)PRINTSPROSITEPopSetDOMO (Gapped MSA)PRODOM (PSI-BLAST)MetaFAMINTERPROiProClass,33,MSA軟件(維基的列表),34,其他MSA軟件,Opal (Bioinf

16、ormatics 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算法),A

17、MASCINEMAHMMTMatch-BoxMusca,35,MSA算法比較,全局(global)算法往往優(yōu)于局部(local)算法迭代(iterative)算法(如PRRP, SAGA)往往優(yōu)于漸進(jìn)式(progressive)算法(如Clustal)(a recent review) Recent Evolutions of Multiple Sequence Alignment Algorithms. Céd

18、ric Notredame. PLoS Computational Biology. 3(8). 2007,36,三、構(gòu)建系統(tǒng)樹(shù),37,非加權(quán)分組平均法,UPGMA (Unweighted Pair Group Method with Arithmetic mean)算法(基于距離)使每個(gè)物種自成一類執(zhí)行下列循環(huán)尋找最小距離的兩個(gè)類,建立一個(gè)新的聚類連接這兩個(gè)類形成新節(jié)點(diǎn)在距離矩陣中刪除這兩個(gè)類相應(yīng)的行和列,為新類加入新的行

19、和列(非加權(quán))重復(fù)循環(huán),直到僅剩一個(gè)類思想跟連鎖聚類方法、漸進(jìn)法類似是一種改進(jìn)了的鄰近歸并法,38,最大簡(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ù),39,最大簡(jiǎn)約法(2),計(jì)算量太大 ? 考慮部分位點(diǎn)信息位點(diǎn) (informative sites)若在某個(gè)位點(diǎn)上至少有兩個(gè)等位基因，而每個(gè)

20、等位基因至少存在于兩條序列，該位點(diǎn)稱為信息位點(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

21、 * * *,位點(diǎn),40,最大簡(jiǎn)約法(3) – “長(zhǎng)枝吸引”,Long Branch Attraction (LBA)若兩個(gè)物種的變異率較大，導(dǎo)致：長(zhǎng)枝可能存在共同變異結(jié)果：若這些變異多于那些能區(qū)別它們共同祖先的變異，MP將產(chǎn)生錯(cuò)誤的樹(shù),,,√,×,41,評(píng)價(jià)結(jié)果,問(wèn)題整棵樹(shù)和它的組成部分(分支)的置信度是多少?這樣得到正確的樹(shù)的可能性比隨機(jī)選出一棵是正確的樹(shù)的可能性大多少?方法自舉檢驗(yàn)

22、(bootstrap)參數(shù)檢驗(yàn),42,全基因組的系統(tǒng)發(fā)生分析,基于多棵系統(tǒng)發(fā)生樹(shù)的方法基于基因內(nèi)容的方法基于蛋白質(zhì)折疊結(jié)構(gòu)的方法基于基因次序的方法基于連接的直向同源蛋白的方法基于代謝途徑(pathway)的方法,43,四、系統(tǒng)發(fā)生軟件,44,Joe Felsenstein's list of Phylogeny Programs (最全的列表),http://evolution.gs.washington.edu/p

23、hylip/software.html,45,JF's list (簡(jiǎn)介;包含309種軟件),三種分類依據(jù)軟件所使用的方法軟件使用的系統(tǒng)軟件所分析的數(shù)據(jù)其他列表最近加入的軟件最近更新的軟件以前列出但已經(jīng)不再發(fā)行的軟件等待加入的軟件不被列出的軟件其他系統(tǒng)發(fā)生軟件的列表,46,JF's list (所有軟件按方法分類),General-purpose packages 一般目的 11Parsimony

24、programs 簡(jiǎn)約法 37Distance matrix methods 距離矩陣 65Computation of distances 計(jì)算距離 58Maximum likelihood and Bayesian methods 最大似然、貝葉斯 77Quartets methods 四重奏 11Artificial-intelligence and genetic algorithms methods 人工智能、遺傳算

25、法 4Invariants (or Evolutionary Parsimony) methods 不變量/進(jìn)化簡(jiǎn)約 4Interactive tree manipulation 24Looking for hybridization or recombination events 19Bootstrapping and other measures of support 63Compatibility analysis 9

26、Consensus trees, subtrees, supertrees, distances between trees 22Tree-based alignment 20Gene duplication and genomic analysis 6Biogeographic analysis and host-parasite comparison 8Comparative method analysis 26Simul

27、ation 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

28、 20Teaching about phylogenies 4(方法后數(shù)字為該分類的軟件個(gè)數(shù)),47,JF's list (一般目的軟件),PHYLIP PAUP* MEGA Phylo_win ARB DAMBE PAL Bionumerics Mesquite PaupUp BIRCH,48,JF's list (軟件按數(shù)據(jù)分類),Microsatellite dataRSTCALC PO

29、PTREE Microsat Populations MSA YCDMA Network IM,49,JF's list (按數(shù)據(jù)分類),RAPDs, RFLPs, or AFLPstfpga RAPDistance Fingerprinting II Informatix Software GelCompar II Bionumerics Winboot REAP RESTSITE MVSP D

30、ENDRON Phyltools Network BIRCH,50,JF's list (按數(shù)據(jù)分類),Continuous quantitative charactersPHYLIP Mesquite ANCML COMPARE CMAP PDAP ACAP Phylogenetic Independence APE CAIC TreeScan PHYLOGR IDC CoMET OUCH

31、Brownie BayesTraits TNT PHYSIG,51,JF's list (按數(shù)據(jù)分類),Gene frequencies (aside from microsatellite loci)PHYLIP DAMBE DISPAN GDA POPGENE YCDMA FSTAT Arlequin DnaSP APE DIVAGE GeneStrut POPTREE Genepop

32、SPAGeDi,52,免費(fèi)開(kāi)源軟件,http://digitaltaxonomy.infobio.net/ (Digital Taxonomy)還包括systematics(分類學(xué)/系統(tǒng)學(xué))、morphometrics(形態(tài)測(cè)定學(xué))方面的軟件,53,維基(Wiki)的列表,54,雜項(xiàng),PhyloCode (不是軟件;是種系發(fā)生命名法的一些規(guī)則)TOPD/FMTS (Bioinformatics 23(12); 2007-6-1),5

33、5,PHYLIP,種系發(fā)生軟件包Joseph Felsenstein,華盛頓大學(xué)下載(Windows版)http://evolution.genetics.washington.edu/phylip/getme.html,56,用PHYLIP繪制樹(shù)(1),安裝目錄里有一個(gè)“exe”目錄將該目錄中某一個(gè)font文件改名為fontfile將ClustalW中保存的引導(dǎo)樹(shù)文件移入該目錄并改名為intree運(yùn)行程序drawgram.