1、第五章 序列比對,2020/9/16,BIOINFORMATICS,1,本章提要：介紹了序列相似性的概念，列舉了描述DNA和蛋白質序列相似性的計分矩陣。介紹了序列比較的基本操作“比對”的概念，以雙序列比對為例詳細學習了序列整體比對的Needleman-Wunsch算法，序列局部比對的Smith-Waterman算法。介紹了多序列比對的概念，簡要介紹了幾種多序列比對的算法，學習了一個常用的多序列比對軟件ClustalW的使用和用途。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,2,序列比較是生物信息學中最基本、最重要的操作，通過序列比較可以發(fā)現生物序列中的功能、結構和進

2、化的信息。序列比較的根本任務是：通過比較生物分子序列，發(fā)現它們的相似性，找出序列之間共同的區(qū)域，同時辨別序列之間的差異。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,3,在分子生物學中，DNA或蛋白質的相似性是多方面的，可能是核酸或氨基酸序列的相似，可能是結構的相似，也可能是功能的相似。研究序列相似性的目的之一是，通過相似的序列得到相似的結構或相似的功能。通過比較未知序列與已知序列（尤其是功能和結構已知的序列）之間的相似性，可以很容易地預測未知序列的功能。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,4,這種方法在大多數情況下是成功的，當然，

3、也存在著這樣的情況，即兩條序列幾乎沒有相似之處，但分子卻折疊成相同的空間形狀，并具有相同的功能。這里先不考慮空間結構或功能的相似性，僅研究序列的相似性。研究序列相似性的另一個目的是通過序列的相似性，判別序列之間的同源性，推測序列之間的進化關系。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,5,序列比較可以分為4種情況： (1)、假設有兩條長度相近的、來自同一個字母表的序列，它們之間非常相似，僅僅有一些細微的差別，例如字符的插入、字符的刪除和字符替換，要求找出這兩條序列的差別。這種操作實際應用比較多，例如，有兩個實驗室同時測定某個基因的DNA序列，其結果可能不一樣，需要

4、通過序列比較來比較實驗結果。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,6,(2)、假設有兩條序列，要求判斷是否有一條序列的前綴與另一條序列的后綴相似，如果是，則分別取出前綴和后綴。該操作常用于大規(guī)模DNA測序中序列片段的組裝。 (3)、假設有兩條序列，要求判斷其中的一條序列是否是另一條序列的子序列。這種操作常用于搜索特定的序列模式。 (4)、假設有兩條序列，要求判斷這兩條序列中是否有非常相似的子序列。這種操作可用于分析保守序列。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,7,當然，進行序列比較時，往往還需要說明是采取全局比較，還是采取局

5、部比較。全局比較是比較兩條完整的序列，而局部比較是找出最大相似的子序列。 本章著重介紹通用的序列比較方法。了解序列比較的原理對于正確、合理、靈活地使用相關生物信息學資源和軟件有重要的指導意義。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,8,5.1序列的相似性,5.1.1 幾個基本概念,序列的相似性可以是定量的數值，也可以是定性的描述。相似度是一個數值，反映兩條序列的相似程度。關于兩條序列之間的關系，有許多名詞，如相同、相似、同源、同功、直系同源、并系同源等。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,9,在很多時候，往往通過一個簡單序列相

6、似性的比較就可以對未知序列進行初步的功能預測，為后續(xù)實驗確定初步的研究方向。本節(jié)將主要講述如何采用生物信息學技術對核酸序列進行較為全面的分析。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,10,在進行序列比較時經常使用“同源”(homology )和“相似”(similarity)這兩個概念，這是兩個經常容易被混淆的不同概念。兩條序列同源是指它們具有共同的祖先。在這個意義上，無所謂同源的程度，兩條序列要么同源，要么不同源。而相似則是有程度的差別，如兩條序列的相似程度達到30或60。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,11,一般來說，

7、相似性很高的兩條序列往往具有同源關系；但也有例外，即兩條序列的相似性很高，但它們可能并不是同源序列，這兩條序列的相似性可能是由隨機因素所產生的，這在進化上稱為“趨同”（convergence)，這樣一對序列可稱為同功序列。直系同源(orthologous)序列是來自于不同種屬的同源序列，而并系同源(paralogous)序列則是來自于同一種屬的序列，它是由進化過程中的序列復制而產生的。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,12,5.1.2 點標方法分析兩序列間的相似性,點標（dot plot）是兩序列對位排列中最基本也是最直觀的方法。設序列A和B的長度不同，但

8、很接近。我們可以用二維坐標來標定每個位點上的對位情況。如圖5-1所示，序列A為X軸，序列B為Y軸。如AiBj,，坐標(i, j)處賦值為“*”，其余賦值為“空白”。逐個比較所有的字符對，最終形成點陣列。,圖5-1 序列比對的點陣圖方式,2020/9/16,BIOINFORMATICS,數理與生物工程學院,14,顯然，如果兩條序列完全相同，則在點矩陣主對角線的位置都有標記；如果兩條序列存在相同的子串，則對于每一個相同的子串對，有一條與對角線平行的由標記點所組成的斜線，如圖5.2中的斜線代表相同的子串“ATCC；而對于兩條互為反向的序列，則在反對角線方向上有標記點組成的斜線，如圖5.3所示。,圖5

