生物信息學(xué)基礎(chǔ)-第三章課件

1、第三章第三章 序列比對序列比對主講教師：丁彥蕊主講教師：丁彥蕊單位：信息工程學(xué)院單位：信息工程學(xué)院序列比對：序列比對：尋找兩條或者兩條以上的序?qū)ふ覂蓷l或者兩條以上的序列中各個字符的一一對應(yīng)關(guān)系。列中各個字符的一一對應(yīng)關(guān)系。序列比對的根本任務(wù)：序列比對的根本任務(wù)：發(fā)現(xiàn)序列之間的相似性發(fā)現(xiàn)序列之間的相似性尋找共同區(qū)域?qū)ふ夜餐瑓^(qū)域辨別序列之間的差異辨別序列之間的差異目的：目的：相似序列相似序列 相似的相似的結(jié)構(gòu)，相似的功能結(jié)構(gòu)，相似的功能 判別序列之間的同源性判別序列之間的同源性推測序列之間的進化關(guān)系推測序列之間的進化關(guān)系 第一節(jié)第一節(jié) 序列的相似性序列的相似性同源（同源（homology）- 具有

2、共同的祖先具有共同的祖先(P81)直向同源（直向同源（Orthologous ）:共同祖先的直接后代共同祖先的直接后代（沒有發(fā)生基因復(fù)制事件）之間的同源基因稱為直（沒有發(fā)生基因復(fù)制事件）之間的同源基因稱為直向同源。向同源。 共生同源（共生同源（paralogous ）:兩個物種兩個物種A和和B的同源基因，的同源基因，分別是共同祖先基因組中由復(fù)制事件而產(chǎn)生的不同分別是共同祖先基因組中由復(fù)制事件而產(chǎn)生的不同拷貝的后代，這被稱為共生同源基因。拷貝的后代，這被稱為共生同源基因。相似（相似（similarity）同源序列一般是相似的同源序列一般是相似的 相似序列不一定是同源的相似序列不一定是同源的 進化

3、趨同（同功能）進化趨同（同功能）序列比較的基本操作是比對（序列比較的基本操作是比對（Alignment） 兩個序列的比對是指這兩個序列中各個字符的一種兩個序列的比對是指這兩個序列中各個字符的一種一一對應(yīng)關(guān)系，或字符的對比排列一一對應(yīng)關(guān)系，或字符的對比排列 。設(shè)有兩個序列：GACGGATTAG，GATCGGAATAGAlignment2: GA CGGATTAGGATCGGAATAGAlignment1:GACGGATTAG GATCGGAATAG1、字母表和序列、字母表和序列字母表字母表4字符DNA字母表：A, C, G, T擴展的遺傳學(xué)字母表或IUPAC編碼單字母氨基酸編碼符 號含 義說 明

4、GGGuanine AAAdenine TTThymine CCCytosineRG or APurine YT or CPyrimidine MA or CAmino KG or TKeto SG or CStrong interaction (3 H bonds) WA or TWeak interaction (2 H bonds) HA or C or TNot-GBG or T or Cnot-AVG or C or Anot-T(not-U) DG or A or Tnot-C NG or A or T or CAny 擴展的遺傳學(xué)字母表或IUPAC編碼氨基酸名稱氨基酸名稱簡簡 寫

5、寫氨基酸名稱氨基酸名稱簡簡 寫寫甘氨酸G絲氨酸S丙氨酸A蘇氨酸T纈氨酸V天冬酰胺N異亮氨酸I谷酰胺Q亮氨酸L酪氨酸Y苯丙氨酸F組氨酸H脯氨酸P天冬氨酸D甲硫氨酸M谷氨酸E色氨酸W賴氨酸K半胱氨酸C精氨酸R特定的符號 代表字母表 A* 代表由字母表A中字符所形成的一系列有限長度序列或字符串的集合 a、b、c代表單獨的字符 s、t、u、v代表A*中的序列 |s|代表序列s的長度為了說明序列s的子序列和s中單個字符，在s中各字符之間用數(shù)字標(biāo)明分割邊界例如，設(shè)s=ACCACGTA，則s可表示為 0A1C2C3A4C5G6T7A8 i:s:j 指明第i位或第j位之間的子序列, 當(dāng)然，0 i j |s|。

6、 子序列0:s: i 稱為前綴，即prefix(s,i)子序列 i:s:|s|稱為后綴，即suffix(s, |s|-i+1) i:s: i 為空序列j-1:s:j 表示s 中的第j 個字符，簡記為sj子序列與子串（子序列與子串（p82）子序列：子序列：選取s中的某些字符（或刪除s中的某些字符）而形成s的子序列例如： TTT 是 ATATAT的子序列。 s的子串的子串：是由s中相繼的字符所組成。 例如：TAC是AGTACA的子串，但不是TTGAC的子串（是子序列）。 子串是子序列子串是子序列子序列不一定是子串子序列不一定是子串字符串操作字符串連接操作：兩個序列s和t的連接： s + + t例如

7、：ACC+CTA = ACCCTA 字符串k操作 刪除字符串兩端的字符 其定義如下：prefix(s,l) = sk|s|-lsuffix(s,l) = k|s|-ls i:s:j = ki-1sk|s|-j 序列比較可以分為四種基本情況序列比較可以分為四種基本情況(P83)（1）兩條長度相近的序列相似）兩條長度相近的序列相似 找出序列的差別找出序列的差別（2）判斷一條序列的前綴與另一條序列的后綴相似）判斷一條序列的前綴與另一條序列的后綴相似（3）判斷一條序列是否是另一條序列的子序列）判斷一條序列是否是另一條序列的子序列（4）判斷兩條序列中是否有非常相似的子序列）判斷兩條序列中是否有非常相似的

8、子序列2、編輯距離（、編輯距離（Edit Distance)GCATGACGAATCAG TATGACAAACAGC GCATGACGAATCAG TATGAC-AAACAGC 說明兩條序列的相似程度說明兩條序列的相似程度 定量計算定量計算 兩條序列的相似程度的定量計算相似度相似度，它是兩個序列的函數(shù)，其值越大，表示兩個序列越相似 兩個序列之間的距離距離。距離越大，則兩個序列的相似度就越小 字符編輯操作（Edit Operation）字符編輯操作可將一個序列轉(zhuǎn)化為一個新序列 Match（a，a）Delete（a，-） Replace（a，b）Insert（-，b）直接距離計算的不足直接距離計算

