pairwisealignment研究生生物信息學(xué)課件03

1、雙序列比對雙序列比對什么是序列比對？什么是序列比對？ 序列比對序列比對(Sequence Alignment)是通過在序是通過在序列中搜索一系列單個性狀或性狀模式來比較列中搜索一系列單個性狀或性狀模式來比較2個（雙序列比對）或更多（多重序列比對）個（雙序列比對）或更多（多重序列比對）序列的方法序列的方法 序列比對分類序列比對分類 雙序列比對：兩條序列的比對雙序列比對：兩條序列的比對 多序列比對：三條或以上序列的比對多序列比對：三條或以上序列的比對我們?yōu)槭裁搓P(guān)注序列比對我們?yōu)槭裁搓P(guān)注序列比對 相似的序列可能具有相同的功能與結(jié)構(gòu)相似的序列可能具有相同的功能與結(jié)構(gòu) 發(fā)現(xiàn)一個基因或蛋白哪些區(qū)域容易發(fā)生

2、突變，哪些發(fā)現(xiàn)一個基因或蛋白哪些區(qū)域容易發(fā)生突變，哪些位點(diǎn)突變后對功能沒有影響位點(diǎn)突變后對功能沒有影響 發(fā)現(xiàn)生物進(jìn)化方面的信息發(fā)現(xiàn)生物進(jìn)化方面的信息 同源性同源性(Homologous Genes) ：序列來自共同的祖先，：序列來自共同的祖先，或具有共同的進(jìn)化史，相似的序列往往具有同源性或具有共同的進(jìn)化史，相似的序列往往具有同源性(如圖如圖) 相似性相似性(Similarity)：兩序列根據(jù)某種參數(shù)相近，但相似：兩序列根據(jù)某種參數(shù)相近，但相似的序列不一定具有同源性。相似性的序列不一定具有同源性。相似性同源性，兩基因只有同源性，兩基因只有同源與非同源關(guān)系同源與非同源關(guān)系我們?yōu)槭裁搓P(guān)注序列比對（續(xù)

3、）我們?yōu)槭裁搓P(guān)注序列比對（續(xù)） 直系同源直系同源(Orthologs)：具有共同祖先與相似功：具有共同祖先與相似功能的同源基因（無基因復(fù)制事件）能的同源基因（無基因復(fù)制事件） 旁系同源旁系同源(Paralogs)：兩個物種：兩個物種A和和B的同源基因，的同源基因，分別是共同祖先基因組中由復(fù)制事件而產(chǎn)生的不分別是共同祖先基因組中由復(fù)制事件而產(chǎn)生的不同拷貝的后代同拷貝的后代 趨同進(jìn)化趨同進(jìn)化(Convergent evolution):序列中的相似序列中的相似區(qū)域可能不具有共同的祖先，而是通過兩條進(jìn)化區(qū)域可能不具有共同的祖先，而是通過兩條進(jìn)化路徑獨(dú)立獲得相同的功能（路徑獨(dú)立獲得相同的功能（如圖如圖

4、）同源序列與祖先序列關(guān)系同源序列與祖先序列關(guān)系進(jìn)化距離：一個序列變成另一個序列所需的步驟數(shù)。進(jìn)化距離：一個序列變成另一個序列所需的步驟數(shù)。如如A變?yōu)樽優(yōu)锽的進(jìn)化距離為：的進(jìn)化距離為：x+y基因進(jìn)化基因進(jìn)化AB：物種：物種I與物種與物種II中的中的a1是直系同源，是直系同源，a1與與a2為旁系同源為旁系同源C：趨同進(jìn)化，物種：趨同進(jìn)化，物種I與物種與物種II經(jīng)歷不同的進(jìn)化途徑，產(chǎn)生相同的功能經(jīng)歷不同的進(jìn)化途徑，產(chǎn)生相同的功能D：基因轉(zhuǎn)移，稱為水平轉(zhuǎn)移基因：基因轉(zhuǎn)移，稱為水平轉(zhuǎn)移基因序列比對兩種類型序列比對兩種類型 全局序列比對全局序列比對l定義：定義：在全局范圍內(nèi)對兩條序列進(jìn)行比對打分的方法在全