9、-2 相同子串點陣圖,圖5-3 反向序列點陣圖,圖5-4 多個相同連續(xù)子串序列的點陣圖,2020/9/16,BIOINFORMATICS,數理與生物工程學院,18,除非已經知道待比較的序列非常相似，一般先用點矩陣方法比較，因為這種方法可以通過觀察陣列的對角線迅速發(fā)現可能的序列比對。 兩條序列中有很多匹配的字符對，因而在點矩陣中會形成很多點標記。當對比較長的序列進行比較時，這樣的點陣圖很快會變得非常復雜和模糊。使用滑動窗口代替一次一個位點的比較是解決這個問題的有效方法。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,19,假設窗口大小為10，相似度閾值為8。首先，將X軸序

10、列的第110個字符與Y軸序列的第110個字符進行比較。如果在第一次比較中，這10個字符中有8個或者8個以上相同，那么就在點陣空間(1，1)的位置畫上點標記。然后窗口沿X軸向右移動一個字符的位置，比較X軸序列的第2 11個字符與Y軸序列的第110個字符。不斷重復這個過程，直到X軸上所有長度為10的子串都與Y軸第110個字符組成的子串比較過為止。 然后，將Y軸的窗口向上移動一個字符的位置，重復以上過程，直到兩條序列中所有長度為10的子串都被兩兩比較過為止?；诨瑒哟翱诘狞c矩陣方法可以明顯地降低點陣圖的噪聲，并且可以明確地指出兩條序列間具有顯著相似性的區(qū)域。,2020/9/16,BIOINFORMA

11、TICS,數理與生物工程學院,20,以上討論了如何利用單元矩陣來構建點陣圖。更加復雜的點陣圖可基于不同的計分規(guī)則而構建。這些計分規(guī)則規(guī)定了不同殘基之間相似性程度的分值。例如，可以根據不同殘基之間在進化關系、空間結構、理化性質等方面的相似性來規(guī)定它們之間的相似性分數值。在這種情況下，由于點陣圖不只是簡單的稀疏矩陣，那些非主對角線點的信號和噪聲同時得到放大，所以噪聲過濾就變得十分重要。常用的方法是引入滑動窗口作為平滑函數提高點陣圖的信噪比。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,21,5.1.3 描述相似性的記分矩陣,如果序列比較僅僅取決于序列間嚴格一致的區(qū)域，那么

12、我們可以將其轉化為一種極為簡單的程序。然而，大多數序列對位排列不是僅僅限制在子序列的范圍內，而是涉及全長序列的比較。有時，也不能簡單理解為如何減少間隔的數目，而要同時考慮對位排列后序列的生物學意義。例如，某些氨基酸有時應放在非嚴格一致的位置。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,22,記分矩陣方法(scoring matrix)被廣泛應用于評價序列對位排列的質量。通常使用得分()、無分(0)或罰分(-)來進行綜合評價?？紤]未匹配和間隔的罰分以及權重不均衡等因素，記分矩陣就更加復雜。人們已提出各種各樣的記分矩陣來進行不同目的序列對位排列。,2020/9/16,B

13、IOINFORMATICS,數理與生物工程學院,23,不同類型的字符替換，其代價或得分是不一樣的，特別是對于蛋白質序列。某些氨基酸可以很容易地相互取代而不用改變它們的理化性質。例如，考慮這樣兩條蛋白質序列，其中一條在某一位置上是丙氨酸，如果該位點被替換成另一個較小且疏水的氨基酸，比如纈氨酸，那么對蛋白質功能的影響可能較?。蝗绻惶鎿Q成較大且?guī)щ姷臍埢?，比如賴氨酸，那么對蛋白質功能的影響可能就要比前者大。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,24,直觀地講，比較保守的替換比起較隨機替換更可能維持蛋白質的功能，且更不容易被淘汰。因此，在為比對打分時，我們可能更傾向