9、的不足擴展的編輯操作ACCGACAATATGCATA ATAGGTATAACAGTCAACCGACAATATGCATA ACTGACAATATGGATA 第二條序列頭尾顛倒CTAGTCGAGGCAATCTGAACAGCTTCGTTAGT ？反向互補序列反向互補序列RNA發(fā)夾式二級結(jié)構(gòu)發(fā)夾式二級結(jié)構(gòu)3、通過點矩陣進行序列比較、通過點矩陣進行序列比較“矩陣作圖法矩陣作圖法” 或或 “對角線作圖對角線作圖” 序列序列1 序列序列2 實實 例例 序列序列1 序列序列1 自我比較自我比較滑動窗口技術(shù)滑動窗口技術(shù)兩條序列中有很多匹配的字符對，因而在點矩陣中兩條序列中有很多匹配的字符對，因而在點矩陣中會形成

10、很多點標(biāo)記。會形成很多點標(biāo)記?；瑒哟翱诩夹g(shù)滑動窗口技術(shù) 使用滑動窗口代替一次一個位點的比較是解決這使用滑動窗口代替一次一個位點的比較是解決這個問題的有效方法。個問題的有效方法。 假設(shè)窗口大小為假設(shè)窗口大小為10，相似度閾值為，相似度閾值為8，則每次比較，則每次比較取取10個連續(xù)的字符，如相同的字符超過個連續(xù)的字符，如相同的字符超過8個，則標(biāo)個，則標(biāo)記記 基于滑動窗口的點矩陣方法可以明顯地降低點陣基于滑動窗口的點矩陣方法可以明顯地降低點陣圖的噪聲，并且明確無誤的指示出了兩條序列間具圖的噪聲，并且明確無誤的指示出了兩條序列間具有顯著相似性的區(qū)域。有顯著相似性的區(qū)域。 （a）對人類（）對人類（Hom

11、o sapiens）與黑猩猩（）與黑猩猩（Pongo pygmaeus）的）的球蛋白基因球蛋白基因序列進行比較的完整點陣圖。（序列進行比較的完整點陣圖。（b）利用滑動窗口對以上的兩種球蛋白基因序列進）利用滑動窗口對以上的兩種球蛋白基因序列進行比較的點陣圖，其中窗口大小為行比較的點陣圖，其中窗口大小為10個核苷酸，相似度閾值為個核苷酸，相似度閾值為8。 (a) (b) 具有連續(xù)相似區(qū)域的兩條具有連續(xù)相似區(qū)域的兩條DNA序列的簡單點陣圖序列的簡單點陣圖4、 序列的兩兩比對序列的兩兩比對序列的兩兩比對序列的兩兩比對(Pairwise Sequence Alignment）:通過字符匹配和替換，或者通

12、過字符匹配和替換，或者插入和刪除字符，使兩條序列達到一樣插入和刪除字符，使兩條序列達到一樣的長度，并使兩條序列中相同的字符盡的長度，并使兩條序列中相同的字符盡可能一一對應(yīng)。可能一一對應(yīng)。 s:AGCACACAAGCACACA t:ACACACTAACACACTA Match(A, A)Match(A, A)Delete(G, - )Replace(G, C)Match(C, C)Insert( -, A)Match(A, A)Match(C, C)Match(C, C)Match(A, A)Match(A, A)Match(C, C)Match(C, C)Replace(A, T)Insert

13、( -, T)Delete(C, -)Match(A, A)Match(A, A)圖3.6 序列AGCACACA和ACACACTA的兩種比對結(jié)果Alignment -1 Alignment -2不同編輯操作的代價不同不同編輯操作的代價不同編輯操作定義函數(shù)w，它表示“代價（cost）”或“權(quán)重（weight）”。對字母表中的任意字符a、b，定義 w (a, a) = 0 w (a, b) = 1 a b w (a, -) = w ( -, b) = 1 也可以使用得分（score）函數(shù)來評價編輯操作 p (a, a) = 1 p (a, b) = 0 a b p (a, -) = w ( -,

14、b) = -1 概念概念兩條序列兩條序列s 和和 t 的比對的得分（或代價）等于將的比對的得分（或代價）等于將s 轉(zhuǎn)化為轉(zhuǎn)化為t 所用的所有編輯操作的得分（或代價）總所用的所有編輯操作的得分（或代價）總和；和；s 和和t 的最優(yōu)比對是所有可能的比對中得分最高的最優(yōu)比對是所有可能的比對中得分最高（或代價最小）的一個比對；（或代價最?。┑囊粋€比對；s 和和t 的真實距離應(yīng)該是在得分函數(shù)的真實距離應(yīng)該是在得分函數(shù)p值（或代價值（或代價函數(shù)函數(shù)w值）最優(yōu)時的距離。值）最優(yōu)時的距離。 例如：例如：s:AGCACAC At:A CACACTA cost=2 s:AGCACAC A t:A CACACTA

15、score (s，t）= 5序列比對的目的是尋找一個得分最大（或代價序列比對的目的是尋找一個得分最大（或代價最?。┑谋葘?。最?。┑谋葘?。5、打分矩陣（、打分矩陣（Weight Matrices）(P87) （1）核酸打分矩陣設(shè)DNA序列所用的字母表為 = A，C，G，T a. 等價矩陣（相同核苷酸得分為1，不同核苷酸替換得分為0） b. BLAST矩陣（相同核苷酸得分為+5，不同核苷酸得分為-4）c. 轉(zhuǎn)移矩陣（transition，transversion） （嘌呤：腺嘌呤A，鳥嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T） ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-

16、45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51表3.1 等價矩陣表表3.3 轉(zhuǎn)移矩陣表3.2 BLAST矩陣（2）蛋白質(zhì)打分矩陣（i）等價矩陣等價矩陣jijiRij01其中Rij代表打分矩陣元素i、j分別代表字母表第i和第j個字符。（ii） 氨基酸突變代價矩陣氨基酸突變代價矩陣GCM GCM矩陣通過計算一個氨基酸殘基轉(zhuǎn)變到另外一個氨基酸殘基所需矩陣通過計算一個氨基酸殘基轉(zhuǎn)變到另外一個氨基酸殘基所需的密碼子變化數(shù)目而得到，矩陣元素的值對應(yīng)于代價。如果變化一的密碼子變化數(shù)目而得到，矩陣元素的值對應(yīng)于代價。如果變化一個堿基就可以使

17、一個氨基酸的密碼子改變?yōu)榱硪粋€氨基酸的密碼子，個堿基就可以使一個氨基酸的密碼子改變?yōu)榱硪粋€氨基酸的密碼子，則這兩個氨基酸的替換代價為則這兩個氨基酸的替換代價為1，如果需要兩個堿基的改變，則替換，如果需要兩個堿基的改變，則替換代價為代價為2，以此類推。，以此類推。 GCM矩陣常用于進化距離的計算，其優(yōu)點是計算結(jié)果可以直接用于矩陣常用于進化距離的計算，其優(yōu)點是計算結(jié)果可以直接用于繪制進化樹，但在蛋白質(zhì)序列比對尤其是相似程度較低的序列比對繪制進化樹，但在蛋白質(zhì)序列比對尤其是相似程度較低的序列比對中很少使用。中很少使用。（iii）疏水矩陣）疏水矩陣根據(jù)氨基酸殘基替換前后疏水性的變化得到的矩陣。如果氨根

