1、生物信息學生物信息學第二章第二章 序列比對序列比對南方醫科大學南方醫科大學 朱浩朱浩吉林大學吉林大學 李瑛李瑛生物信息學生物信息學第一節第一節 引引 言言 Section 1 Introduction 3一一 同源同源兩個序列享有一個共同的進化上的祖先，那么這兩個序列是同源的。兩個序列享有一個共同的進化上的祖先，那么這兩個序列是同源的。對于兩個序列，他們或者同源或者不同源，不能說他們對于兩個序列，他們或者同源或者不同源，不能說他們70%或或80%同源。同源。、同源、類似與間隔、同源、類似與間隔4同源可分為垂直同源同源可分為垂直同源ortholog和程度同源和程度同源paralog垂直同源與程度

2、同源垂直同源與程度同源5二類似性與間隔二類似性與間隔類似性、間隔：是兩個定量描畫多個序列類似度的度量。類似性、間隔：是兩個定量描畫多個序列類似度的度量。類似性：被比對序列之間的類似程度。類似性：被比對序列之間的類似程度。間隔：被比對序列間的差別程度。間隔：被比對序列間的差別程度。類似性既可用于全局比對也可用于部分比對，而間隔普通僅用于全局比對，類似性既可用于全局比對也可用于部分比對，而間隔普通僅用于全局比對，由于它反映了把一個序列轉換成另一個序列所需字符交換的耗費。由于它反映了把一個序列轉換成另一個序列所需字符交換的耗費。6二、類似與間隔的定量描畫二、類似與間隔的定量描畫類似性可定量地定義為兩

3、個序列的函數，即它可有多個值，值的大小取決于類似性可定量地定義為兩個序列的函數，即它可有多個值，值的大小取決于兩個序列對應位置上一樣字符的個數，值越大那么表示兩個序列越類似。兩個序列對應位置上一樣字符的個數，值越大那么表示兩個序列越類似。編輯間隔編輯間隔edit distance也可定量地定義為兩個序列的函數，其值取決于兩也可定量地定義為兩個序列的函數，其值取決于兩個序列對應位置上差別字符的個數，值越小那么表示兩個序列越類似。個序列對應位置上差別字符的個數，值越小那么表示兩個序列越類似。7對于一個比對，不論運用什么計分函數進展計分，類似性被定義為總等值對于一個比對，不論運用什么計分函數進展計分

4、，類似性被定義為總等值于最大的計分：于最大的計分：對于對于k個序列，假設用一個函數個序列，假設用一個函數cost對每一列的一切交換操作進展計分，對每一列的一切交換操作進展計分，那么多個序列之間的間隔等值于最小的計分：那么多個序列之間的間隔等值于最小的計分：8對類似性的計分對類似性的計分9編輯間隔編輯間隔edit distance：普通用海明間隔表示。：普通用海明間隔表示。10三、算法實現的比對三、算法實現的比對用計算機科學的術語來說，比對兩個序列就是找出兩個序列的最長公共子序用計算機科學的術語來說，比對兩個序列就是找出兩個序列的最長公共子序列列longest common subsequenc

5、e，LCS，它反映了兩個序列的最高類似，它反映了兩個序列的最高類似度。度。11動態規劃法表示動態規劃法表示A運用動態規劃法尋覓兩個序列的最長公共部分；運用動態規劃法尋覓兩個序列的最長公共部分；B動態規劃表的填寫。動態規劃表的填寫。12四、序列比對的作用四、序列比對的作用獲得共性序列獲得共性序列序列測序序列測序突變分析突變分析種系分析種系分析保守區段分析保守區段分析基因和蛋白質功能分析基因和蛋白質功能分析13第二節第二節 比對算法概要比對算法概要Section 2 Alignment Algorithms14一經過點矩陣對序列比較進展計分一經過點矩陣對序列比較進展計分A.兩條序列完全一樣兩條序列

6、完全一樣一、交換計分矩陣一、交換計分矩陣15B.兩條序列有一個共同的子序列兩條序列有一個共同的子序列16C.兩條序列反向匹配兩條序列反向匹配17D.兩條序列存在不延續的兩條子序列兩條序列存在不延續的兩條子序列18二二DNADNA序列比對的交換計分矩陣序列比對的交換計分矩陣等價矩陣等價矩陣unitary matrix轉換轉換-顛換矩陣顛換矩陣transition-transversion matrixBLAST矩陣矩陣19核苷酸轉換矩陣核苷酸轉換矩陣20三蛋白質序列比對的交換計分矩陣三蛋白質序列比對的交換計分矩陣等價矩陣等價矩陣遺傳密碼矩陣遺傳密碼矩陣GCM疏水性矩陣疏水性矩陣hydrophob