14、對丙氨酸與纈氨酸的比對位點給予一定的獎勵，而對于丙氨酸與那些大而帶電氨基酸（比如賴氨酸）的比對位點則相反。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,25,理化性質相近的氨基酸殘基之間替換的代價顯然應該比理化性質相差甚遠的氨基酸殘基替換得分高，或者代價小。同樣，保守的氨基酸替換得分應該高于非保守的氨基酸替換。這樣的打分方法在比對非常相近的序列以及差異極大的序列時，會得出不同的分值。這就是提出得分矩陣(或者稱為取代矩陣）的原由。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,26,在得分矩陣中，詳細地列出各種字符替換的得分，從而使得計算序列之間

15、的相似度更為合理。在比較蛋白質時，我們可以用得分矩陣來增強序列比對的敏感性。得分矩陣是序列比較的基礎，選擇不同的得分矩陣將得到不同的比較結果，而了解得分矩陣的理論依據將有助于在實際應用中選擇合適的得分矩陣。以下介紹一些常用的得分矩陣或代價矩陣。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,27,5.1.3.1 核酸得分矩陣,設核酸序列所用的字母表為A=A,C,G,T。 (1) 等價矩陣 等價矩陣(見表5-1)是最簡單的一種得分矩陣，其中，相同核苷酸匹配的得分為“1”，而不同核苷酸的替換得分為“0”（沒有得分）。,2020/9/16,BIOINFORMATICS,28,

16、表5-1 等價矩陣,2020/9/16,BIOINFORMATICS,29,(2) BLAST矩陣 BLAST是目前最流行的核酸序列比較程序，表5-2是其得分矩陣。這也是一個非常簡單的矩陣，如果被比較的兩個核苷酸相同，則得分為“5”，反之得分為“-4”。,表5-2 BLAST矩陣,2020/9/16,BIOINFORMATICS,數理與生物工程學院,30,（3）轉換顛換矩陣 核酸的堿基按照環(huán)結構分為兩類，一類是嘌呤（腺嘌呤A，鳥嘌呤G），它們有兩個環(huán)；另一類是嘧啶（胞嘧啶C，胸腺嘧啶T），它們的堿基只有一個環(huán)。如果DNA堿基的變化（堿基替換）保持環(huán)數不變，則稱為轉換( transition)，

17、如AG, CT；如果環(huán)數發(fā)生變化，則稱為顛換(transversion)，如AC, AT等。在進化過程中，轉換發(fā)生的頻率遠比顛換高，而表5-3所示的矩陣正好反映了這種情況，其中轉換的得分為“-1”，而顛換的得分為“-5”。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,31,表5-3 轉移矩陣,2020/9/16,BIOINFORMATICS,32,5.1.3.2蛋白質得分矩陣,表5-4給出了20種氨基酸的英文縮寫：,表5-4 20種氨基酸的英文縮寫,2020/9/16,BIOINFORMATICS,數理與生物工程學院,33,（1) 等價矩陣,其中，Rij代表得分矩陣元

18、素，i、j分別代表字母表第i個和第j個字符。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,34,(2) 遺傳密碼矩陣GCM GCM矩陣通過計算一個氨基酸殘基轉變到另一個氨基酸殘基所需的密碼子變化數目而得到，矩陣元素的值對應于代價。如果變化一個堿基，就可以使一個氨基酸的密碼子改變?yōu)榱硪粋€氨基酸的密碼子，則這兩個氨基酸的替換代價為1；,2020/9/16,BIOINFORMATICS,數理與生物工程學院,35,如果需要兩個堿基的改變，則替換代價為2；以此類推（見表5-5)。注意Met到Tyr的轉變是僅有的密碼子三個位置都發(fā)生變化的轉換。在表5-5中，Glx代表Gly、Gl

19、n或Glu，而Asx則代表Asn或Asp，X代表任意氨基酸。GCM矩陣常用于進化距離的計算，其優(yōu)點是計算結果可以直接用于繪制進化樹，但是它在蛋白質序列比對尤其是相似程度很低的序列比對中很少被使用。,表5-5 遺傳密碼矩陣GCM,2020/9/16,BIOINFORMATICS,數理與生物工程學院,37,(3) 疏水矩陣 該矩陣（見表5-6）是根據氨基酸殘基替換前后疏水性的變化而得到得分矩陣。若一次氨基酸替換疏水特性不發(fā)生太大的變化，則這種替換得分高，否則替換得分低。,表5-6 蛋白質疏水矩陣,2020/9/16,BIOINFORMATICS,數理與生物工程學院,39,(4) PAM矩陣 為了得

20、到得分矩陣，更常用的方法是統(tǒng)計自然界中各種氨基酸殘基的相互替換率。如果兩種特定的氨基酸之間替換發(fā)生得比較頻繁，那么這一對氨基酸在得分矩陣中的互換得分就比較高。PAM矩陣就是這樣一種得分矩陣。PAM矩陣是第一個廣泛使用的最優(yōu)矩陣，它是基于進化原理的，建立在進化的點接受突變模型PAM ( point accepted mutation)基礎上，通過統(tǒng)計相似序列比對中的各種氨基酸替換發(fā)生率而得到該矩陣。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,40,Dayhoff和她的同事們研究了71個相關蛋白質家族的1572個突變，發(fā)現蛋白質家族中氨基酸的替換并不是隨機的。由此斷言一

21、些氨基酸的替換比其他替換更容易發(fā)生，其主要原因是這些替換不會對蛋白質的結構和功能產生太大的影響。如果氨基酸的替換是隨機的，那么，每一種可能的取代頻率僅僅取決于不同氨基酸出現的背景頻率。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,41,然而，在相關蛋白質中，存在取代頻率大大地傾向于那些不影響蛋白質功能的取代。換句話說，這些點突變已經被進化所接受。這意味著，在進化歷程上，相關的蛋白質在某些位置上可以出現不同的氨基酸。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,42,一個PAM就是一個進化的變異單位，即1的氨基酸改變。但是，這并不意味著經過10

22、0次PAM后，每個氨基酸都發(fā)生變化，因為其中一些位置可能會經過多次改變，甚至可能變回到原先的氨基酸。因此，另外一些氨基酸可能不發(fā)生改變。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,43,PAM有一系列的替換矩陣，每個矩陣用于比較具有特定進化距離的兩條序列。例如，PAM-120矩陣用于比較相距120個PAM單位的序列。一個PAM-N矩陣元素（,j)的值反映兩條相距N個PAM單位的序列中第i種氨基酸替換第j種氨基酸的概率。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,44,從理論上講，PAM-0是一個單位矩陣，主對角線上的元素值為1，其他矩陣元