18、據(jù)氨基酸殘基替換前后疏水性的變化得到的矩陣。如果氨基酸基酸A被氨基酸被氨基酸B替換后，疏水性變化不大則替換得分高，替換后，疏水性變化不大則替換得分高，否則替換得分低。否則替換得分低。（iv）PAM矩陣（矩陣（Point Accepted Mutation）統(tǒng)計自然界中各種氨基酸殘基的相互替換率。如果兩種特定統(tǒng)計自然界中各種氨基酸殘基的相互替換率。如果兩種特定的氨基酸之間替換發(fā)生得比較頻繁，則這一對氨基酸在得分的氨基酸之間替換發(fā)生得比較頻繁，則這一對氨基酸在得分矩陣中的互換得分就高。矩陣中的互換得分就高。PAM矩陣基于進化原理，建立在進化的點接受突變模型基矩陣基于進化原理，建立在進化的點接受突變

19、模型基礎(chǔ)上，通過統(tǒng)計相似序列中的各種氨基酸替換發(fā)生率而得到礎(chǔ)上，通過統(tǒng)計相似序列中的各種氨基酸替換發(fā)生率而得到的矩陣。的矩陣。PAM矩陣（矩陣（Point Accepted Mutation） 基于進化的點突變模型基于進化的點突變模型 一個一個PAM就是一個進化的變異單位就是一個進化的變異單位, 即即1%的氨基酸改變的氨基酸改變 這類矩陣里列出同源蛋白質(zhì)在進化過程中氨基酸變化的可能性。這類矩陣里列出同源蛋白質(zhì)在進化過程中氨基酸變化的可能性。 這類矩陣式基于進化原理的這類矩陣式基于進化原理的 證據(jù)：證據(jù)： 編碼相同蛋白質(zhì)的基因隨著進化發(fā)生分歧，相似度降低。編碼相同蛋白質(zhì)的基因隨著進化發(fā)生分歧，相

20、似度降低。 科學(xué)科學(xué) 用得多用得多 矩陣集合矩陣集合- PAM-N如，如，PAM120矩陣用于比較相距矩陣用于比較相距120個個PAM單位的序列。單位的序列。一個一個PAM-N矩陣矩陣元素（元素（i，j）的值：的值： 反應(yīng)兩個相距反應(yīng)兩個相距N個個PAM單位的序列中第單位的序列中第i種氨基酸種氨基酸替替換換第第j種氨基酸的頻率。種氨基酸的頻率。針對不同的進化距離采用針對不同的進化距離采用PAM 矩陣矩陣序列相似度序列相似度 = 40% 50% 60% | | |打分矩陣打分矩陣 = PAM120 PAM80 PAM 60PAM250 14% - 27% （v） BLOSUM矩陣矩陣 （Bloc

21、ks Amino Acid Substitution Matrices）通過統(tǒng)計相似蛋白質(zhì)序列的替換率得到的。PAM矩陣是從蛋白質(zhì)序列的全局比對結(jié)果推導(dǎo)出來的，而BLOSUM矩陣是從蛋白質(zhì)序列塊比對而推導(dǎo)出來的。BLOSUM 62第二節(jié)第二節(jié) 兩兩比對算法兩兩比對算法1、序列兩兩比對基本算法、序列兩兩比對基本算法直接方法直接方法 生成兩個序列所有可能的比對，分別計算代生成兩個序列所有可能的比對，分別計算代價函數(shù)，然后挑選一個代價最小的比對作為最終結(jié)果。價函數(shù)，然后挑選一個代價最小的比對作為最終結(jié)果。本質(zhì)問題：優(yōu)化本質(zhì)問題：優(yōu)化動態(tài)規(guī)劃尋優(yōu)策略動態(tài)規(guī)劃尋優(yōu)策略動態(tài)規(guī)劃算法（動態(tài)規(guī)劃算法（Dyna

22、mic Programming）（）（P93）最短路經(jīng)問題最短路經(jīng)問題起點起點終點終點C1 C2 W1 W2路徑1：C1 + w1 ？路徑2：C2 + w2 ？ 取最小值！取最小值！算法求解算法求解: 從起點到終點逐層計算從起點到終點逐層計算利用利用動態(tài)規(guī)劃動態(tài)規(guī)劃方法求解序列的兩兩比對方法求解序列的兩兩比對起點起點終點終點ATTCCGAAGA AGTCGAAGGTATTCCGAAG AGTCGAAGGAT+（1）ATTCCGAAGA AGTCGAAGG-T+（2）ATTCCGAAG AGTCGAAGGTA-+（3）求解過程求解過程起點起點終點終點ATTCCGAAGA AGTCGAAGGT 從

