雙序列比對(duì)的方法課件

1、雙序列比對(duì)郭志云Email:1課程主線序列比對(duì)基本概念空位罰分相似性與同源性雙序列比對(duì)方法點(diǎn)陣序列比較(Dot Matrix Sequence Comparison)動(dòng)態(tài)規(guī)劃算法(Dynamic Programming Algorithm)記分矩陣2什么是序列比對(duì)？序列比對(duì)(Sequence Alignment)是通過(guò)在序列中搜索一系列單個(gè)性狀或性狀模式來(lái)比較2個(gè)（雙序列比對(duì)）或更多（多重序列比對(duì)）序列的方法按比對(duì)序列條數(shù)分類雙序列比對(duì)：兩條序列的比對(duì)多序列比對(duì)：三條或以上序列的比對(duì)3我們?yōu)槭裁搓P(guān)注序列比對(duì)？相似的序列可能具有相似的功能與結(jié)構(gòu)發(fā)現(xiàn)一個(gè)基因或蛋白哪些

2、區(qū)域容易發(fā)生突變，哪些位點(diǎn)突變后對(duì)功能沒有影響 發(fā)現(xiàn)生物進(jìn)化方面的信息4序列比對(duì)兩種類型全局序列比對(duì)定義：在全局范圍內(nèi)對(duì)兩條序列進(jìn)行比對(duì)打分的方法適合于非常相似且長(zhǎng)度近似相等的序列局部序列比對(duì)定義：一種尋找匹配子序列的序列比對(duì)方法 適合于一些片段相似而另一些片段相異的序列5序列比對(duì)兩種類型6空位罰分(Gap Penalties)空位為了獲得兩個(gè)序列最佳比對(duì)，必須使用空位和空位罰分空位罰分分類：空位開放罰分(Gap opening penalty)空位擴(kuò)展罰分(Gap extension penalty)最優(yōu)的序列比對(duì)通常具有以下兩下特征：盡可能多的匹配盡可能少的空位插入任意多的空位會(huì)產(chǎn)生較高的

3、分?jǐn)?shù)，但找到的并不一定是真正相似序列71 GTGATAGACAC | 1 GTGCATAGACAC空位罰分允許空位但不罰分不允許有空位 match = 5mismatch = -41 GTG-ATAGACAC | |1 GTGCATAGACAC1 GTG-ATAGACAC | |1 GTGC-ATAGACAC?Score: -21Score: 558空位罰分公式 A T G T T A T A CT A T G T G C G T A T A Score=4參數(shù):匹配= 1非匹配= 0g= 3r = 0.1x = 3score：8 - 3.2 = 4.8Wx=g+r(x-1)Wx:空位總記分g

4、:空位開放罰分r:空位擴(kuò)展罰分x:空位長(zhǎng)度T A T G T G C G T A T A insertion / deletionA T G T - - - T A T A CWx= -3 - (3 -1) 0.1 = -3.29雙序列比對(duì)方法點(diǎn)陣序列比較 (Dot Matrix Sequence Comparison)動(dòng)態(tài)規(guī)劃算法 (Dynamic Programming Algorithm)詞或K串方法 (Word or K-tuple Methods)10點(diǎn)陣序列比較點(diǎn)陣(Dot Matrix)分析是一種簡(jiǎn)單的圖形顯示序列相似性的方法沿X軸上序列1中的每一個(gè)單元（核苷酸或氨基酸）與沿Y軸

5、的第二個(gè)序列中的每一個(gè)單元進(jìn)行比較，相同的區(qū)域在點(diǎn)陣圖中顯示為由點(diǎn)組成的對(duì)角線，對(duì)角線之外零散的點(diǎn)為背景噪音11IONIZATIONIONIZATION12IONIZATNOIIONIZATNOI13點(diǎn)陣分析的應(yīng)用自身比對(duì)尋找序列中的正向或反向重復(fù)序列蛋白質(zhì)的重復(fù)結(jié)構(gòu)域(domain)相同殘基重復(fù)出現(xiàn)的低復(fù)雜區(qū)(Low Complexity)RNA二級(jí)結(jié)構(gòu)中的互補(bǔ)區(qū)域等對(duì)兩條序列的相似性作整體的估計(jì)14點(diǎn)陣分析中的插入或刪除TACTGTCAT T A C T G T T C A TSequence 1Sequence 2T A C T G - T C A T| | | | | | | | |T

6、 A C T G T T C A T插入空位15點(diǎn)陣分析的應(yīng)用人類低脂受體(human low-density lipoprotein receptor)自身比對(duì)發(fā)現(xiàn)正向重復(fù)序列具有連續(xù)相似區(qū)域的兩條DNA序列的簡(jiǎn)單點(diǎn)陣圖正向重復(fù)16點(diǎn)陣分析實(shí)例編碼噬菌體c（水平軸）和噬菌體P22 c2（垂直軸）的氨基酸序列間的點(diǎn)陣分析相同的點(diǎn)打印全部打印，很難找到有用的信息17使用滑動(dòng)窗口技術(shù)降低噪聲T A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C