5、局范圍內(nèi)對兩條序列進(jìn)行比對打分的方法l適合于非常相似且長度近似相等的序列適合于非常相似且長度近似相等的序列 局部序列比對局部序列比對l定義：定義：一種尋找匹配子序列的序列比對方法一種尋找匹配子序列的序列比對方法 l適合于一些片段相似而另一些片段相異的序列適合于一些片段相似而另一些片段相異的序列 Global Alignment Local L G P S S K Q T G K G S - S R I W D N | | | | | | | L N - I T K S A G K G A I M R L G D A T G K G | | | A G K G 記分矩陣與空位罰分記分矩陣與空位罰

6、分 DNA 計(jì)分矩陣計(jì)分矩陣 蛋白質(zhì)計(jì)分矩陣蛋白質(zhì)計(jì)分矩陣 廣泛使用的兩種矩陣廣泛使用的兩種矩陣 PAM BLOSUM 空位罰分空位罰分DNA 計(jì)分矩陣計(jì)分矩陣actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配: 1錯配: 0分值：5轉(zhuǎn)換和顛換轉(zhuǎn)換和顛換CTAG嘧啶嘧啶嘌呤嘌呤 表示表示轉(zhuǎn)換轉(zhuǎn)換(transition)， 表示表示顛換顛換(transversions)轉(zhuǎn)換比顛換更容易發(fā)生轉(zhuǎn)換比顛換更容易發(fā)生轉(zhuǎn)換和顛換轉(zhuǎn)換和顛換

7、AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99轉(zhuǎn)換速率是顛換轉(zhuǎn)換速率是顛換3倍時的模型倍時的模型蛋白質(zhì)計(jì)分矩陣蛋白質(zhì)計(jì)分矩陣PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2記分矩陣記分矩陣T:G= -2 T:T = 5Score= 48 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 . CSTPAGND.C 9S-1

8、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 .PAM( Point Accepted Mutation)矩陣矩陣 氨基酸記分系統(tǒng)需要替換的模式來提高靈敏度以檢測弱的相氨基酸記分系統(tǒng)需要替換的模式來提高靈敏度以檢測弱的相似性似性 氨基酸容易被其它生化、物理特性相似的氨基酸替換氨基酸容易被其它生化、物理特性相似的氨基酸替換 PAM矩陣給出了進(jìn)化過程中同源蛋白質(zhì)從一個氨基酸變到另矩陣給出了進(jìn)化過程中同源蛋白質(zhì)從一個氨基酸變到另一個氨基酸的似然率一個氨基酸的似然率(Likelihood) PAM1(

9、1個個PAM單位）被定義為每單位）被定義為每100個殘基出現(xiàn)一個被接個殘基出現(xiàn)一個被接受的點(diǎn)突變受的點(diǎn)突變(氨基酸的置換不引起蛋白質(zhì)功能上的顯著變化）氨基酸的置換不引起蛋白質(zhì)功能上的顯著變化） PAMn是是PAM1自乘自乘n次次 PAM250、PAM120、PAM80和和PAM60矩陣可用于相似性分矩陣可用于相似性分別為別為20%、40%、50%和和60%的序列比對的序列比對 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

10、 -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 -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

11、 -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 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

12、 -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 -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 -

13、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 -2 2 -1 -3 1 2 2 -4 -2 0 6 5 Z 1 2 3 4 -4 5 5 1 3 -1 -1 2 0 -4 1 1

14、1 -4 -3 0 5 6 PAM 250C-817WW u模塊替換矩陣模塊替換矩陣BLOSUM以序列片段為基礎(chǔ)以序列片段為基礎(chǔ),它是它是 基于蛋白質(zhì)模塊基于蛋白質(zhì)模塊(Block)數(shù)據(jù)庫而建立起來的數(shù)據(jù)庫而建立起來的 u 在模塊比對的每一列中，分別計(jì)算在模塊比對的每一列中，分別計(jì)算 兩兩氨基酸的變化情況兩兩氨基酸的變化情況,來自所有來自所有 模塊的數(shù)值被用來計(jì)算模塊的數(shù)值被用來計(jì)算BLOSUM矩陣矩陣u矩陣后面的數(shù)字表示構(gòu)建此矩陣所用的矩陣后面的數(shù)字表示構(gòu)建此矩陣所用的 序列的相似程度，如序列的相似程度，如BLOSUM62表示由表示由 相似度為相似度為62%的序列構(gòu)建的序列構(gòu)建AACECA

15、- C = 4A - E = 2C - E = 2A - A = 1C - C = 1AACECBLOSUM矩陣矩陣 (Blocks Substitution Matrix)BLOSUM62 如何選擇合適的評分矩陣？如何選擇合適的評分矩陣？n 一般來說一般來說,在局部相似性搜索上，在局部相似性搜索上， BLOSUM 矩陣矩陣較較PAM要好要好n當(dāng)比較距離相近的蛋白時，應(yīng)選擇低的當(dāng)比較距離相近的蛋白時，應(yīng)選擇低的PAM或高的或高的BLOSUM矩陣；當(dāng)比較距離較遠(yuǎn)的蛋白時，應(yīng)選擇矩陣；當(dāng)比較距離較遠(yuǎn)的蛋白時，應(yīng)選擇高的高的PAM或低的或低的BLOSUM矩陣矩陣 n 對于數(shù)據(jù)庫搜索來說一般選擇對于數(shù)

16、據(jù)庫搜索來說一般選擇BLOSUM62矩陣矩陣nPAM矩陣可用于尋找蛋白質(zhì)的進(jìn)化起源，矩陣可用于尋找蛋白質(zhì)的進(jìn)化起源，BLOSUM矩陣用于發(fā)現(xiàn)蛋白質(zhì)的保守域矩陣用于發(fā)現(xiàn)蛋白質(zhì)的保守域空位罰分空位罰分(Gap Penalties) 空位為了獲得兩個序列最佳比對，必須使用空位和空位為了獲得兩個序列最佳比對，必須使用空位和空位罰分空位罰分 空位罰分分為：空位開放罰分空位罰分分為：空位開放罰分(Gap opening penalty)和空位擴(kuò)展罰分和空位擴(kuò)展罰分(Gap extension penalty) 最優(yōu)的序列比對通常具有以下兩下特征：最優(yōu)的序列比對通常具有以下兩下特征： 盡可能多的匹配盡可能多

17、的匹配 盡可能少的空位盡可能少的空位 插入任意多的空位會產(chǎn)生較高的分?jǐn)?shù)，但找到的并插入任意多的空位會產(chǎn)生較高的分?jǐn)?shù)，但找到的并不一定是真正相似序列不一定是真正相似序列1 GTGATAGACAC | 1 GTGCATAGACAC空位罰分空位罰分允許空位但不罰分允許空位但不罰分 Score: 55 不允許有空位不允許有空位 Score: -21匹配匹配 = 5錯配錯配 = -41 GTG-ATAGACAC | |1 GTGCATAGACAC1 GTG-ATAGACAC | |1 GTGC-ATAGACAC?空位罰分公式空位罰分公式 A T G T T A T A CT A T G T G C G