7、ic matrix PAM矩陣矩陣BLOSUM矩陣矩陣21PAM矩陣是從蛋白質序列的全局比對結果推導出來的，而矩陣是從蛋白質序列的全局比對結果推導出來的，而BLOSUM 矩陣那矩陣那么是從蛋白質序列塊短序列比對推導出來的。么是從蛋白質序列塊短序列比對推導出來的。PAM/BLOSUM矩陣編號與序列親緣關系的比較矩陣編號與序列親緣關系的比較22二、雙序列全局比對二、雙序列全局比對動態規劃算法的思想動態規劃算法的思想 a, b是運用某一字符集是運用某一字符集的序列的序列DNA 或蛋白質序列；或蛋白質序列； m = a的長度；的長度； n = b的長度；的長度； Si,j 是按照某交換計分矩陣得到的前

8、綴是按照某交換計分矩陣得到的前綴a1.i與與b1.j最大類似性得分；最大類似性得分；23 wc,d是字符是字符c和和d按照交換計分矩陣計算的得分。按照交換計分矩陣計算的得分。可按照規那么建立得分矩陣：可按照規那么建立得分矩陣：Si,0 = 0, 0 i mS0,j = 0, 0 j n Si-1,j-1+ wai,bj 匹配或錯配匹配或錯配Si,j=max Si-1,j+ wai,- 插入插入 Si,j-1 缺失不罰分缺失不罰分24例如，對于序列例如，對于序列a=ACACACTA，序列，序列b=AGCACACA，計分規那么，計分規那么w匹配匹配=+2；wa,-=w-,b=w失配失配=-125得

9、分矩陣得分矩陣26三、雙序列部分比對三、雙序列部分比對處置子序列與完好序列或短序列與長序列比對的普經過程是：設短序列處置子序列與完好序列或短序列與長序列比對的普經過程是：設短序列a和長序列和長序列b，它們的長度分別為，它們的長度分別為La和和Lb，比對是在，比對是在b序列中尋覓序列中尋覓La長度的長度的a序列的過程。序列的過程。27四、多序列全局比對四、多序列全局比對多序列比對主要涉及四個要素：多序列比對主要涉及四個要素：選擇一組能進展比對的序列要求是同源序列；選擇一組能進展比對的序列要求是同源序列；選擇一個實現比對與計分的算法與軟件；選擇一個實現比對與計分的算法與軟件；確定軟件的參數；確定軟

10、件的參數；合理地解釋比對的結果；合理地解釋比對的結果；與雙序列比對一樣，多序列比對也有全局比對和部分比對。與雙序列比對一樣，多序列比對也有全局比對和部分比對。28一動態規劃法進展多序列比對一動態規劃法進展多序列比對A計算三個序列間的一個比對單元計算三個序列間的一個比對單元i,j,k依賴于其依賴于其7個前導項；個前導項；B計算計算u=ATGTTAT，v=ATCGTAC，w=ATGC三序列比對的三維得分矩陣三序列比對的三維得分矩陣。計算三序列比對計算三序列比對29二漸進多序列比對二漸進多序列比對三個序列的配對比對未必能組合成一個多序列比對三個序列的配對比對未必能組合成一個多序列比對30對于接近或超

11、越對于接近或超越100個序列的多序列比對，漸進多序列比對具有較高效率。最個序列的多序列比對，漸進多序列比對具有較高效率。最流行的漸進多序列比對軟件是流行的漸進多序列比對軟件是Clustal家族。家族。31ClustalW有以下特點：有以下特點：首先，在比對中對每個序列賦予一個特殊的權值以降低高度近似序列的影響和提首先，在比對中對每個序列賦予一個特殊的權值以降低高度近似序列的影響和提高相距遙遠的序列的影響如以下圖。高相距遙遠的序列的影響如以下圖。ClustalW中對序列賦權的方法中對序列賦權的方法32其次，根據序列間進化間隔的離異度其次，根據序列間進化間隔的離異度divergence在比對的不同

12、階段運用不同在比對的不同階段運用不同的氨基酸交換矩陣；的氨基酸交換矩陣；第三，采用了與特定氨基酸相關的空缺第三，采用了與特定氨基酸相關的空缺gap罰分函數，對親水性氨基酸區域罰分函數，對親水性氨基酸區域中的空缺予以較低的罰分；中的空缺予以較低的罰分；第四，對在早期配對比對中產生空缺的位置進展較少的罰分，對引入空缺和擴展第四，對在早期配對比對中產生空缺的位置進展較少的罰分，對引入空缺和擴展空缺進展不同的罰分。空缺進展不同的罰分。33迭代法迭代法基于一致性的方法基于一致性的方法遺傳算法遺傳算法其他多序列全局比對方法其他多序列全局比對方法34五、多序列部分比對五、多序列部分比對全局比對，其共同特征是