7、G G T A T G A C A G T A T CC T A T G A C A TACGGTATGWindow=3 Word Size = 318ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 019ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 020

8、ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 021G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCGWindow size = 5Stringency = 3Match = 1 Mismatch = 022G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG23G C G A T G C A

9、 T T G A G T A T C A T AATACTACAAGACACGTACCG24使用滑動(dòng)窗口技術(shù)降低噪聲（a）對(duì)人類（Homo sapiens）與黑猩猩（Pongo pygmaeus）的球蛋白基因序列進(jìn)行比較的完整點(diǎn)陣圖（b）利用滑動(dòng)窗口對(duì)以上的兩種球蛋白基因序列進(jìn)行比較的點(diǎn)陣圖，其中窗口大小為10個(gè)核苷酸， 相似度閾值為8，即10個(gè)核苷酸中有8個(gè)相同時(shí)就打一個(gè)點(diǎn)ab25點(diǎn)陣分析的優(yōu)缺點(diǎn)優(yōu)點(diǎn)直觀性，整體性點(diǎn)陣分析不依賴空位(gap)參數(shù)，可尋找兩序列間所有可能的殘基匹配不依賴任何先決條件，是一種可用于初步分析的理想工具點(diǎn)陣分析允許隨時(shí)動(dòng)態(tài)地改變最高和最低界限值，可以用來(lái)摸索區(qū)分信號(hào)

10、和背景標(biāo)準(zhǔn)的嚴(yán)格程度26點(diǎn)陣分析的優(yōu)缺點(diǎn)缺點(diǎn)不能很好地兼容打分矩陣滑動(dòng)窗口和預(yù)值的選擇過(guò)于經(jīng)驗(yàn)化信噪比低 不適合進(jìn)行高通量的數(shù)據(jù)分析27點(diǎn)陣分析程序DNA Strider (Macintosh)cellbiol/soft.htm Dotter (Unix/Linux, X-Windows)COMPARE, DOTPLOT (GCG軟件)PLALIGN (FASTA)Dotletisrec.isb-sib.ch/java/dotlet/Dotlet.html2829動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法(Dynamic Programming Algorithm)是一種計(jì)算方法，它的主要思路是把一個(gè)問(wèn)題分成若

11、干個(gè)小問(wèn)題來(lái)解決在生物學(xué)中應(yīng)用的兩種動(dòng)態(tài)規(guī)劃算法：Needleman-Wunsch算法（全局比對(duì)）和Smith-Waterman算法（局部比對(duì)）30序列比對(duì)中某一位點(diǎn)匹配的三種可能性Eg. 匹配=1,非匹配=0, 空位罰分=-1Sequence1: CACGASequence2: CGA第一個(gè)位點(diǎn)得分剩余序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGA31動(dòng)態(tài)規(guī)劃算法的正式表述Si,j這個(gè)位置的分?jǐn)?shù)為圖中箭頭所示三個(gè)方向值中最大的一個(gè)i -xi -1j -1i -yji Si - x,j - wx Si 1, j- 1 + s(ai , bj)Si, j - y - wy S

12、i, j 32動(dòng)態(tài)規(guī)劃算法的數(shù)學(xué)形式Sij=maxSi-1,j-1,+s(aibj),maxx1 (Si-x,j-wx),maxy 1 (Si,j-y-wy)Sij=maxSi-1,j-1,+s(aibj),maxx1 (Si-1,j-wx),maxy 1 (Si,j-1-wy)公式一的簡(jiǎn)化公式一公式二說(shuō)明：Sij是序列a在位置i和序列b在位置j的分值， s(aibj)是位置i 和j上比對(duì)分值，wx是在序列a 中長(zhǎng)度為x的間隔罰分，wy是序列b中長(zhǎng)度為y的間隔罰分33動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCGACTAG匹配3錯(cuò)配-1空位-234ACTTCG0ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配3錯(cuò)配-1空位-23

13、5ACTTCG0-2ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配3錯(cuò)配-1空位-236ACTTCG0-2-4-6-8-10-12ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配3錯(cuò)配-1空位-237ACTTCG0-2-4-6-8-10-12A-2CTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配3錯(cuò)配-1空位-238ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10動(dòng)態(tài)規(guī)劃算法實(shí)例?S(2,2)-2+(-2)-2+(-2)0+3匹配3錯(cuò)配-1空位-239ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10動(dòng)態(tài)規(guī)劃算法實(shí)例?S(2,3)-4+(-2) 3+(-2)-2+(-1)匹配3錯(cuò)配-1空位-24

14、0動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3錯(cuò)配-1空位-241動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-14?A-8-3 2G-10-50S(4,4) 4+(-2) 4+(-2) 6+3匹配3錯(cuò)配-1空位-242動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3錯(cuò)配-1空位-243ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-