18、T A T A 總分：總分：4空位參數(shù)空位參數(shù):g= 3(空位開放罰分空位開放罰分)r = 0.1(空位擴(kuò)展罰分空位擴(kuò)展罰分)x = 3(空位長度空位長度)Wx= -3 - (3 -1) 0.1 = -3.2 匹配匹配= 1錯配錯配= 0總分：總分：8 - 3.2 = 4.8Wx=g+r(x-1)Wx 為總空位記分，為總空位記分，g為空位開為空位開放罰分，放罰分，r為空位擴(kuò)展罰分，為空位擴(kuò)展罰分，x為空位長度為空位長度T A T G T G C G T A T A insertion / deletionA T G T - - - T A T A C雙序列比對方法雙序列比對方法 點(diǎn)陣序列比較點(diǎn)

19、陣序列比較(Dot Matrix Sequence Comparison) 動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法(Dynamic Programming Algorithm) 詞或詞或K串方法串方法(Word or K-tuple Methods) 貝葉斯統(tǒng)計(jì)方法貝葉斯統(tǒng)計(jì)方法(Bayesian Statistical Methods)點(diǎn)陣序列比較點(diǎn)陣序列比較(Dot Matrix Sequence Comparison) 點(diǎn)陣分析是一種簡單的圖形顯示序列相似性點(diǎn)陣分析是一種簡單的圖形顯示序列相似性的方法的方法,Gibbs&McIntyre(1970) 沿沿X軸上序列軸上序列1中的每一個單元（核苷酸或氨中

20、的每一個單元（核苷酸或氨基酸）與沿基酸）與沿Y軸的第二個序列中的每一個單軸的第二個序列中的每一個單元進(jìn)行比較，相同的區(qū)域在點(diǎn)陣圖中顯示為元進(jìn)行比較，相同的區(qū)域在點(diǎn)陣圖中顯示為由點(diǎn)組成的對角線，對角線之外零散的點(diǎn)為由點(diǎn)組成的對角線，對角線之外零散的點(diǎn)為背景噪音背景噪音IONIZATIONIONIZATION點(diǎn)陣分析中的插入或刪除點(diǎn)陣分析中的插入或刪除TACTGTCAT T A C T G T T C A TSequence 1Sequence 2T A C T G - T C A T| | | | | | | | |T A C T G T T C A T插入空位點(diǎn)陣分析的應(yīng)用點(diǎn)陣分析的應(yīng)用 自身