23、素的值為0。其他PAM-N矩陣可以通過統(tǒng)計計算而得到。首先針對那些確信是相距一個PAM單位的序列進行統(tǒng)計分析，得到PAM-1矩陣。PAM-1矩陣對角線上的元素值接近于1，而其他矩陣元素值接近于0。例如，可以按下述方法構建PAM-1矩陣。首先，構建一個序列間相似度很高（通常大于85）的比對。接著，計算每個氨基酸j的相對突變率mj。相對突變率就是某種氨基酸被其他任意氨基酸替換的次數。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,45,比如，丙氨酸的相對突變率是通過計算丙氨酸與非丙氨酸殘基比對的次數來得到。然后，針對每個氨基酸對i和j，計算氨基酸j被氨基酸i替換的次數。最后

24、，將以上替換次數除以對應的相對替換率，利用每個氨基酸出現的頻度對其進行標準化，并將以上計算結果取常用對數，于是得到了PAM-1矩陣中的元素PAM-1(i , j )。這種矩陣被稱作對數幾率矩陣（log odds matrix），因為其中的元素是根據每個氨基酸替換率的對數值來得到的。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,46,將PAM-1自乘N次，可以得到矩陣PAM-N。雖然Dayhoff等人只發(fā)表了PAM-250，但潛在的突變數據可以外推至其他PAM值，產生一組矩陣?？梢愿鶕容^序列的長度以及序列間的先驗相似程度來選用特定的PAM矩陣，以發(fā)現最適合的序列比對

25、。一般，在比較差異極大的序列時，通常在較高的PAM值處得到最佳結果，比如在PAM-200到PAM-250之間，而較低值的PAM矩陣一般用于高度相似的序列。實踐中用得最多的且比較折中的矩陣是PAM-250。,表5-7 Dayhoff PAM 250記分矩陣,2020/9/16,BIOINFORMATICS,數理與生物工程學院,48,(5) BLOSUM矩陣 不少情況下Dayhoff PAM記分矩陣可能失效，因為其置換速率是通過至少具有85一致性的序列對位排列所獲得的。那些進化距離較遠的矩陣是推算出來而不是直接計算得到的，其準確率受到一定限制，這就需要使用新的記分矩陣。,2020/9/16,BIO

26、INFORMATICS,數理與生物工程學院,49,BLOSUM矩陣是由Henikoff首先提出的另一種氨基酸替換矩陣，它也是通過統(tǒng)計相似蛋白質序列的替換率而得到的。PAM矩陣是從蛋白質序列的全局比對結果推導出來的，而BLOSUM矩陣則是從蛋白質序列塊（短序列）比對而推導出來的。但在評估氨基酸替換頻率時，應用了不同的策略?；緮祿碓从贐LOCKS數據庫，其中包括了局部多重比對（包含較遠的相關序列，與在PAM中使用較近的相關序列相反）。雖然在這種情況下沒有用進化模型，但它的優(yōu)點在于可以通過直接觀察而不是通過外推獲得數據。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,50

27、,同PAM模型一樣，也有一系列的BLOSUM矩陣，可以根據親緣關系的不同來選擇不同的BLOSUM矩陣進行序列比較。然而BLOSUM矩陣階數的意義與PAM矩陣正好相反。低階PAM矩陣適合用來比較親緣較近的序列，而低階BLOSUM矩陣更多是用來比較親緣較遠的序列。一般來說，BLOSUM-62矩陣適于用來比較大約具有62相似度的序列，而BLOSUM-80矩陣更適合于相似度為80左右的序列。,表5-8 BLOSUM-62矩陣,2020/9/16,BIOINFORMATICS,數理與生物工程學院,52,相似性記分矩陣的構建，是基于遠距離進化過程中觀察到的殘基替換率，并用不同的記分值表征不同殘基之間的相似

28、度。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,53,5.1.3.3 不同記分方法比較,在實際工作中，不同對位排列的優(yōu)劣可以用總分(即對核苷酸或氨基酸序列進行對位排列所獲得的分數之和)來綜合反映。不同的記分方法(模型)的特點可簡單歸納如下。 1. 基于“一致性”的記分 在這種記分方法中，僅統(tǒng)計序列位點間的一致性。匹配的位點記正分(通常為1)，非匹配的位點記0分。 優(yōu)點：簡單明了，適用于高度相似性序列。 缺點：沒有考慮非匹配位點間的不等價問題；在對相似性較低的序列進行對位排列時，效果尤差。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,54,2

29、. 基于“化學相似性”的記分方式 該方法是對一致性記分方法的局部改進。 例如，Mclachlan和Feng 等結合氨基酸的性質(如極性、電荷、大小和結構特征)，對不同氨基酸進行了加權。 優(yōu)點：考慮了氨基酸和蛋白質的結構與性質。例如，一個氨基酸從極性到非極性的改變對蛋白質的結構與功能的影響，可能比具有相似性質的氨基酸間的突變要顯著一些。 缺點：并非所有蛋白質的結構與功能的改變都可以用簡單的記分描述。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,55,3. 基于“遺傳密碼”的記分 該方法考慮到當一個氨基酸轉換成另一個氨基酸時，在基因組水平上堿基變化的最小數目。 優(yōu)點：具有