13、序列中一切對應字符均假定可以匹配，一切字符具全局比對，其共同特征是序列中一切對應字符均假定可以匹配，一切字符具有同等的重要性，空格的插入是為了使整個序列得到比對，包括使兩端對齊。有同等的重要性，空格的插入是為了使整個序列得到比對，包括使兩端對齊。部分比對不假定整個序列可以匹配，重在思索序列中可以高度匹配的一個區部分比對不假定整個序列可以匹配，重在思索序列中可以高度匹配的一個區段，可賦予該區段更大的計分權值，空格的插入是為了使高度匹配的區段得段，可賦予該區段更大的計分權值，空格的插入是為了使高度匹配的區段得到更好的比對。到更好的比對。35對對2個序列進展全局和部分比對可得到完全不同的結果個序列進

14、展全局和部分比對可得到完全不同的結果36 基于隱馬爾可夫模型的多序列比對方法基于隱馬爾可夫模型的多序列比對方法隱馬爾可夫模型和隱馬爾可夫模型和3個蛋白質序列個蛋白質序列PHSFTYVMT、PGSFTYW、RFTGFW的最小公共超圖的最小公共超圖37六、比對的統計顯著性六、比對的統計顯著性確定比對得分確定比對得分score能否偶爾：能否偶爾：1.將將球蛋白或肌球蛋白與大量非同源的蛋白質做比對，然后將球蛋白或肌球蛋白與大量非同源的蛋白質做比對，然后將score與這些比與這些比對的得分進展比較。對的得分進展比較。2.把一個序列與一組隨機產生的序列進展比對，然后同樣將把一個序列與一組隨機產生的序列進展

15、比對，然后同樣將score與這些比對的與這些比對的得分進展比較。得分進展比較。3.隨機將兩個序列中的一個打亂重組，比如說重組隨機將兩個序列中的一個打亂重組，比如說重組100次，并與另一個序列比對，次，并與另一個序列比對，同樣得到一組比對的得分。同樣得到一組比對的得分。38第三節第三節 數據庫搜索數據庫搜索Section 3 Database Search39一、經典一、經典BLASTBLAST根本的根本的BLAST算法本身很簡單，它的要點是片段對算法本身很簡單，它的要點是片段對segment pair的概的概念，它是指兩個給定序列中的一對子序列，它們的長度相等，且可以構成念，它是指兩個給定序列

16、中的一對子序列，它們的長度相等，且可以構成無空格的完全匹配。無空格的完全匹配。40程序名程序名查詢序列查詢序列數據庫類型數據庫類型方法方法blastp蛋白質蛋白質蛋白質蛋白質用蛋白質查詢序列搜索蛋白質序列數據庫用蛋白質查詢序列搜索蛋白質序列數據庫blastn核酸核酸核酸核酸用核酸查詢序列搜索核酸序列數據庫用核酸查詢序列搜索核酸序列數據庫blastx核酸核酸蛋白質蛋白質將核酸序列按將核酸序列按6條鏈翻譯成蛋白質序列后搜索蛋白質條鏈翻譯成蛋白質序列后搜索蛋白質序列數據庫序列數據庫tblastn蛋白質蛋白質核酸核酸用蛋白質查詢序列搜索核酸序列數據庫，核酸序列按用蛋白質查詢序列搜索核酸序列數據庫，核酸

17、序列按6條鏈翻譯成蛋白質條鏈翻譯成蛋白質tblastx核酸核酸核酸核酸將核酸序列按將核酸序列按6條鏈翻譯成蛋白質序列后搜索由核酸條鏈翻譯成蛋白質序列后搜索由核酸序列數據庫按序列數據庫按6條鏈翻譯成的蛋白質序列的數據庫條鏈翻譯成的蛋白質序列的數據庫BLAST的查詢序列和數據庫的類型的查詢序列和數據庫的類型41BLAST算法圖示算法圖示42二、衍生二、衍生BLASTBLAST一一PSI-BLASTPSI-BLAST主要用于搜索與感興趣的蛋白質關系較遠的蛋白質。主要用于搜索與感興趣的蛋白質關系較遠的蛋白質。二二PHI-BLASTPHI-BLAST用來協助判別這個蛋白質屬于哪個家族。用來協助判別這個蛋