21、比對自身比對 尋找序列中的正向或反向重復(fù)序列尋找序列中的正向或反向重復(fù)序列 蛋白質(zhì)的重復(fù)結(jié)構(gòu)域蛋白質(zhì)的重復(fù)結(jié)構(gòu)域(domain) 相同殘基重復(fù)出現(xiàn)的低復(fù)雜區(qū)相同殘基重復(fù)出現(xiàn)的低復(fù)雜區(qū)(Low Complexity) RNA二級結(jié)構(gòu)中的互補(bǔ)區(qū)域等二級結(jié)構(gòu)中的互補(bǔ)區(qū)域等 對兩條序列的相似性作整體的估計(jì)對兩條序列的相似性作整體的估計(jì)點(diǎn)陣分析的應(yīng)用自身比對發(fā)現(xiàn)自身比對發(fā)現(xiàn)正向重復(fù)序列正向重復(fù)序列具有連續(xù)相似區(qū)域的兩條具有連續(xù)相似區(qū)域的兩條DNADNA序列的簡單點(diǎn)陣圖序列的簡單點(diǎn)陣圖正向重復(fù)點(diǎn)陣分析實(shí)例點(diǎn)陣分析實(shí)例 編碼噬菌體編碼噬菌體c（水平軸）和（水平軸）和噬菌噬菌體體P22 c2（垂直軸）（垂直軸

22、）的氨基酸序列間的的氨基酸序列間的點(diǎn)陣分析點(diǎn)陣分析 相同的點(diǎn)打印全部相同的點(diǎn)打印全部打印，很難找到有打印，很難找到有用的信息用的信息使用滑動窗口技術(shù)降低噪聲使用滑動窗口技術(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 G G T A T G A C A G T A T CC T A T G A C A T A C G G T A T GWindow=3 Word Size = 3使用滑動窗口技術(shù)降低噪聲使用滑動窗口技術(shù)降低噪

23、聲（a a）對人類（）對人類（Homo sapiensHomo sapiens）與黑猩猩（）與黑猩猩（Pongo pygmaeusPongo pygmaeus）的）的球蛋白基因序列進(jìn)行比較的完整點(diǎn)陣圖球蛋白基因序列進(jìn)行比較的完整點(diǎn)陣圖（b b）利用滑動窗口對以上的兩種球蛋白基因序列進(jìn)行比較的點(diǎn)陣圖，其中窗口大小為）利用滑動窗口對以上的兩種球蛋白基因序列進(jìn)行比較的點(diǎn)陣圖，其中窗口大小為1010個核苷酸，個核苷酸， 相似度閾值為相似度閾值為8 8，即，即1010個核苷酸中有個核苷酸中有8 8個相同時就打一個點(diǎn)個相同時就打一個點(diǎn)ab點(diǎn)陣分析的優(yōu)缺點(diǎn)點(diǎn)陣分析的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn) 直觀性，整體性直觀性，整

24、體性 點(diǎn)陣分析不依賴空位點(diǎn)陣分析不依賴空位(gap)參數(shù)，可尋找兩序列參數(shù)，可尋找兩序列間所有可能的殘基匹配間所有可能的殘基匹配 不依賴任何先決條件，是一種可用于初步分析的不依賴任何先決條件，是一種可用于初步分析的理想工具理想工具 點(diǎn)陣分析允許隨時動態(tài)地改變最高和最低界限值，點(diǎn)陣分析允許隨時動態(tài)地改變最高和最低界限值，可以用來摸索區(qū)分信號和背景標(biāo)準(zhǔn)的嚴(yán)格程度可以用來摸索區(qū)分信號和背景標(biāo)準(zhǔn)的嚴(yán)格程度點(diǎn)陣分析的優(yōu)缺點(diǎn)點(diǎn)陣分析的優(yōu)缺點(diǎn) 缺點(diǎn)缺點(diǎn) 不能很好地兼容距離矩陣不能很好地兼容距離矩陣 滑動窗口和預(yù)值的選擇過于經(jīng)驗(yàn)化滑動窗口和預(yù)值的選擇過于經(jīng)驗(yàn)化 信噪比較低信噪比較低 不適合進(jìn)行高通量的數(shù)據(jù)分析

