1、生物信息學,1,PPT學習交流,第二章 序列比對,南方醫(yī)科大學 朱浩 吉林大學 李瑛,生物信息學,2,PPT學習交流,第一節(jié) 引 言,Section 1 Introduction,3,PPT學習交流,（一） 同源,兩個序列享有一個共同的進化上的祖先，則這兩個序列是同源的。 對于兩個序列，他們或者同源或者不同源，不能說他們70%或80%同源。,、同源、相似與距離,4,PPT學習交流,同源可分為垂直同源（ortholog）和水平同源（paralog）,垂直同源與水平同源,5,PPT學習交流,（二）相似性與距離,相似性、距離：是兩個定量描述多個序列相似度的度量。 相似性：被比對序列之間的相似程度。

2、距離：被比對序列間的差異程度。 相似性既可用于全局比對也可用于局部比對，而距離一般僅用于全局比對，因為它反映了把一個序列轉換成另一個序列所需字符替換的耗費。,6,PPT學習交流,二、相似與距離的定量描述,相似性可定量地定義為兩個序列的函數(shù)，即它可有多個值，值的大小取決于兩個序列對應位置上相同字符的個數(shù)，值越大則表示兩個序列越相似。 編輯距離（edit distance）也可定量地定義為兩個序列的函數(shù)，其值取決于兩個序列對應位置上差異字符的個數(shù)，值越小則表示兩個序列越相似。,7,PPT學習交流,對于一個比對，不論使用什么計分函數(shù)進行計分，相似性被定義為總等值于最大的計分：,對于k個序列，如果用一

3、個函數(shù)cost（）對每一列的所有替換操作進行計分，則多個序列之間的距離等值于最小的計分：,8,PPT學習交流,對相似性的計分,9,PPT學習交流,編輯距離（edit distance）：一般用海明距離表示。,10,PPT學習交流,三、算法實現(xiàn)的比對,用計算機科學的術語來說，比對兩個序列就是找出兩個序列的最長公共子序列（longest common subsequence，LCS），它反映了兩個序列的最高相似度。,11,PPT學習交流,動態(tài)規(guī)劃法示意,（A）使用動態(tài)規(guī)劃法尋找兩個序列的最長公共部分； （B）動態(tài)規(guī)劃表的填寫。,12,PPT學習交流,四、序列比對的作用,獲得共性序列 序列測序 突變

4、分析 種系分析 保守區(qū)段分析 基因和蛋白質功能分析,13,PPT學習交流,第二節(jié) 比對算法概要,Section 2 Alignment Algorithms,14,PPT學習交流,（一）通過點矩陣對序列比較進行計分,A.兩條序列完全相同,一、替換計分矩陣,15,PPT學習交流,B.兩條序列有一個共同的子序列,16,PPT學習交流,C.兩條序列反向匹配,17,PPT學習交流,D.兩條序列存在不連續(xù)的兩條子序列,18,PPT學習交流,（二）DNA序列比對的替換計分矩陣,等價矩陣（unitary matrix）,轉換-顛換矩陣（transition-transversion matrix）,BLAS

5、T矩陣,19,PPT學習交流,核苷酸轉換矩陣,20,PPT學習交流,（三）蛋白質序列比對的替換計分矩陣,等價矩陣 遺傳密碼矩陣（GCM） 疏水性矩陣（hydrophobic matrix ） PAM矩陣 BLOSUM矩陣,21,PPT學習交流,PAM矩陣是從蛋白質序列的全局比對結果推導出來的，而BLOSUM 矩陣則是從蛋白質序列塊（短序列）比對推導出來的。,PAM/BLOSUM矩陣編號與序列親緣關系的比較,22,PPT學習交流,二、雙序列全局比對,動態(tài)規(guī)劃算法的思想, a, b是使用某一字符集的序列（DNA 或蛋白質序列）； m = a的長度； n = b的長度； S（i,j） 是按照某替換計