30、分子生物學基礎。 缺點：考慮隨機因素較少。例如，堿基變化數目并非總是與氨基酸序列間的相似性相對應。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,56,4. 基于“觀察突變”的記分 該方法考慮了對位排列序列中所實際觀察到的突變頻率。Dayhoff矩陣和BLOSUM矩陣就屬于這類方法。 優(yōu)點： 以自然界中真實事件為基礎。與其他記分方法相比，真實的突變頻率更有助于解釋序列間的進化關系。 缺點： 突變頻率是從已對位排列的序列中獲得的，而初始的對位排列必須人工進行，較為復雜且容易發(fā)生錯誤。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,57,5.2 雙序

31、列對位排列,5.2.1序列對位排列的基本概念,在序列檢索和分析中，經常涉及到兩條序列對位排列(sequence alignment)的問題，即通過字符匹配和替換，或者插入間隔(gap)和刪除字符的方法使不同長度的序列對齊，達到長度一致。優(yōu)化的對位排列應使間隔的數目最小，同時序列間相似性區(qū)域最大。序列的比對是一種關于序列相似性的定性描述，它反映在什么部位兩條序列相似，在什么部位兩條序列存在差別。最優(yōu)比對揭示兩條序列的最大相似程度，指出序列之間的根本差異。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,58,例如，對序列XCGATCAG(長度為7)和序列YCGTCAG(長度

32、為6)，只需插入一個間隔即可。對位排列后的兩個序列為： X：CGATCAG Y：CG TCAG 下面就不同類型的編輯操作定義函數w，它表示“代價(cost)”或“權重(weight)”。 對字母表A中的任意字符a、b，定義：,(5-1),2020/9/16,BIOINFORMATICS,數理與生物工程學院,59,這是一種簡單的代價定義，在實際應用中還需使用更復雜的代價模型。一方面，可以改變各編輯操作的代價值，例如，在蛋白質序列比較時，用理化性質相近的氨基酸進行替換的代價應該比完全不同的氨基酸替換代價?。涣硪环矫?，也可以使用得分（score）函數來評價編輯操作。下面給出一種基本的得分函數：,(5

33、-2),2020/9/16,BIOINFORMATICS,數理與生物工程學院,60,在進行序列比對時，可根據實際情況選用代價函數或得分函數，即選用式（5-1)或式（5-2）。 下面給出在進行序列比對時常用的概念。 (1)、兩條序列s和t的比對的得分（或代價）等于將s轉化為t所用的所有編輯操作的得分（或代價）總和； (2)、s和t的最優(yōu)比對是所有可能的比對中得分最高（或代價最?。┑囊粋€比對；,2020/9/16,BIOINFORMATICS,數理與生物工程學院,61,(3）、s和t的真實距離應該是在得分函數p值（或代價函數w值）最優(yōu)時的距離。 使用前面代價函數w的定義，可以得到下列比對的代價。,

34、2020/9/16,BIOINFORMATICS,數理與生物工程學院,62,而使用得分函數p的定義，可以得到下列比對的得分。,進行序列比對的目的是尋找一個得分最高（或代價最?。┑谋葘Α?2020/9/16,BIOINFORMATICS,數理與生物工程學院,63,序列對位排列中，有時要用到子序列(sub-sequence)的概念。例如，序列A含200個堿基，序列B含500個堿基。如果整個序列A與序列B的一部分完全一致，則稱A為B的子序列。圖5-5(a)示出了對A和B進行對位排列的簡單方法。 如果A有兩個區(qū)域分別與B一致，則需要將A分為兩部分圖5-5(b)，兩端和中間分別插入間隔即可。,2020/

35、9/16,BIOINFORMATICS,數理與生物工程學院,64,圖5-5 子序列與比對排列,顯然，隨著所比較的序列數目和長度的增加，序列比對排列的工作將變得愈來愈困難。因而，有關的數學方法和計算機程序已成為比對排列所不可缺少的手段。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,65,5.2.2 局部相似性和整體相似性,從上面的介紹中可以看出，序列比對基于某個數學模型，模型的參數可以加以調節(jié)。不同模型所反映的生物學性質不同。例如，可以根據分子結構、功能和進化等方面的相關性來進行構建。必須指出，比對結果沒有正確和錯誤之分，其區(qū)別是由于模型所反映的生物學性質不同。,202

36、0/9/16,BIOINFORMATICS,數理與生物工程學院,66,總體來說，比對模型可以分為兩類：一類是考察兩個序列之間的整體相似性，稱全局性比對；另一類則著眼于序列中的某些特殊片段，比較這些片段之間的相似性，即局部性比對。搞清這兩類相似性和這兩種不同比對方法之間的區(qū)別，對于正確選擇使用哪種比對方法十分重要。應該指出，在實際應用中，用整體比對方法企圖找出只有局部相似性的兩個序列之間的關系，顯然是徒勞的；而用局部比對得到的局部相似性結果不能說明這兩個序列的三維結構或折疊方式是否相同。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,67,目前常用的BLAST和FastA

37、等數據庫搜索程序均采用局部相似性比對方法，具有較快的運行速度，采用某些優(yōu)化算法可進一步提高速度。局部相似性搜索主要用于找出序列中的功能位點，如酶的催化位點等。它們通常只有一個或幾個殘基，具有較高的保守性，并且不受序列中其他部分的插入和突變的影響。從這個意義上說，局部相似性搜索比整體相似性比對更加靈敏，也更具有生物學意義。需要特別指出，那些具有一定相似性的序列片段不一定具有相同的三維結構。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,68,5.2.3 整體比對算法,在對上述基本概念有所了解后，我們開始討論整體比對的Needleman和Wunsch算法。從本質上講，這一算

38、法和已經廣為使用的點陣圖方法類似。整體比對方法中，兩條蛋白質序列具有最多匹配殘基定義為最佳匹配，其中允許進行必要的插入或缺失。為控制無限制的空位插入，我們引入罰分(penalty)概念。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,69,與點陣圖類似，整體比對基于一個二維矩陣，并通過某種算法找出最佳匹配路徑。矩陣的最基本形式是： 將兩序列中匹配殘基所對應單元的值置為1，不匹配的值置為0。然后對矩陣中每個單元進行連續(xù)求和，即把能夠到達該位置的所有單元中最大值與該位置的值相加。 若令當前位置為第i行、第j列，那么能夠達到它的單元為 (I) 第i+1行中的第j個單元之后的所

39、有單元 (ii) 第j+1列中的第i個單元之后的所有單元。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,70,對矩陣的所有單元都重復這一操作，直到全部結束為止。這樣，可以構建一條最大匹配路徑，它由N末端具有最大值的單元格開始，按照取最大值的原則一直到C末端，即從序列的起始開始到最后一個殘基為止。不在主對角線上的單元格表示需要在此插入空位。在允許空位插入的情況下，可以借此來尋求最大比對。假如不允許空位插入，則只能找一條分值較低的路徑。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,71,例5-1 對兩個核酸序列ACACACTA和AGCACACA進

40、行全局比對;將兩序列中匹配殘基所對應單元的值置為1，不匹配的值置為0。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,72,對矩陣中每個單元進行連續(xù)求和，即把能夠到達該位置的所有單元中最大值與該位置的值相加。 對矩陣的所有單元都重復這一操作，直到全部結束為止。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,73,完成所有矩陣單元的分值計算后，接下來就是從最高分值單元開始找出最大分值路徑，也就是找出最佳匹配。根據上述求和過程的特性，最大分值單元一定是在序列的N一端，也就是矩陣左上角。從這一起始單元回溯，找出具有最大分值的路徑，即最佳路徑。所謂回溯，

41、就是由算法結束時的單元開始，反向查找到達到該單元所經過的路徑。最終比對結果如圖,2020/9/16,BIOINFORMATICS,數理與生物工程學院,74,矩陣起始單元的最大匹配值7，實際上就是最佳匹配路徑中相同匹配殘基的數目。,例5-2 對兩條短序列“ADLGAVFALCDRYFQ”和“ADLGRTQNCDRYYQ”進行全局比對。 根據算法，首先構建一個二維矩陣，用來表示兩個序列的匹配狀況。第一個序列沿水平方向，即x軸；第二個序列沿垂直方向，即y軸。,對矩陣中每個單元進行連續(xù)求和，即把能夠到達該位置的所有單元中最大值與該位置的值相加。對矩陣的所有單元都重復這一操作，直到全部結束為止。,202

42、0/9/16,BIOINFORMATICS,數理與生物工程學院,77,完成所有矩陣單元的分值計算后，接下來就是從最高分值單元開始找出最大分值路徑，也就是找出最佳匹配。根據上述求和過程的特性，最大分值單元一定是在序列的N一端，也就是矩陣左上角。從這一起始單元回溯，找出具有最大分值的路徑，即最佳路徑。所謂回溯，就是由算法結束時的單元開始，反向查找到達到該單元所經過的路徑。本例中，最佳路徑中間有一個間隔，可以通過在y軸方向序列中殘基N和C之間插入一個空位實現。最終比對結果如下圖所示。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,78,可見，對用1和0表示匹配和非匹配的初始分

43、數矩陣，上述連續(xù)求和得到的最大單元分值，即本例中矩陣起始單元的最大匹配值9，實際上就是最佳匹配路徑中相同匹配殘基的數目。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,79,Needleman和Wunsch算法考慮了兩個序列中所有殘基的貢獻。其最佳路徑的回溯一定從N-端開始，而每個單元的分值計算則是從C端開始。因此，這種方法稱整體性序列比對，其結果反映了兩個序列中所有殘基的整體相似性。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,80,5.2.4 局部比對算法,Needleman-Wunsch算法適用于整體水平上相似性程度較高的兩個序列。如果兩

44、個序列的親緣關系較遠，它們在整體上可能不具有相似性，但在一些較小的區(qū)域上卻可能存在局部相似性。1981年，Smith和Waterman提出了一種用來尋找并比較這些具有局部相似性區(qū)域的方法，即常用的Smith-Waterman算法。與Needleman-Wunsch算法類似，它也是一種基于矩陣的方法，而且也同樣是運用回溯法(backtracking)建立允許空位插入的比對。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,81,多年來，Smith-Waterman算法一直是序列局部比對算法的基礎，許多其他算法都是基于這一算法開發(fā)和改進的。它也經常作為比較不同比對方法的標準。

45、Smith-Waterman算法在識別局部相似性時，確實具有很高的靈敏度，但使用時要注意，它只是尋找序列中一些小的、具有局部相似性的片段，而不是序列的整體相似性。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,82,Smith-Waterman算法一個重要特性是矩陣中每個單元均可以是比對結果序列片段的終點，該片段的相似性程度由該單元中的分數值表示。 下面以例5-3為例將該算法的具體過程描述如下 ：,2020/9/16,BIOINFORMATICS,數理與生物工程學院,83,例5-3 對例5-2的兩個序列進行局部比對。 首先，矩陣最上面一行和最左邊一列前面插入一個邊界行和

46、邊界列，圖中用字符“X”表示，稱為第0行和第0列。該邊界行和邊界列所有單元的分值均為0.0。可以把這些單元理解為序列片段的起始端，其長度為0。它們的相似性分數值自然也為0。至于用小數還是整數表示，沒有實質性區(qū)別。,2020/9/16,BIOINFORMATICS,84,2020/9/16,BIOINFORMATICS,數理與生物工程學院,85,接下來計算矩陣中每個單元的計分值。與Needleman-Wunsch算法不同，Smith-Waterman算法在計算矩陣單元分值時，從左往右、從上到下，并沿對角線從左上角到右下角，而不是從下到上、從右到左。 當前單元對角線方向前一格的分值與當前單元相似性

47、數值之和，相似性數值匹配時為1.0，不匹配時為-0.333 。,2020/9/16,BIOINFORMATICS,86,2020/9/16,BIOINFORMATICS,數理與生物工程學院,87,接下來進行遞推，用兩個函數分別計算由二條路徑到達該單元的分值并找出其中的最大值，若此分值小于0，則用0替代。這兩個函數分別計算： (I) 當前行前面各分值與相應空位罰分值之差，并取最大值；所用求空位罰分值的函數為W1.0+0.333 k，k表示連續(xù)的第k個空位。 (II) 當前列前面各分值與相應的空位罰分值之差，并取最大值。如果出現負值就用0代替，表示沒有相似性比對可以延續(xù)到當前位置。,2020/9/

48、16,BIOINFORMATICS,數理與生物工程學院,89,一旦矩陣中所有單元的分值計算完畢，就可以找出具有最高分值的單元，也就是代表兩個序列間高分匹配的終點。到達這個單元的其他矩陣元素可以通過回溯方法確定。然后根據回溯路徑求得一個片段的比對。如果需要，還可以找出在上述回溯范圍以外其他具有較高分值的矩陣單元，再進行回溯，即找出多個具有較高分值的相似性片段。本例中發(fā)現有兩個區(qū)域ADLG和CDRY具有局部相似性。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,90,5.2.5 序列比對的主要用途,1. 用于系統(tǒng)發(fā)育分析 (phylogenetic analysis) 通過

49、序列比對，可以尋找序列間的同源性(相似性)，這種同源相似性是序列間進化關系的一種反映，所構建的數據矩陣成為系統(tǒng)發(fā)育分析的基礎。 2. 結構預測 (structure prediction) 將新序列與已知結構的蛋白質序列進行比對，可以通過序列同源性來粗略地推測其結構的相似性。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,91,3. 序列基序鑒定 (sequence motif identification) 局部排列可以鑒定蛋白質和核苷酸序列中潛在的序列和功能基序。 4. 功能預測（function prediction) 蛋白質序列間的高度相似性通常意味著同源序列間