18、白質屬于哪個家族。三三BLASTZBLASTZBLASTZBLASTZ是在比對人和鼠的基因組中開展起來的，它適宜于比對非常長的序列。是在比對人和鼠的基因組中開展起來的，它適宜于比對非常長的序列。43三、三、BLATBLATBLATThe BLAST-Like Alignment Tool與與BLAST搜索原理類似，但開展搜索原理類似，但開展了一些專門針對全基因組分析的技術。了一些專門針對全基因組分析的技術。BLAT的優點在于速度快，其比對速度要比的優點在于速度快，其比對速度要比BLAST快幾百倍，其根本緣由在快幾百倍，其根本緣由在于于: BLAST是將查詢序列索引化，而是將查詢序列索引化，而B

19、LAT那么是將搜索數據庫索引化，那么是將搜索數據庫索引化，BLAT 把相關的呈共線性的比對結果銜接成為更大的比對結果。把相關的呈共線性的比對結果銜接成為更大的比對結果。44四、四、RNARNA序列搜索序列搜索RNA序列比對序列比對/搜索算法可大致分成兩類：搜索算法可大致分成兩類： 查詢序列查詢序列query的構造未知，要找到數據庫中和其構造相近的同源序列。的構造未知，要找到數據庫中和其構造相近的同源序列。45 利用查詢序列的構造信息，在構造信息的運用上又可以細分為：利用查詢序列的構造信息，在構造信息的運用上又可以細分為：經過構建一個描畫經過構建一個描畫RNA序列共性構造的概率模型進展數據庫檢索

20、；序列共性構造的概率模型進展數據庫檢索； 基于索引基于索引index或者模體或者模體motif描畫的方法定義描畫的方法定義rna構造或共性構造，構造或共性構造，并進展數據庫搜索。并進展數據庫搜索。46五、數據庫搜索的統計顯著性五、數據庫搜索的統計顯著性一個典型的一個典型的BLAST搜索的輸出包括搜索的輸出包括E值和得分，后者又分原始得分值和得分，后者又分原始得分raw scores和比特得分和比特得分bit scores。 P=1-e-EP值和值和E值是反映比對顯著性的兩種不同方式，大部分值是反映比對顯著性的兩種不同方式，大部分BLAST在線效在線效力運用力運用E值而非值而非P值來定義搜索的統

21、計學顯著性。值來定義搜索的統計學顯著性。47第四節第四節 比對軟件、參數與數據資源比對軟件、參數與數據資源Section 4 Alignment Software， Parameter and Resource48一、參數選擇的普通原那么一、參數選擇的普通原那么空格罰分涉及幾個問題：空格罰分涉及幾個問題：空格罰分能否大于失配罰分；空格罰分能否大于失配罰分；不同大小空缺的罰分；不同大小空缺的罰分；空格的引入與延伸能否予以不同罰分。空格的引入與延伸能否予以不同罰分。49假設一次數據庫搜索產生了太多的前往結果，可采取如下措施：假設一次數據庫搜索產生了太多的前往結果，可采取如下措施： 運用參考序列帶運

22、用參考序列帶“refseq的數據庫，這樣可減少許多冗余結果；的數據庫，這樣可減少許多冗余結果； 使查詢序列只包含一個構造域，減少多構造域帶來的多匹配；使查詢序列只包含一個構造域，減少多構造域帶來的多匹配； 根據查詢序列與數據庫序列的關系運用更適宜的交換計分矩陣；根據查詢序列與數據庫序列的關系運用更適宜的交換計分矩陣； 降低降低E值。值。50假設一次數據庫搜索產生了太少的前往結果，可采取如下措施：假設一次數據庫搜索產生了太少的前往結果，可采取如下措施： 提高提高E值；值； 運用更大的運用更大的PAM矩陣或更小的矩陣或更小的BLOSUM矩陣；矩陣； 減小字長以及減小閾值。減小字長以及減小閾值。51

23、二、主要比對軟件二、主要比對軟件52三、三、EBIEBI中的序列比對工具中的序列比對工具雙序列比對雙序列比對多序列比對多序列比對特性特性工具工具工具工具Global alignmentNeedleClustal OmegaGlobal alignmentStretcherClustalW2Local alignmentWaterDbClustalLocal alignmentLalignKalignLocal alignmentMatcherMAFFTGenomic alignmentPromoterWiseMUSCLEGenomic alignmentGeneWiseMViewGenomic alignmentWise2DBAPRANK53四、四、UCSCUCSC中的中的BLATBLAT比對工具比對工具BLAT在線工具在線工具輸入界面輸入界面54BLAT在線工具在線工具輸出結果輸出結果55第五節第五節 比對技術的開展比對技術的開展Section 5 Advances of Alignment Techniques56一、一、glocal glocal 比對比對兩個序列的部分、全局和兩個序列的部分、全局和glocal比對所對應