23、兩個序列前端開始從兩個序列前端開始 逐步推進逐步推進 直到兩個序列的末端。直到兩個序列的末端。序列S: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case1:匹配（si，tj )中間過程：比對中間過程：比對0:S:i 與與 0:T:j 序列S: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case2:刪除（si， -） 序列S: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case3:插入（ -，tj ） 設(shè)序列設(shè)序列s

24、、t的長度分別為的長度分別為m和和n?？紤]兩個前綴考慮兩個前綴 0:s:i 0:t:j 假如已知序列假如已知序列0:s:i 和和0:t:j 所有較短子列的最優(yōu)比對，即已知：所有較短子列的最優(yōu)比對，即已知：（1）0:s:(i-1) 和和 0:t:(j-1) 的最優(yōu)比對的最優(yōu)比對（2） 0:s:(i-1) 和和 0:t:j 的最優(yōu)比對的最優(yōu)比對（3） 0:s:i 和和 0:t:(j-1) 的最優(yōu)比對的最優(yōu)比對則則0:s:i和和 0:t:j 的最優(yōu)比對一定是上述三種情況之一的擴展的最優(yōu)比對一定是上述三種情況之一的擴展（1）替換（）替換（si，tj）或匹配（）或匹配（si，tj ) ，這取決于，這取決

25、于si 是否等于是否等于tj ；（2）刪除（）刪除（si， -）；）；（3）插入（）插入（ -，tj ）。）。 ):, :(00jitsS令：令：為序列為序列0:s:i和與序列和與序列 0:t:j 比對的得分比對的得分按下述方法求解按下述方法求解 其初值為：其初值為：for i=1 , 2 ,., mfor j=1 , 2 ,., n),():, :(),():,:(),():,:(max):, :()1(000)1(0)1(0)1(000jjiijijijijitptsSsptsStsptsStsS),():,:():,:(),():,:():, :(0):,:() 1(00000000)