50、的功能相似性。 5. 數據庫搜索(database search),2020/9/16,BIOINFORMATICS,數理與生物工程學院,92,這是序列比對很重要的一個應用。上章介紹的BLAST (basic local alignment search tool)就是一個例子。值得一提的是，手工比對因費時費力，已基本上被計算機軟件所取代。然而，某些軟件自動排列結果可能會出現一些偏差，特別是某些序列涉及復雜的生物學背景，在這種情況下，手工校正不失為一種重要的補充途徑。如果使用了手工排列，一般應在文章或報告中加以說明。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,93,

51、5.3 序列多重比對,5.3.1 多序列比對的意義,與序列兩兩比對不一樣，序列多重比對的目標是發(fā)現多條序列的共性。如果說序列兩兩比對主要用于建立兩條序列的同源關系和推測它們的結構、功能，那么，同時比對一組序列對于研究分子結構、功能及進化關系更為有用。例如，某些在生物學上有重要意義的相似性只能通過將多個序列對比排列起來才能識別。同樣，只有在多序列比對之后，才能發(fā)現與結構域或功能相關的保守序列片段。對于一系列同源蛋白質，人們希望研究隱含在蛋白質序列中的系統(tǒng)發(fā)育的關系，以便更好地理解這些蛋白質的進化。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,94,在實際研究中，生物學家