6、分矩陣得到的前綴a1.i與b1.j最大相似性得分；,23,PPT學習交流, w（c,d）是字符c和d按照替換計分矩陣計算的得分。 可按照規(guī)則建立得分矩陣： S（i,0） = 0, 0 i m S（0,j） = 0, 0 j n,S（i-1,j-1）+ w（ai,bj） 匹配或錯配 S（i,j）=max S（i-1,j）+ w（ai,-） 插入 S（i,j-1） 缺失不罰分,24,PPT學習交流,例如，對于序列a=ACACACTA，序列b=AGCACACA，計分規(guī)則w（匹配）=+2；w（a,-）=w（-,b）=w（失配）=-1,25,PPT學習交流,得分矩陣,26,PPT學習交流,三、雙序列局部

7、比對,處理子序列與完整序列（或短序列與長序列）比對的一般過程是：設短序列a和長序列b，它們的長度分別為La和Lb，比對是在b序列中尋找La長度的a序列的過程。,27,PPT學習交流,四、多序列全局比對,多序列比對主要涉及四個要素： 選擇一組能進行比對的序列（要求是同源序列）； 選擇一個實現(xiàn)比對與計分的算法與軟件； 確定軟件的參數(shù)； 合理地解釋比對的結果；,與雙序列比對一樣，多序列比對也有全局比對和局部比對。,28,PPT學習交流,（一）動態(tài)規(guī)劃法進行多序列比對,（A）計算三個序列間的一個比對單元（i,j,k）依賴于其7個前導項； （B）計算u=ATGTTAT，v=ATCGTAC，w=ATGC三

8、序列比對的三維得分矩陣。,計算三序列比對,29,PPT學習交流,（二）漸進多序列比對,三個序列的配對比對未必能組合成一個多序列比對,30,PPT學習交流,對于接近或超過100個序列的多序列比對，漸進多序列比對具有較高效率。最流行的漸進多序列比對軟件是Clustal家族。,31,PPT學習交流,ClustalW有以下特點： 首先，在比對中對每個序列賦予一個特殊的權值以降低高度近似序列的影響和提高相距遙遠的序列的影響（如下圖）。,ClustalW中對序列賦權的方法,32,PPT學習交流,其次，根據(jù)序列間進化距離的離異度（divergence）在比對的不同階段使用不同的氨基酸替換矩陣； 第三，采用了

9、與特定氨基酸相關的空缺（gap）罰分函數(shù)，對親水性氨基酸區(qū)域中的空缺予以較低的罰分； 第四，對在早期配對比對中產(chǎn)生空缺的位置進行較少的罰分，對引入空缺和擴展空缺進行不同的罰分。,33,PPT學習交流,迭代法 基于一致性的方法 遺傳算法,其他多序列全局比對方法,34,PPT學習交流,五、多序列局部比對,全局比對，其共同特征是序列中所有對應字符均假定可以匹配，所有字符具有同等的重要性，空格的插入是為了使整個序列得到比對，包括使兩端對齊。 局部比對不假定整個序列可以匹配，重在考慮序列中能夠高度匹配的一個區(qū)段，可賦予該區(qū)段更大的計分權值，空格的插入是為了使高度匹配的區(qū)段得到更好的比對。,35,PPT學

10、習交流,對2個序列進行全局和局部比對可得到完全不同的結果,36,PPT學習交流,基于隱馬爾可夫模型的多序列比對方法,隱馬爾可夫模型和3個蛋白質序列PHSFTYVMT、PGSFTYW、RFTGFW的最小公共超圖,37,PPT學習交流,六、比對的統(tǒng)計顯著性,確定比對得分score是否偶然： 1.將球蛋白或肌球蛋白與大量非同源的蛋白質做比對，然后將score與這些比對的得分進行比較。 2.把一個序列與一組隨機產(chǎn)生的序列進行比對，然后同樣將score與這些比對的得分進行比較。 3.隨機將兩個序列中的一個打亂重組，比如說重組100次，并與另一個序列比對，同樣得到一組比對的得分。,38,PPT學習交流,第

11、三節(jié) 數(shù)據(jù)庫搜索,Section 3 Database Search,39,PPT學習交流,一、經(jīng)典BLAST,基本的BLAST算法本身很簡單，它的要點是片段對（segment pair）的概念，它是指兩個給定序列中的一對子序列，它們的長度相等，且可以形成無空格的完全匹配。,40,PPT學習交流,BLAST的查詢序列和數(shù)據(jù)庫的類型,41,PPT學習交流,BLAST算法圖示,42,PPT學習交流,二、衍生BLAST,（一）PSI-BLAST 主要用于搜索與感興趣的蛋白質關系較遠的蛋白質。,（二）PHI-BLAST 用來幫助判斷這個蛋白質屬于哪個家族。,（三）BLASTZ BLASTZ是在比對人和

