1、雙序列比對雙序列比對什么是序列比對？什么是序列比對？ 序列比對序列比對(Sequence Alignment)是通過在序是通過在序列中搜索一系列單個性狀或性狀模式來比較列中搜索一系列單個性狀或性狀模式來比較2個（雙序列比對）或更多（多重序列比對）個（雙序列比對）或更多（多重序列比對）序列的方法序列的方法 序列比對分類序列比對分類 雙序列比對：兩條序列的比對雙序列比對：兩條序列的比對 多序列比對：三條或以上序列的比對多序列比對：三條或以上序列的比對我們為什么關注序列比對我們為什么關注序列比對 相似的序列可能具有相同的功能與結構相似的序列可能具有相同的功能與結構 發現一個基因或蛋白哪些區域容易發生

2、突變，哪些發現一個基因或蛋白哪些區域容易發生突變，哪些位點突變后對功能沒有影響位點突變后對功能沒有影響 發現生物進化方面的信息發現生物進化方面的信息 同源性同源性(Homologous Genes) ：序列來自共同的祖先，：序列來自共同的祖先，或具有共同的進化史，相似的序列往往具有同源性或具有共同的進化史，相似的序列往往具有同源性(如圖如圖) 相似性相似性(Similarity)：兩序列根據某種參數相近，但相似：兩序列根據某種參數相近，但相似的序列不一定具有同源性。相似性的序列不一定具有同源性。相似性同源性，兩基因只有同源性，兩基因只有同源與非同源關系同源與非同源關系我們為什么關注序列比對（續

3、）我們為什么關注序列比對（續） 直系同源直系同源(Orthologs)：具有共同祖先與相似功：具有共同祖先與相似功能的同源基因（無基因復制事件）能的同源基因（無基因復制事件） 旁系同源旁系同源(Paralogs)：兩個物種：兩個物種A和和B的同源基因，的同源基因，分別是共同祖先基因組中由復制事件而產生的不分別是共同祖先基因組中由復制事件而產生的不同拷貝的后代同拷貝的后代 趨同進化趨同進化(Convergent evolution):序列中的相似序列中的相似區域可能不具有共同的祖先，而是通過兩條進化區域可能不具有共同的祖先，而是通過兩條進化路徑獨立獲得相同的功能（路徑獨立獲得相同的功能（如圖如圖

4、）同源序列與祖先序列關系同源序列與祖先序列關系進化距離：一個序列變成另一個序列所需的步驟數。進化距離：一個序列變成另一個序列所需的步驟數。如如A變為變為B的進化距離為：的進化距離為：x+y基因進化基因進化AB：物種：物種I與物種與物種II中的中的a1是直系同源，是直系同源，a1與與a2為旁系同源為旁系同源C：趨同進化，物種：趨同進化，物種I與物種與物種II經歷不同的進化途徑，產生相同的功能經歷不同的進化途徑，產生相同的功能D：基因轉移，稱為水平轉移基因：基因轉移，稱為水平轉移基因序列比對兩種類型序列比對兩種類型 全局序列比對全局序列比對l定義：定義：在全局范圍內對兩條序列進行比對打分的方法在全

5、局范圍內對兩條序列進行比對打分的方法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 計分矩陣計分矩陣 蛋白質計分矩陣蛋白質計分矩陣 廣泛使用的兩種矩陣廣泛使用的兩種矩陣 PAM BLOSUM 空位罰分空位罰分DNA 計分矩陣計分矩陣actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配: 1錯配: 0分值：5轉換和顛換轉換和顛換CTAG嘧啶嘧啶嘌呤嘌呤 表示表示轉換轉換(transition)， 表示表示顛換顛換(transversions)轉換比顛換更容易發生轉換比顛換更容易發生轉換和顛換轉換和顛換