52、并不是僅僅分析單個蛋白質，而是更著重于研究蛋白質之間的關系，研究一個家族中的相關蛋白質，研究相關蛋白質序列中的保守區(qū)域，進而分析蛋白質的結構和功能。序列兩兩比對往往不能滿足這樣的需要，難以發(fā)現多個序列的共性，必須同時比對多條同源序列。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,95,多序列比對有時用來區(qū)分一組序列之間的差異；但其主要用于描述一組序列之間的相似性關系，以便對一個基因家族的特征有一個基本了解。與雙序列比對一樣，多序列比對的方法建立在某個數學或生物學模型之上。因此，正如我們不能對雙序列比對的結果得出“正確或錯誤”的簡單結論一樣，多序列比對的結果也沒有絕對正

53、確和絕對錯誤之分，而只能認為所使用的模型在多大程度上反映了序列之間的相似性關系以及它們的生物學特征。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,96,圖5-6是從多條免疫球蛋白序列中提取的8個片段的多重比對。這8個片段的多重比對揭示了保守的殘基（一個來自于二硫橋的半胱氨酸，另一個是色氨酸）、保守區(qū)域（特別是前4個片段末端的Q-PG )和其他更復雜的模式，如1位和3位的疏水殘基。多重序列比對在蛋白質結構的預測中非常有用。,圖5-6 多重序列比對,2020/9/16,BIOINFORMATICS,數理與生物工程學院,98,多重比對也能用來推測各個序列的進化歷史。從圖5-