15、2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA回 溯44ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA45ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAA46比對(duì)結(jié)果1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一個(gè)是最優(yōu)比對(duì)(optimal alignme

16、nt)呢?記分矩陣47Needleman-Wunsch算法Seq1: MPRCLCQRJNCBASeq2: PBRCKCRNJCJA匹配=1，錯(cuò)配=0，空位罰分=048Needleman-Wunsch算法Seq1: MPRCLCQRJNCBASeq2: PBRCKCRNJCJA求出陰影部分所能達(dá)到的最大值填入當(dāng)前位置，并記下到達(dá)這一位置的路徑49Needleman-Wunsch算法Seq1: MPRCLCQRJNCBASeq2: PBRCKCRNJCJA550Needleman-Wunsch算法 MPRCLCQRJNCBA PBRCKCRNJCJAResult：51 F(i-1,j-1) +

17、s(ai, bj), F(i,j)= max F(i,j-1)-wy, F(i-1,j)-wx.0動(dòng)態(tài)規(guī)劃算法Smith-Waterman 算法Smith-Waterman算法52Smith-Waterman 算法AACCTATAGCT000000000000G000000000100C000110000021G000000000101A011000101000T000001021001A011000203210T000001132212A011000224321匹配=1非匹配=-1空位=-153Smith-Waterman 算法AACCTATAGCT000000000000G00000000

18、0100C000110000021G000000000101A011000101000T000001021001A011000203210T000001132212A011000224321A A C C T A T A G C T- G C G A T A T A - - -匹配=1非匹配=-1空位=-154Genetics Computer Group (GCG) 程序 GAP (Needleman-Wunsch algorithm) and BESTFIT (Smith-Waterman algorithm)最相似的比對(duì)表示為 :, 較相似的表示為 . 無(wú)相關(guān)的表示為空格, carbox

19、y-terminal55記分矩陣與空位罰分DNA計(jì)分矩陣蛋白質(zhì)計(jì)分矩陣廣泛使用的兩種矩陣 PAM BLOSUM空位罰分56記分矩陣(SCORING MATRICES)DNA Scoring MatricesAmino Acid Substitution MatricesPAM (Point Accepted Mutation) BLOSUM (Blocks Substitution Matrix)57DNA計(jì)分矩陣actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA10

20、00G0100C0010T0001匹配: 1錯(cuò)配: 0分值：558轉(zhuǎn)換和顛換CTAG嘧啶嘌呤 表示轉(zhuǎn)換(transition)，表示顛換(transversions)轉(zhuǎn)換比顛換更容易發(fā)生59轉(zhuǎn)換和顛換AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99轉(zhuǎn)換速率是顛換3倍時(shí)的模型60蛋白質(zhì)計(jì)分矩陣PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2記分矩陣T:G= -2 T:T = 5Score= 48 CSTPAGND.C 9S-1 4T-1 1 5P-3-1

21、-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 . CSTPAGND.C 9S-1 4T-1 1 5P-3-1-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 .61PAM( Percent Accepted Mutation)矩陣氨基酸容易被其它生化、物理特性相似的氨基酸替換PAM1(1個(gè)PAM單位）被定義為每100個(gè)殘基出現(xiàn)一個(gè)被接受的點(diǎn)突變(氨基酸的置換不引起蛋白質(zhì)功能上的顯著變化）PAMn是PAM1自乘n次PAM250、PAM120、PAM8

22、0和PAM60矩陣可用于相似性分別為20%、40%、50%和60%的序列比對(duì)62 A R N D C Q E G H I L K M F P S T W Y V B ZA 2 -2 0 0 -2 0 0 1 -1 -1 -2 -1 -1 -3 1 1 1 -6 -3 0 2 1 R -2 6 0 -1 -4 1 -1 -3 2 -2 -3 3 0 -4 0 0 -1 2 -4 -2 1 2 N 0 0 2 2 -4 1 1 0 2 -2 -3 1 -2 -3 0 1 0 -4 -2 -2 4 3 D 0 -1 2 4 -5 2 3 1 1 -2 -4 0 -3 -6 -1 0 0 -7 -4

23、-2 5 4 C -2 -4 -4 -5 12 -5 -5 -3 -3 -2 -6 -5 -5 -4 -3 0 -2 -8 0 -2 -3 -4 Q 0 1 1 2 -5 4 2 -1 3 -2 -2 1 -1 -5 0 -1 -1 -5 -4 -2 3 5 E 0 -1 1 3 -5 2 4 0 1 -2 -3 0 -2 -5 -1 0 0 -7 -4 -2 4 5 G 1 -3 0 1 -3 -1 0 5 -2 -3 -4 -2 -3 -5 0 1 0 -7 -5 -1 2 1 H -1 2 2 1 -3 3 1 -2 6 -2 -2 0 -2 -2 0 -1 -1 -3 0 -2 3 3

24、 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 2 -2 2 1 -2 -1 0 -5 -1 4 -1 -1 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 -3 4 2 -3 -3 -2 -2 -1 2 -2 -1 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 0 -5 -1 0 0 -3 -4 -2 2 2 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 0 -2 -2 -1 -4 -2 2 -1 0 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 -5 -3 -3 0 7 -1 -3

25、 -4 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 1 0 -6 -5 -1 1 1 S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 1 -2 -3 -1 2 1 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 -5 -3 0 2 1 W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 0 -6 -4 -4 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 -2 -2 -3 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 0 0 B 2 1 4 5 -3 3 4 2 3 -1 -