12、鼠的基因組中發(fā)展起來的，它適合于比對非常長的序列。,43,PPT學習交流,三、BLAT,BLAT（The BLAST-Like Alignment Tool）與BLAST搜索原理相似，但發(fā)展了一些專門針對全基因組分析的技術。 BLAT的優(yōu)點在于速度快，其比對速度要比BLAST快幾百倍，其根本原因在于: BLAST是將查詢序列索引化，而BLAT則是將搜索數(shù)據(jù)庫索引化，BLAT 把相關的呈共線性的比對結果連接成為更大的比對結果。,44,PPT學習交流,四、RNA序列搜索,RNA序列比對/搜索算法可大致分成兩類：, 查詢序列（query）的結構未知，要找到數(shù)據(jù)庫中和其結構相近的同源序列。,45,PP

13、T學習交流, 利用查詢序列的結構信息，在結構信息的使用上又可以細分為： 通過構建一個描述RNA序列共性結構的概率模型進行數(shù)據(jù)庫檢索； 基于索引（index）或者模體（motif）描述的方法定義rna結構或共性結構，并進行數(shù)據(jù)庫搜索。,46,PPT學習交流,五、數(shù)據(jù)庫搜索的統(tǒng)計顯著性,一個典型的BLAST搜索的輸出包括E值和得分，后者又分原始得分（raw scores）和比特得分（bit scores）。,P=1-e-E,P值和E值是反映比對顯著性的兩種不同方式，大部分BLAST在線服務使用E值而非P值來定義搜索的統(tǒng)計學顯著性。,47,PPT學習交流,第四節(jié) 比對軟件、參數(shù)與數(shù)據(jù)資源,Secti

14、on 4 Alignment Software， Parameter and Resource,48,PPT學習交流,一、參數(shù)選擇的一般原則,空格罰分涉及幾個問題： 空格罰分是否大于失配罰分； 不同大小空缺的罰分； 空格的引入與延伸是否予以不同罰分。,49,PPT學習交流,如果一次數(shù)據(jù)庫搜索產(chǎn)生了太多的返回結果，可采取如下措施： 使用參考序列（帶“refseq”的）數(shù)據(jù)庫，這樣可減少許多冗余結果； 使查詢序列只包含一個結構域，減少多結構域帶來的多匹配； 根據(jù)查詢序列與數(shù)據(jù)庫序列的關系使用更合適的替換計分矩陣； 降低E值。,50,PPT學習交流,如果一次數(shù)據(jù)庫搜索產(chǎn)生了太少的返回結果，可采取如下

15、措施： 提高E值； 使用更大的PAM矩陣或更小的BLOSUM矩陣； 減小字長以及減小閾值。,51,PPT學習交流,二、主要比對軟件,52,PPT學習交流,三、EBI中的序列比對工具,53,PPT學習交流,四、UCSC中的BLAT比對工具,BLAT在線工具 輸入界面,54,PPT學習交流,BLAT在線工具 輸出結果,55,PPT學習交流,第五節(jié) 比對技術的發(fā)展,Section 5 Advances of Alignment Techniques,56,PPT學習交流,一、glocal 比對,兩個序列的局部、全局和glocal比對所對應的路徑,57,PPT學習交流,二、全基因組比對,全基因組比對主要揭示多個序列中保守的和非保守的區(qū)段以及這些區(qū)段在基因組中的分布特征，這里主要介紹UCSC基因組瀏覽器（The UCSC Genome Browser）中的全基因組比對方法。,58,PPT學習交流,UCSC基因組瀏覽器中所采用的多序列比對在多方面作了改進,首先，它采用了參照序列（reference sequence），使用BLASTZ將每一個序列與參照序列進行局部配對比對，參照序列中的一個堿基比對另一個序列中的至多一個堿基。 其次，依據(jù)計分矩陣和兩序列的種系關系，對配對比對的結果進行所謂的“串連”（chaining）和“連網(wǎng)”（netting）。 接著，U