26、1(00000000jjjiiitptsStsSsptsStsStsS距離矩陣距離矩陣按照上述方法，對于給定的得分函數(shù)按照上述方法，對于給定的得分函數(shù)p，兩，兩個序列所有前綴的得分定義了一個個序列所有前綴的得分定義了一個(m+1) (n+1)的距離矩陣的距離矩陣D = ( d i , j )其中其中d i , j = S (0:s:i , 0:t:j ) d i , j的計算公式如下：的計算公式如下：),(),(),(max1, 11, 1,jjiijijijijitpdspdtspddd i , j 最小值的三種選擇決定了各矩陣元素之間的關(guān)系，最小值的三種選擇決定了各矩陣元素之間的關(guān)系，用下

27、圖表示：用下圖表示：di,jdi,j-1di-1,jdi-1,j-1 距離矩陣元素d i , j 的計算S (0:s:i , 0:t:j )S (0:s:i-1 , 0:t:j )S (0:s:i-1 , 0:t:j-1 )S (0:s:i , 0:t:j-1 )動態(tài)規(guī)劃算法計算過程動態(tài)規(guī)劃算法計算過程： 計算過程從計算過程從d 0 , 0開始開始 可以是按行計算，每行從左到右，也可以是按列計算，每可以是按行計算，每行從左到右，也可以是按列計算，每列從上到下。列從上到下。 當(dāng)然，任何計算過程，只要滿足在計算當(dāng)然，任何計算過程，只要滿足在計算d i , j時時 d i-1 , j、d i-1 ,

28、 j-1、和、和d i, j-1都已經(jīng)被計算這個條件即可。都已經(jīng)被計算這個條件即可。 在計算在計算d i , j后，需要保存后，需要保存d i , j是從是從d i-1 , j、d i-1 , j-1、或、或d i, j-1中的哪一個推進的，或保存計算的路徑，以便于后續(xù)處理。中的哪一個推進的，或保存計算的路徑，以便于后續(xù)處理。上述計算過程到上述計算過程到d m , n結(jié)束。結(jié)束。 最優(yōu)路徑求解：最優(yōu)路徑求解：與計算過程相反與計算過程相反 從從d m , n開始，反向前推。開始，反向前推。 假設(shè)在反推時到達假設(shè)在反推時到達d i ,j，根據(jù)保存的計算路徑判斷，根據(jù)保存的計算路徑判斷d i , j

29、究竟是根據(jù)究竟是根據(jù)d i-1 , j、d i-1 , j-1、和、和d i, j-1中的那一個中的那一個計算而得到的。找到這個點以后，再從此點出發(fā)，計算而得到的。找到這個點以后，再從此點出發(fā)，一直到一直到d 0 , 0為止。為止。 走過的這條路徑就是最優(yōu)路徑（即代價最小路走過的這條路徑就是最優(yōu)路徑（即代價最小路徑），其對應(yīng)于兩個序列的最優(yōu)比對。徑），其對應(yīng)于兩個序列的最優(yōu)比對。 計算過程：計算過程：（1）初始化）初始化計算過程：計算過程：（2）反復(fù)計算）反復(fù)計算按列計算按列計算計算過程：計算過程：（2）反復(fù)計算）反復(fù)計算按行計算按行計算其他方式其他方式計算過程：計算過程：（3）求最佳路徑）求

30、最佳路徑t ts s ACACACTAAGCACACA例：例：s = AGCACACAt = ACACACTA 得分矩陣得分矩陣D （99 9）t ts s ACACACTA0-1-2-3-4-5-6-7-8A-1G-2C-3A-4C-5A-6C-7A-8初始化初始化計算計算d（2，2）t ts s ACACACTA0-1-2-3-4-5-6-7-8A-110-1-2-3-4-5-6G-201C-3A-4C-5A-6C-7A-8最終的得分矩陣最終的得分矩陣及序列比對及序列比對t ts s ACACACTA0-1-2-3-4-5-6-7-8A-110-1-2-3-4-5-6G-2010-1-2-

31、3-4-5C-3-11110-1-2-3A-4-2021210-1C-5-3-1132321A-6-4-2024333C-7-5-3-113543A-8-6-4-202455AGCACAC A| | |A CACACTA舉例例 1: Si 和 Tj對齊 S: C A T T C A C T: C - T T C A Gi - 1ijj -1 S: C A T T C A - C T: C - T T C A G - 例 2: Si 中加入空位i - 1ij S: C A T T C A C - T: C - T T C A - G例 3: Tj 是入空位i jj -1計算過程C(n,m)C(0

32、,0)C(i,j) 1j, i (C,) j, 1i (C),T,S(w) 1j, 1i (Cmax) j, i (CjiC(i-1,j)C(i-1,j-1)C(i,j-1) C T C G C A G CACTTCAC+10 匹配, -2 不匹配, -5 空位 0 -5 -10 -15 -20 -25 -30 -35 -40-5-10-15-20-25-30-3510 50-5-10-15-20-25-30-35-40-51050-5-10-15-20-25-10583-2-70-5-10-150151050-5-2-7-20-5101383-2-7-4-25-1052015181383-3

33、0-150151813282318-35-20-5101328232633 C T C G C A G CACTTCAC回溯得到最佳的比對*C - T C G C A G CC A T - T C A - CC - T C G C A G CC A T T - C A - C第一種比對方式第二種比對方式2 2、子序列與完整序列的比對、子序列與完整序列的比對-AGCT-ATGCAGCTGCTT目標(biāo)：目標(biāo)：使使S(s, i:t:j ) 最大最大序列S:序列t: i j不計前綴0:t:i 的得分, 也不計刪除后綴的j+1:t:|t|得分局部序列比對給定兩條序列0:s:m和0:t:n，從t中尋找一個子

34、序列i:t:j使得S(s,i:t:j)最大.不計前綴不計前綴0:t:i 的得分的得分處理第一行處理第一行t ts s ACACACTA000000000AGCACACA0):,:(000itsS不計刪除后綴的不計刪除后綴的j+1:t:|t|得分得分 處理最后一行處理最后一行):,:(),():,:(),():,:(max):,:() 1(000) 1(0) 1(0) 1(000jmmjmjmjmjmtsSsptsStsptsStsSdm,jdm,j-1dm-1,jdm-1,j-1S (0:s:i , 0:t:j )S (0:s:i-1 , 0:t:j )S (0:s:i-1 , 0:t:j-1

35、 )S (0:s:i , 0:t:j-1 )不計代價不計代價距離矩陣初始化時，對第一行進行如下處理：距離矩陣初始化時，對第一行進行如下處理：d0,j = 0 for 0 j n 最后一行的計算應(yīng)該是：最后一行的計算應(yīng)該是：同樣，同樣，d m, n依然是最優(yōu)局部比對的得分，而匹配的子列依然是最優(yōu)局部比對的得分，而匹配的子列i:t:j 按如下方式尋找：按如下方式尋找： （1） j = min k d m ,k = d m ,n （2）由（）由（m,j）反推比對路徑，最終通過斜線（非空位）到達（）反推比對路徑，最終通過斜線（非空位）到達（0，i）。）。 （3-10）（3-11） 1, 11, 1,)

36、,(),(maxjmmjmjmjmjmdspdtspdd3、尋找最大的相似子序列、尋找最大的相似子序列目標(biāo)：目標(biāo)：使使dw (i:s :j, i:t:j ) 最大最大序列S:序列t: i ji j數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：（m+1） （n+1）的矩陣）的矩陣 D但是，對數(shù)組元素含義解釋與基本算法有所不同但是，對數(shù)組元素含義解釋與基本算法有所不同每個元素的值代表序列每個元素的值代表序列0:s:i 某個某個后綴后綴和序列和序列0:t:j 某個某個后綴后綴的最佳比對。的最佳比對。 這種局部比對不計前綴的得分，所以新的邊界條件是：d0,j = 0 for 0 j n （3-12）di,0 = 0for 1

37、i m另外，由于0:s:i 和0:t:j 總有一個得分為“0”的空后綴比對，因此矩陣D中的所有元素大于或等于“0”，于是，新的遞歸計算公式為：(3-13)0),(),(),(max1, 11, 1,jjiijijijijitpdspdtspdd尋找最佳比對的子序列尋找最佳比對的子序列在矩陣中找最大值在矩陣中找最大值該值就是最優(yōu)的局部比對得分該值就是最優(yōu)的局部比對得分該值對應(yīng)的點為序列局部比對的末點該值對應(yīng)的點為序列局部比對的末點然后反向推演前面的最優(yōu)路徑，直到局部比對的起點。然后反向推演前面的最優(yōu)路徑，直到局部比對的起點。 TATA|TATA4、準全局比較、準全局比較所謂準全局比較就是在評價序

38、列比對時不計終端“空缺”（end space，或空位）的得分或代價 序列序列1 長度為長度為8序列序列2 長度為長度為18（a）6個匹配，個匹配，1個失配，個失配，1個空位個空位 （b）8個匹配個匹配情況1 ：不記s后面的空位與 t 后綴比對的得分在矩陣di,j中取最后一行的最大值.序列S:序列t: i ji j空位后綴情況2 ：不記s前面的空位與 t 前綴比對的得分將矩陣di,j中的第一行各元素值置為“0”序列S:序列t: i ji j空位前綴情況3：情況4：半全局比較算法與基本算法在計算半全局比較算法與基本算法在計算di,j時的區(qū)別歸納為時的區(qū)別歸納為下列四個方面：下列四個方面：（1）第一

39、行初始值為“0”，表示不計第一個序列的前端空位；（2）尋找最后一行的最大值，表示不計第一個序列的末端空位；（3）第一列初始值為“0”，表示不計第二個序列的前端空位；（4）尋找最后一列的最大值，表示不計第二個序列的末端空位。對于最后一行和最后一列的另一種處理辦法是：對于最后一行和最后一列的另一種處理辦法是：最后一行的橫向移動不被空位罰分最后一行的橫向移動不被空位罰分最后一列的縱向移動也不被罰分最后一列的縱向移動也不被罰分這樣，就可以允許在兩條序列終端自由存在空位。這樣，就可以允許在兩條序列終端自由存在空位。 當(dāng)矩陣當(dāng)矩陣D所有元素計算完以后，其右下角得值即為兩條序列最所有元素計算完以后，其右下角

40、得值即為兩條序列最終準全局比對的得分。終準全局比對的得分。 ACACTGATCG|ACACTG5、關(guān)于連續(xù)空位的問題、關(guān)于連續(xù)空位的問題K 階空位 K個連續(xù)的空位字符 “-”ATG-A-T-C-A-GATG-ATCAGATGCAGTGCAATGATGTTTTTATCAG生物學(xué)意義 “插入” 或“刪除” 突變突變次數(shù)連續(xù)空位可能對應(yīng)于一次突變非連續(xù)空位對應(yīng)于 多次突變對于連續(xù)空位的代價是一個線性的函數(shù)。設(shè)p（k）代表空位得分函數(shù)，其中k是連續(xù)空位的個數(shù)，則： p（k）= -bk 這里b（0）是單個“空位”得分的絕對值。處理方法：任何一個比對可以被唯一地分為若干個相繼的塊。有三類塊：（1）兩個字符

41、的比對（2）與序列s空位進行比對的t的最大連續(xù)字符序列（3） 與序列t空位進行比對的s的最大連續(xù)字符序列上述算法的時間復(fù)雜度為上述算法的時間復(fù)雜度為O(n3)。比起標(biāo)準算法，其多花的時間主要用于處理連續(xù)的空位。那么，是比起標(biāo)準算法，其多花的時間主要用于處理連續(xù)的空位。那么，是否可以改進連續(xù)空位的得分函數(shù)，而使得算法的時間復(fù)雜度降低為否可以改進連續(xù)空位的得分函數(shù)，而使得算法的時間復(fù)雜度降低為O(n2)呢？呢？如果認為k個連續(xù)空位比k個孤立空位出現(xiàn)的可能性更大，則p(k) kp(1) （3-22）或更一般地，p(k1 + k2 + + kn ) p(k1) + p(k2) + +p(kn) (3-

42、23)可以用下式重新計算連續(xù)“空位”的得分：p(0)=0（3-24） p(k) = h g(k-1), k1 （3-25） h0，g0，hg。 6、比較相似序列、比較相似序列相似序列快速比較算法 例如，有兩個序列： s=GCGCATGGATTGAGCGA t=TGCGCCATGGATGAGCA 最優(yōu)比對所對應(yīng)的路徑偏離主對角線，經(jīng)過一段以后重新返回主對角線。經(jīng)驗法則（針對蛋白質(zhì)序列）：經(jīng)驗法則（針對蛋白質(zhì)序列）： 如果兩個序列的長度都大于如果兩個序列的長度都大于100，在適當(dāng)?shù)丶尤肟?，在適當(dāng)?shù)丶尤肟瘴恢?，它們配對的相同率達到位之后，它們配對的相同率達到25%以上，則兩個以上，則兩個序列相關(guān)；