54、6可以看出，前4條序列與后4條序列可能是從兩個不同祖先演化而來，而這兩個祖先又是由一個最原始的祖先演化得到。實際上，其中的4個片段是從免疫球蛋白的可變區(qū)域取出的，而另4個片段則從免球蛋白的恒定區(qū)域取出。當然，如果要詳細研究進化關系，還必須取更長的序列進行比對分析。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,99,可以從多個不同角度出發(fā)構建多序列比對棋型。這里，主要指建立比對模型的生物學基礎，而不僅是具體的比對方法如自動比對或手動比對等。目前，構建多序列比對模型的方法大體可以分為兩大類：第一類是基于氨基酸殘基的相似性：如物化性質、殘基之間的可突變性等；另一類方法則主要

55、利用蛋白質分子的二級結構和三級結構信息，也就是說根據序列的高級結構特征幫助確定比對結果。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,100,顯然，這兩種方法所得結果可能有很大差別。一般說來，很難斷定哪種方法所得結果一定正確，應該說，它們從不同角度反映了蛋白質序列中所包含的生物學信息。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,101,基于序列信息和基于結構信息的比對都是非常重要的比對模型，但它們都有不可避免的局限性，因為這兩種方法都不能完全反映蛋白質分子所攜帶的全部信息。我們知道，蛋白質序列是經過DNA序列轉錄翻譯得到的。從信息論角度看，

56、蛋白質序列所攜帶的信息應該比DNA分子更為“接近”實際發(fā)生的遺傳事件；而蛋白質結構除了序列本身帶來的信息外，還包括經過翻譯后加工修飾所增加的結構信息，包括殘基修飾、分子間相互作用等，最終形成穩(wěn)定的天然蛋白質結構。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,102,因此，這也是對完全基于序列數據的比對方法批評的主要原因。顯然，如果能夠利用結構數據，對于序列比對無疑有很大幫助。不幸的是，與大量的序列數據相比，實驗測得的蛋白質三維結構數據相當有限。在大多數情況下，并沒有結構數據可以利用，而只能依靠序列相似性和一些生物化學特性建立一個比較滿意的多序列比對模型。,2020/9

57、/16,BIOINFORMATICS,數理與生物工程學院,103,通過序列的多重比對，可以得到一個序列家族的序列特征。當給定一個新序列時，根據序列特征，可以判斷這個序列是否屬于該家族。對于多序列比對，現有的大多數算法都基于漸進比對的思想，在序列兩兩比對的基礎上逐步優(yōu)化多序列比對的結果。進行多序列比對后，可以對比對結果進行進一步處理，例如構建序列的特征模式、將序列聚類及構建分子進化樹等。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,104,5.3.2 多重序列比對的定義,為便于描述，可以對多序列比對過程給出下面的定義：把多序列比對看作一張二維表，表中每一行代表一個序列，

58、每一列代表一個殘基位置。將序列依照下列規(guī)則填入表中： (1)一個序列所有殘基的相對位置保持不變； (2)將不同序列間相同或相似的殘基放入同一列，即盡可能將序列間相同或相似殘基上下對齊,2020/9/16,BIOINFORMATICS,數理與生物工程學院,105,為便于敘述，可以把比對前序列中殘基的位置稱為絕對位置。如序列I第3位殘基是甘氨酸G，則絕對位置I3就是甘氨酸，而不可能是任何其他氨基酸。相應地，稱比對后序列中殘基的位置為相對位置。顯然，比對后同一列中所有殘基相對位置相同，而每個殘基的絕對位置不同，因為它們來自不同的序列。需要說明的是，絕對位置是序列本身固有的屬性，或者說是比對前的位置，

59、而相對位置則是經過比對后的位置，也就比對過程賦予它的屬性。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,106,表5-9 多序列比對的定義,表示5個短序列（IV）的比對結果。通過插入空位，使5個序列中大多數相同或相似殘基放入同一列，并保持每個序列殘基順序不變。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,107,5.3.3 調和序列,多序列比對的最終結果可以用一個調和序列（consensus sequence）表示，通常加在比對后所有序列下面。調和序列的殘基是由對應的同一列殘基歸納而得到（表5-10)。,2020/9/16,BIOINFORMATICS,數理與生物工程學院,108,調和序列只是多序列比結果的一種表示方式。還可以用權重矩陣來表示比對結果，如下面將要介紹的序列譜方法。BLOCKS數據庫則是找出比對結果中沒有空位出現的保守模塊，并把它們轉化成特異性分數矩陣；而PRINTS數據庫則用人工方法從比對結果中找出所有沒有空位的序列模體，其