7、AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99轉換速率是顛換轉換速率是顛換3倍時的模型倍時的模型蛋白質計分矩陣蛋白質計分矩陣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)矩陣矩陣 氨基酸記分系統需要替換的模式來提高靈敏度以檢測弱的相氨基酸記分系統需要替換的模式來提高靈敏度以檢測弱的相似性似性 氨基酸容易被其它生化、物理特性相似的氨基酸替換氨基酸容易被其它生化、物理特性相似的氨基酸替換 PAM矩陣給出了進化過程中同源蛋白質從一個氨基酸變到另矩陣給出了進化過程中同源蛋白質從一個氨基酸變到另一個氨基酸的似然率一個氨基酸的似然率(Likelihood) PAM1(

9、1個個PAM單位）被定義為每單位）被定義為每100個殘基出現一個被接個殘基出現一個被接受的點突變受的點突變(氨基酸的置換不引起蛋白質功能上的顯著變化）氨基酸的置換不引起蛋白質功能上的顯著變化） 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以序列片段為基礎以序列片段為基礎,它是它是 基于蛋白質模塊基于蛋白質模塊(Block)數據庫而建立起來的數據庫而建立起來的 u 在模塊比對的每一列中，分別計算在模塊比對的每一列中，分別計算 兩兩氨基酸的變化情況兩兩氨基酸的變化情況,來自所有來自所有 模塊的數值被用來計算模塊的數值被用來計算BLOSUM矩陣矩陣u矩陣后面的數字表示構建此矩陣所用的矩陣后面的數字表示構建此矩陣所用的 序列的相似程度，如序列的相似程度，如BLOSUM62表示由表示由 相似度為相似度為62%的序列構建的序列構建AACECA

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

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

17、的匹配 盡可能少的空位盡可能少的空位 插入任意多的空位會產生較高的分數，但找到的并插入任意多的空位會產生較高的分數，但找到的并不一定是真正相似序列不一定是真正相似序列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空位參數空位參數:g= 3(空位開放罰分空位開放罰分)r = 0.1(空位擴展罰分空位擴展罰分)x = 3(空位長度空位長度)Wx= -3 - (3 -1) 0.1 = -3.2 匹配匹配= 1錯配錯配= 0總分：總分：8 - 3.2 = 4.8Wx=g+r(x-1)Wx 為總空位記分，為總空位記分，g為空位開為空位開放罰分，放罰分，r為空位擴展罰分，為空位擴展罰分，x為空位長度為空位長度T A T G T G C G T A T A insertion / deletionA T G T - - - T A T A C雙序列比對方法雙序列比對方法 點陣序列比較點

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

20、的每一個單元（核苷酸或氨基酸）與沿基酸）與沿Y軸的第二個序列中的每一個單軸的第二個序列中的每一個單元進行比較，相同的區域在點陣圖中顯示為元進行比較，相同的區域在點陣圖中顯示為由點組成的對角線，對角線之外零散的點為由點組成的對角線，對角線之外零散的點為背景噪音背景噪音IONIZATIONIONIZATION點陣分析中的插入或刪除點陣分析中的插入或刪除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插入空位點陣分析的應用點陣分析的應用 自身

21、比對自身比對 尋找序列中的正向或反向重復序列尋找序列中的正向或反向重復序列 蛋白質的重復結構域蛋白質的重復結構域(domain) 相同殘基重復出現的低復雜區相同殘基重復出現的低復雜區(Low Complexity) RNA二級結構中的互補區域等二級結構中的互補區域等 對兩條序列的相似性作整體的估計對兩條序列的相似性作整體的估計點陣分析的應用自身比對發現自身比對發現正向重復序列正向重復序列具有連續相似區域的兩條具有連續相似區域的兩條DNADNA序列的簡單點陣圖序列的簡單點陣圖正向重復點陣分析實例點陣分析實例 編碼噬菌體編碼噬菌體c（水平軸）和（水平軸）和噬菌噬菌體體P22 c2（垂直軸）（垂直軸

22、）的氨基酸序列間的的氨基酸序列間的點陣分析點陣分析 相同的點打印全部相同的點打印全部打印，很難找到有打印，很難找到有用的信息用的信息使用滑動窗口技術降低噪聲使用滑動窗口技術降低噪聲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使用滑動窗口技術降低噪聲使用滑動窗口技術降低噪

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

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

25、不適合進行高通量的數據分析點陣分析程序點陣分析程序 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動態規劃算法動態規劃算法動態規劃算法動態規劃算法(Dynamic Programming Algorithm)是綜合運用是綜合運用分級決策方法分級決策方法和和最優最優化原理化原理而形成的數學方法。而形成的數學方法。主要思路是把一個

26、復雜問題分成若干個關聯的子主要思路是把一個復雜問題分成若干個關聯的子問題，找出子問題的最優解，進而得出原來復雜問題，找出子問題的最優解，進而得出原來復雜問題的最優解。問題的最優解。動態規劃算法動態規劃算法 在序列比對尤其是雙序列比對中非常重要。在序列比對尤其是雙序列比對中非常重要。將比對過程分為若干步，每一步增加一個位將比對過程分為若干步，每一步增加一個位置。可提供序列間最優的對位排列。置。可提供序列間最優的對位排列。 應用最多的兩種動態規劃算法：應用最多的兩種動態規劃算法：Needleman-Wunsch（全局比對）（全局比對） Smith-Waterman（局部比對）（局部比對）動態規劃算

27、法動態規劃算法填充矩陣填充矩陣構建矩陣構建矩陣確定遞歸計算方法確定遞歸計算方法矩陣回溯矩陣回溯動態規劃算法的簡單描述動態規劃算法的簡單描述序序列列 b序列序列a動態規劃算法的正式表述動態規劃算法的正式表述S Si,ji,j這個位置這個位置的分數為圖中的分數為圖中箭頭所示三個箭頭所示三個方向值中最大方向值中最大的一個的一個i -xi -1j -1i -yji Si - x,j - wx Si 1, j- 1 + s(ai , bj)Si, j - y - wy Si, j 動態規劃算法的數學形式動態規劃算法的數學形式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動態規劃算法舉例

29、動態規劃算法舉例例例:用動態規劃算法比對以下兩條序列用動態規劃算法比對以下兩條序列序列序列a: ACTTCG序列序列b: ACTAG記分規則記分規則:匹配匹配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