43、序列相關(guān)； 如果配對的相同率小于如果配對的相同率小于15%，則不管兩個序列的，則不管兩個序列的長度如何，它們都不可能相關(guān)；長度如何，它們都不可能相關(guān)； 如果兩個序列的相同率在如果兩個序列的相同率在15% 25%之間，它們可之間，它們可能是相關(guān)的。能是相關(guān)的。第三節(jié)第三節(jié) 序列多重比對序列多重比對多序列比對的定義設(shè)有k個序列s1, s2, . ,sk，每個序列由同一個字母表中的字符組成，k大于2。通過插入操作，使得各序列達到一樣的長度。多序列比對的目的發(fā)現(xiàn)多個序列的共性發(fā)現(xiàn)與結(jié)構(gòu)和功能相關(guān)的保守序列片段多序列比對的應(yīng)用研究蛋白質(zhì)之間的關(guān)系研究一個家族中的相關(guān)蛋白質(zhì)研究相關(guān)蛋白質(zhì)的保守區(qū)域研究蛋白

44、質(zhì)的結(jié)構(gòu)和功能進行蛋白質(zhì)結(jié)構(gòu)預(yù)測推測各個序列的進化歷史1、SP（Sum-of-Pairs）模型）模型評價多重序列比對的結(jié)果評價多重序列比對的結(jié)果按照每個對比的列進行打分，然后加和按照每個對比的列進行打分，然后加和(P106)處理每一列：處理每一列： k個變量的打分函數(shù)個變量的打分函數(shù) 用一個用一個k維數(shù)組來表示該顯式函數(shù)（類似于打分矩陣）維數(shù)組來表示該顯式函數(shù)（類似于打分矩陣）期望：期望：函數(shù)在形式上應(yīng)該簡單函數(shù)在形式上應(yīng)該簡單具有統(tǒng)一的形式具有統(tǒng)一的形式不隨序列的個數(shù)而發(fā)生形式變化不隨序列的個數(shù)而發(fā)生形式變化 11121),(),.,(kikijjikccpcccscoreSP其中，c1,c

45、2,ck是一列中的k個字符，p是關(guān)于一對字符相似性的打分函數(shù)。逐對加和逐對加和SP（sum-of-pairs）函數(shù)）函數(shù)(P106) 26GSGPALLscoreSP逐對計算逐對計算p(1,2)，p (1,3)，.，p(1,8)，p (2,3)，p(2,4)，.， p (2,8)，.，p (7,8) 的所有得分的所有得分（-7-6-5-4-3-2-1）+2 = -26 另一種計算方式：先處理每一個序列對另一種計算方式：先處理每一個序列對在處理序列對時，逐個計算字符對，最后加和在處理序列對時，逐個計算字符對，最后加和則則SP得分模型的計算公式如下：得分模型的計算公式如下：jiijscoreSP)