25、不適合進(jìn)行高通量的數(shù)據(jù)分析點(diǎn)陣分析程序點(diǎn)陣分析程序 DNA Strider (Macintosh) http:/ Dotter (Unix/Linux, X-Windows) COMPARE, DOTPLOT in GCG PLALIGN (FASTA) Dotlet http:/www.isrec.isb-sib.ch/java/dotlet/Dotlet.html動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法(Dynamic Programming Algorithm)是綜合運(yùn)用是綜合運(yùn)用分級決策方法分級決策方法和和最優(yōu)最優(yōu)化原理化原理而形成的數(shù)學(xué)方法。而形成的數(shù)學(xué)方法。主要思路是把一個

26、復(fù)雜問題分成若干個關(guān)聯(lián)的子主要思路是把一個復(fù)雜問題分成若干個關(guān)聯(lián)的子問題，找出子問題的最優(yōu)解，進(jìn)而得出原來復(fù)雜問題，找出子問題的最優(yōu)解，進(jìn)而得出原來復(fù)雜問題的最優(yōu)解。問題的最優(yōu)解。動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法 在序列比對尤其是雙序列比對中非常重要。在序列比對尤其是雙序列比對中非常重要。將比對過程分為若干步，每一步增加一個位將比對過程分為若干步，每一步增加一個位置。可提供序列間最優(yōu)的對位排列。置?？商峁┬蛄虚g最優(yōu)的對位排列。 應(yīng)用最多的兩種動態(tài)規(guī)劃算法：應(yīng)用最多的兩種動態(tài)規(guī)劃算法：Needleman-Wunsch（全局比對）（全局比對） Smith-Waterman（局部比對）（局部比對）動態(tài)規(guī)劃算

27、法動態(tài)規(guī)劃算法填充矩陣填充矩陣構(gòu)建矩陣構(gòu)建矩陣確定遞歸計(jì)算方法確定遞歸計(jì)算方法矩陣回溯矩陣回溯動態(tài)規(guī)劃算法的簡單描述動態(tài)規(guī)劃算法的簡單描述序序列列 b序列序列a動態(tài)規(guī)劃算法的正式表述動態(tài)規(guī)劃算法的正式表述S Si,ji,j這個位置這個位置的分?jǐn)?shù)為圖中的分?jǐn)?shù)為圖中箭頭所示三個箭頭所示三個方向值中最大方向值中最大的一個的一個i -xi -1j -1i -yji Si - x,j - wx Si 1, j- 1 + s(ai , bj)Si, j - y - wy Si, j 動態(tài)規(guī)劃算法的數(shù)學(xué)形式動態(tài)規(guī)劃算法的數(shù)學(xué)形式Sij=maxSi-1,j-1+s(aibj) , maxx1 (Si-x,j-

28、wx),maxy 1 (Si,j-y-wy)Sij=maxSi-1,j-1+s(aibj) , maxx1 (Si-1,j-w),maxy 1 (Si,j-1-w)公式一的簡化公式一公式一公式二公式二說明：說明：Sij是序列是序列a a在位置在位置i i和序列和序列b b在位置在位置j j的分值，的分值，s(as(ai ib bj j) )是位置是位置i i和和j j上比對分值，上比對分值，w wx x是在序列是在序列a a 中長度為中長度為x x的空位罰的空位罰分，分，w wy y是序列是序列b b中長度為中長度為y y的空位罰分。的空位罰分。Needleman-Wunsch動態(tài)規(guī)劃算法舉例

29、動態(tài)規(guī)劃算法舉例例例:用動態(tài)規(guī)劃算法比對以下兩條序列用動態(tài)規(guī)劃算法比對以下兩條序列序列序列a: ACTTCG序列序列b: ACTAG記分規(guī)則記分規(guī)則:匹配匹配3錯配錯配-2空位空位-2Scoring MatrixACTTCGACTAGACTTCG0ACTAGScoring MatrixACTTCG0-2ACTAGScoring MatrixACTTCG0-2-4-6-8-10-12ACTAGScoring MatrixACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10Scoring MatrixACTTCG0-2-4-6-8-10-12A-23CTAGScoring MatrixACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27755G-10-505558GGT-CATTCCAA回溯回溯Scoring MatrixACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27755G-10-505558GGT-CATTCCAAScoring Matrix什么是第三什么是第三種可能？種可能？ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2