46、( 是一個多重比對是一個多重比對 ij是由是由 推演出來的序列推演出來的序列s i 和和s j的兩兩比對的兩兩比對 2、多重比對的動態(tài)規(guī)劃算法、多重比對的動態(tài)規(guī)劃算法多重序列比對的最終目標(biāo)是得到一個得分最高多重序列比對的最終目標(biāo)是得到一個得分最高（或代價最小）的序列對比排列，從而分析各（或代價最小）的序列對比排列，從而分析各序列之間的相似性和差異序列之間的相似性和差異。前趨節(jié)點的個數(shù)等于前趨節(jié)點的個數(shù)等于2k - 1 )(),(jjjkjjisccbisColumn假設(shè)以k維數(shù)組A存放超晶格，則計算過程如下： a 0, 0, ,0 = 0 a i = max a i - b + SP-scor

47、e(Column(s, i, b) (3-37)(3-38) if bj = 1if bj = 0多序列比對的過程實際是一個遞推過程，在計算每個晶格節(jié)點得分的時候，將其各前趨節(jié)點的值分別加上從前趨節(jié)點到當(dāng)前點的SP得分，然后取最大值作為當(dāng)前節(jié)點的值。計算量問題對于k條序列的比對，動態(tài)規(guī)劃算法需要處理k維空間里的每個節(jié)點，計算量與晶格中的節(jié)點數(shù)成正比，而節(jié)點數(shù)等于各序列長度的乘積，況且計算的每個節(jié)點依賴于前趨節(jié)點的個數(shù)，因此用動態(tài)規(guī)劃進行多重序列比對的時間復(fù)雜度為O(2k i=1,.,k si )即即O(2kNk) 利用SP模型尋找最優(yōu)多重序列比對是一個NP-完全類問題完全類問題。NP-完全問題

48、通常被認為是一些人們難以在有限的時間、空間內(nèi)對問題求出最佳解得問題，幾乎所有專家都認為不可能在多項式時間內(nèi)準確求解的問題。解決辦法1. 只求解規(guī)模比較小的問題2. 利用動態(tài)規(guī)劃、分支約束等技術(shù)減小搜索空間，提高求解問題的效率。3. 針對具體問題的特點，根據(jù)實際情況，設(shè)計實用求解算法。4. 采用近似算法或者啟發(fā)式方法，如局部搜索、模擬退火、遺傳算法等。3、 優(yōu)化計算方法（優(yōu)化計算方法（p110)標(biāo)準動態(tài)規(guī)劃算法存在的問題：標(biāo)準動態(tài)規(guī)劃算法存在的問題： 搜索搜索空間大空間大對于兩兩序列比對，最優(yōu)的路徑常常處對于兩兩序列比對，最優(yōu)的路徑常常處于對角線附近，而對于多序列比對，最于對角線附近，而對于多序

49、列比對，最優(yōu)的路徑不可能在某個平面上，而是在優(yōu)的路徑不可能在某個平面上，而是在某一個區(qū)域范圍內(nèi)。某一個區(qū)域范圍內(nèi)。利用人工智能空間搜索策略的剪枝技術(shù)，根據(jù)問題本身的特殊性將搜索空間限定在一個較小的區(qū)域范圍內(nèi)。若問題是搜索一條得分最高（或代價最小）的路徑，則在搜索時如果當(dāng)前路徑的得分低于某個下限（或累積代價已經(jīng)超過某個上限），則對當(dāng)前路徑進行剪枝，即不再搜索當(dāng)前路徑的后續(xù)空間。4、星形比對、星形比對(P112)星形比對的基本思想是：在給定的若干序列中，選擇星形比對的基本思想是：在給定的若干序列中，選擇一個核心序列，通過該序列與其它序列的兩兩比對形一個核心序列，通過該序列與其它序列的兩兩比對形成所

50、有序列的多重比對成所有序列的多重比對 ，從而使得，從而使得 在核心序列和任在核心序列和任何一個其它序列方向的投影是最優(yōu)的兩兩比對。何一個其它序列方向的投影是最優(yōu)的兩兩比對。利用標(biāo)準的動態(tài)規(guī)劃方法求出所有利用標(biāo)準的動態(tài)規(guī)劃方法求出所有si和和sc的最優(yōu)兩兩比的最優(yōu)兩兩比對對時間為時間為O（2knk）將這些兩兩比對聚集起來將這些兩兩比對聚集起來并采用并采用“只要是空位只要是空位 ， 則永遠是空位則永遠是空位”的原則。的原則。scs1s2sk(sc, s1) (sc, s2) (sc, sk)兩兩比對兩兩比對 多重比對多重比對如何選擇核心序列？嘗試將每一個序列分別作為核心序列，進行星形多重序列比對，

51、取比對結(jié)果最好的一個。另一種方法是計算所有的兩兩比對，取下式值最大的一個： sim( si, sc )例如，有5個序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACCsc=s1ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATTATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC- ATTGCCATT-ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC- 星形比對是一種近似的方法，可以證明，星形比對是一種近似的

52、方法，可以證明，用該方法所得到多重序列比對的代價不會用該方法所得到多重序列比對的代價不會大于最優(yōu)多重序列比對代價的兩倍大于最優(yōu)多重序列比對代價的兩倍 5、樹形比對、樹形比對k個待比對的序列個待比對的序列 具有具有k個葉節(jié)點的樹個葉節(jié)點的樹每個葉節(jié)點對應(yīng)一個序列每個葉節(jié)點對應(yīng)一個序列 將序列賦予樹的內(nèi)部節(jié)點，可以計算樹中每個分支的權(quán)值。將序列賦予樹的內(nèi)部節(jié)點，可以計算樹中每個分支的權(quán)值。權(quán)值代表對應(yīng)分支連接的兩個序列之間的相似性。權(quán)值代表對應(yīng)分支連接的兩個序列之間的相似性。所有權(quán)值的和就是這棵樹所有權(quán)值的和就是這棵樹 尋找一種樹的內(nèi)部節(jié)點序列賦予方式，使得樹的得分最大。尋找一種樹的內(nèi)部節(jié)點序列賦

53、予方式，使得樹的得分最大。將將CT、CG、CT分別賦予節(jié)點分別賦予節(jié)點x、y、z，則樹的得分為，則樹的得分為8。這里假設(shè)如果這里假設(shè)如果a=b，則，則p(a,b)=1， 否則否則p(a,b)=0，p(a,-)=-1。 CTCGCT多重序列比對多重序列比對 兩兩序列比對兩兩序列比對 合并兩個比對（比對的比對）合并兩個比對（比對的比對）Alignment of alignments, AA算法算法 假設(shè)假設(shè)：有兩個多重序列比對：有兩個多重序列比對 1、 2， 1代表序列代表序列s1、s2、si的多重比對，的多重比對， 2代表序列代表序列t1、t2、tj的多重比對，的多重比對，（s1，s2，si）

54、（t1，t2，tj）= 代表代表s1和和t1的兩兩比對，則計算與的兩兩比對，則計算與 相一致的相一致的 1和和 2比對的算法如下比對的算法如下 ：（1）標(biāo)定）標(biāo)定 1的各列，如果的各列，如果s1在比對中對應(yīng)位置的編輯操作不在比對中對應(yīng)位置的編輯操作不是插入或刪除，則這些列分別標(biāo)記為是插入或刪除，則這些列分別標(biāo)記為s1對應(yīng)位置上的字符對應(yīng)位置上的字符a1、a2、als1（ls1為序列為序列s1的長度）；的長度）；（2）標(biāo)定）標(biāo)定 2的各列，如果的各列，如果t1在比對中對應(yīng)的位置編輯操作不在比對中對應(yīng)的位置編輯操作不是插入或刪除，則這些列分別標(biāo)記為是插入或刪除，則這些列分別標(biāo)記為t1對應(yīng)位置上的字

55、符對應(yīng)位置上的字符b1、b2、blt1（lt1為序列為序列t1的長度）；的長度）；（3）對）對a1、a2、als1和和b1、b2、blt1進行比對；進行比對；（4）在所得到的比對中，對于）在所得到的比對中，對于 1、 2和和 中原來有插入或刪中原來有插入或刪除操作的位置，恢復(fù)其原有的實際字符或空位字符除操作的位置，恢復(fù)其原有的實際字符或空位字符“-”。例：例：1: s1 -H-LVV 2: t1 L-HCLV ：s1 -H-LVV s2 G-VLVC t2 VLHCL- t1 LHCLV- s3 GN-LVVAA算法的輸出為-H-LVV-G-VLVC-GN-LVVL-HC-LV-V-HC-L分

56、別對第1、2列和4、5列進行壓縮，則最后結(jié)果為HLVVGVLVGGNLVVLHCLV-VHCL- 對于對于n個序列的樹形比對的基本算法過程如下：個序列的樹形比對的基本算法過程如下：（1）初始化，對于每個序列，生成一個葉節(jié)點）初始化，對于每個序列，生成一個葉節(jié)點（2）利用）利用AA算法合并兩個節(jié)點，形成一個新節(jié)算法合并兩個節(jié)點，形成一個新節(jié) 點，合并的結(jié)果放在新節(jié)點中，原來的兩點，合并的結(jié)果放在新節(jié)點中，原來的兩 個節(jié)點作為新節(jié)點的子節(jié)點個節(jié)點作為新節(jié)點的子節(jié)點（3）反復(fù)執(zhí)行（）反復(fù)執(zhí)行（2），直到形成），直到形成n個葉節(jié)點的樹個葉節(jié)點的樹 根為止，根節(jié)點中的序列即為最終的多重根為止，根節(jié)點中的

57、序列即為最終的多重 比對結(jié)果。比對結(jié)果。 s1 s2 s3 s41 12 26 6、其它多重序列比對算法、其它多重序列比對算法一般漸進式比對方法所采用的過程：一般漸進式比對方法所采用的過程：（1）先將多個序列進行兩兩比對，基于這些比較，）先將多個序列進行兩兩比對，基于這些比較，計算得到一個距離矩陣，該矩陣反映每對序列的計算得到一個距離矩陣，該矩陣反映每對序列的關(guān)系；關(guān)系；（2） 利用距離矩陣，建立一棵利用距離矩陣，建立一棵“相關(guān)樹相關(guān)樹”；（3）從最接近的一對序列出發(fā)，逐步歸并形成比）從最接近的一對序列出發(fā)，逐步歸并形成比對的聚類，直到所有序列處理完。對的聚類，直到所有序列處理完。例：例：(L

58、YCES, SPIOL 84), (YEAST, (XENLA,(RAT, MOUSE 96), HUMAN 83), CHICK71) 66), DROVI 58)相關(guān)樹相關(guān)樹多序列比對多序列比對目前使用最廣泛的多重序列比對程序是ClustalW ClustalW是一種漸進的比對方法，先將多個序列進行兩兩比對，基于這些比較，計算得到一個距離矩陣，該矩陣反映了每對序列的關(guān)系 EBI的CLUSTALW網(wǎng)址是： http:/www.ebi.ac.uk/clustalw/ 7、統(tǒng)計特征分析、統(tǒng)計特征分析對于所得到的多重序列比對，我們往往需要進行歸納分析，對于所得到的多重序列比對，我們往往需要進行歸納

59、分析，總結(jié)這些序列的特征，或者給出這些序列共性的表示總結(jié)這些序列的特征，或者給出這些序列共性的表示 HLVVGVLVGGNLVVLHCLV-VHCL- （1）保守序列）保守序列表示序列每個位置上最可能出現(xiàn)的字符（或者所有可能出表示序列每個位置上最可能出現(xiàn)的字符（或者所有可能出現(xiàn)的字符）現(xiàn)的字符）ATNTSC (N - A,T,C,G ; S - G,C)（2）特征統(tǒng)計圖（）特征統(tǒng)計圖（Profile） 令令P=(P1,P2,PL)，P表示在表示在 的每一列上各的每一列上各種字符出現(xiàn)的概率分布種字符出現(xiàn)的概率分布Pj=(pj0,pj1,pj|A|)A代表字母表，代表字母表，Pjk代表字母表代表字母表A中第中第k個字符在第個字符在第 j 列出現(xiàn)的概率。列出現(xiàn)的概率。 第第0個字符是特殊的空位符號個字符是特殊的空位符號“-”。 ATTATAACTTCTTATACTTTAGAAT 1 2 3 4 5 (位置位置) A 0.8 0.2 0.2 0.6 0.0 T 0.0 0.4 0.6 0.4 1.0 C 0.2 0.2 0.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （堿基）（堿基）利用保守序列或者特征統(tǒng)計圖可以判斷一個序列利用保守序列或者