第3講-序列比對

序列比對序列比對基本概念、打分矩陣與算法1序列比對的根本任務是：發(fā)現(xiàn)序列之間的相似性辨別序列之間的差異目的： 相似序列相似的結(jié)構(gòu)，相似的功能 判別序列之間的同源性 推測序列之間的進化關系???2主要內(nèi)容一、概述1、生物序列之間的關系2、序列比對的概念3、序列比對的意義二、序列比對的得分系統(tǒng)1、核酸的得分矩陣2、蛋白質(zhì)的得分矩陣3、空位罰分體系三、序列比對的算法31、生物序列之間的關系序列比對的理論基礎是進化學說，如果兩個序列之間具有足夠的相似性，就推測二者可能有共同的進化祖先，經(jīng)序列內(nèi)殘基或者序列片段的替換、插入、缺失等遺傳編譯過程分別演化而來。相似性高并不一定來自同一祖先。4原序列：ACGTTAGCGCTAGCTGCTAGCTAG替

換：ACGCTAGCGCTAGCTGCTAGCTAG插

入：ACGCTAGCGCTAGCTAGCTAGCTAG

缺

失：ACGCTAGCGCAGCTGCTAGCTG

5同源性（homology）同源性：兩條序列有一個共同的進化祖先，那么它們是同源的。相似性（similarity）：序列間相似性的量度。同源性是序列同源或者不同源的一種論斷，而相似性或者一致性是二個序列相關性的量化，是兩個不同的概念。兩序列有90%的相似性兩序列有90%的同源性6直系同源（orthology）：不同物種內(nèi)的同源序列。旁系同源（paralogy）：同一物種內(nèi)的同源序列。7人類與模式生物——小鼠

因為他們各自的kit基因都存在缺陷8基本概念：序列：由一些字母組成的字符串，包括核酸和蛋白質(zhì)序列。字母表（alphabet），核酸序列（DNA序列）的字母表為ATGC，再加一個gap（-）。gap空位。字符串長度：AT-GGCC的長度為7。子序列【可以非連續(xù)】或子串（subsequence）：原序列中任意連續(xù)的一段序列，包括0長度和全長的序列。隨機序列：每個位置出現(xiàn)ATGC中任何一個字符的概率都是1/4。也就沒有什么生物學方面的意義。非隨機序列也就是有生物學意義的序列。距離：兩序列之間差異程度的一個量化數(shù)字，如兩個序列完全相同則距離為0。2、序列比對的概念9序列比對(alignment)，是根據(jù)特定的計分規(guī)則，將兩個或多個符號序列按位置比較排列后，得到最具相似性的排列的過程。ACGCTAGCGCTAGCTGCTAGCTAGACGTTAGCGCTAGCTGCTAGCTAGACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCTG-ACGCTAGCGCAAGCTGCTAGCT-G10Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247比對的三種情況匹配不匹配空位11序列比對(alignment)，是根據(jù)特定的計分規(guī)則，將兩個或多個符號序列按位置比較排列后，得到最具相似性的排列的過程。計分規(guī)則：序列相似性的計算規(guī)則規(guī)定匹配、不匹配、空位各自的得分如：匹配：1不匹配：0空格：0ACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCTG-21ACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCT-G2212記分矩陣（scoringmatrix），即記分規(guī)則。RawScore和Bitscore：比對得分。記分矩陣不同，可能得到不同的結(jié)果。ATCG-A10000T01000C00100G00010-0000╳13全局比對：序列全長進行比對，尋找一個最佳的配對。局部比對：子序列比對，只需要尋找局部的最佳匹配。比對的統(tǒng)計顯著性E值。Algorithm算法。AATCTATAAAGATA14序列比對的關鍵問題：

記分矩陣算法153、序列比對的意義序列比對(alignment)是序列分析的基礎，其他一切都建立在序列比對的基礎上。根據(jù)相似性推導可能的演化過程，確定親緣關系，構(gòu)建進化書。最常見的是蛋白質(zhì)序列之間或者核酸序列之間的兩兩比對。通過比較兩個序列之間的相似區(qū)域和保守性位點，尋找二者可能的分子進化關系。將多個序列同時比對，尋找這些有進化關系的序列之間共同的保守區(qū)域、位點和profile（概型），從而探索導致它們產(chǎn)生共同功能的序列模式（motif）。把蛋白質(zhì)序列與核酸序列相比來探索核酸序列可能的表達框架。把蛋白質(zhì)序列與具有三維結(jié)構(gòu)信息的蛋白質(zhì)相比，從而獲得蛋白質(zhì)折疊類型的信息。比對還是數(shù)據(jù)庫搜索算法的基礎。可以通過查詢序列與整個數(shù)據(jù)庫所有序列進行比對，從數(shù)據(jù)庫中獲得與其相似序列的已有數(shù)據(jù)，對于進一步分析其結(jié)構(gòu)和功能會有很大的幫助。16確定特定的蛋白質(zhì)或者核酸序列有哪些直系同源或旁系同源序列?！舅阉髡麄€數(shù)據(jù)庫】確定哪些蛋白質(zhì)和基因在特定的物種中出現(xiàn)。確定一個DNA或蛋白質(zhì)序列身份。發(fā)現(xiàn)新基因。確定一個特定基因或者蛋白質(zhì)有哪些已經(jīng)被發(fā)現(xiàn)了的變種。研究可能存在多種剪接方式的表達序列標簽。尋找對于一個蛋白質(zhì)的功能和/或結(jié)構(gòu)域起關鍵作用的氨基酸殘基。17二、序列比對的得分系統(tǒng)1、核酸的得分矩陣（WeightMatrices）核酸打分矩陣設DNA序列所用的字母表為={A，C，G，T}Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247比對需要一個量化的分數(shù)。181、核酸的得分矩陣（WeightMatrices）a.等價矩陣ATCGA1000T0100C0010G0001AGTCGAAATCGT4191、核酸的得分矩陣（WeightMatrices）b.BLAST矩陣ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45AGTCGAAATCGT?12201、核酸的得分矩陣（WeightMatrices）c.轉(zhuǎn)換顛換矩陣（transition，transversion）（嘌呤：腺嘌呤A，鳥嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51AGTCGAAATCGT?-2212、蛋白質(zhì)打分矩陣（i）等價矩陣（ii）遺傳密碼矩陣GCM（iii）疏水矩陣（iv）PAM矩陣（PointAcceptedMutation）（v）BLOSUM矩陣（BlocksAminoAcidSubstitutionMatrices）其中Rij代表打分矩陣元素i、j分別代表字母表第i和第j個字符。22遺傳密碼矩陣通過計算一個氨基酸殘基轉(zhuǎn)變到另外一個氨基酸殘基所需的堿基變化的最小數(shù)目而得到。23疏水矩陣是根據(jù)氨基酸殘基替換前后疏水性的變化而得到的矩陣。若一次氨基酸替換，疏水性不發(fā)生太大的變化，則這種替換得分高，否則替換得分低。蛋白質(zhì)疏水矩陣24PAM矩陣（PointAcceptedMutation）基于進化的點突變模型，通過統(tǒng)計相似序列比對中的各種氨基酸替換發(fā)生率而得到該矩陣。如果兩種特定的氨基酸之間替換發(fā)生得比較頻繁，那么這一對氨基酸在得分矩陣中的互換得分就比較高。該記分矩陣科學，用得多。25矩陣集合-----PAM-N如，PAM60矩陣用于比較相距60個PAM單位的序列。26cstp27針對不同的進化距離采用不同的PAM矩陣序列相似度=40%50%60%

|||打分矩陣=PAM120PAM80PAM60PAM250→14%-27%

28BLOSUM62模塊氨基酸替換矩陣29BLOSUM90PAM30高相似度小鼠和大鼠RBPBLOSUM45PAM240低相似度小鼠和細菌的lipocalinBLOSUM80PAM120BLOSUM62PAM180相似度越低的序列，在比對的時候，采用PAM矩陣時，后面的數(shù)字越大，采用BLOSUM矩陣時，后面的數(shù)字越小。303，空位罰分體系一般有兩種罰分方法：1，線性罰分2，仿射罰分（affinepenalty）原理在于一個位置變異的影響小于多個位置同時變異的影響。從生物學角度看，一個位置發(fā)生變異是一個突變事件，而多個位置發(fā)生變異可能是發(fā)生了多個進化（突變）事件。AGTCGATAGTCGATAGT---TAGTCGATAGTCGATAGTCGATA-TCGAT-GTC-AT31三、序列比對的算法點陣法動態(tài)規(guī)劃法詞或k串法（BLAST或FASTA中采用）。32點陣法點陣法是最基本的，也是很重要的一種可視化序列比對方法?！熬仃囎鲌D法”或“對角線作圖”。首先建立一個矩陣，兩條序列的長度分別為矩陣的行數(shù)和列數(shù)，一條序列置于矩陣的頂部，一條序列置于矩陣的左側(cè)。把具有相同字符的單元做標記。ACCTGAGCTCGTTAACCAGCTAA33對角線上的元素如果兩個序列完全相同，則對角線上每個位置都會出現(xiàn)標記。34其它位置的元素其它位置如果出現(xiàn)連續(xù)的相同字符，同樣可以在表中體現(xiàn)出來。點陣圖可以很直觀的發(fā)現(xiàn)兩條序列所有可能的匹配，這些匹配可能是某種功能域。也可用于尋找蛋白質(zhì)或者DNA內(nèi)部的重復或者反向重復區(qū)域35反向重復序列序列1→序列2→36滑動窗口技術由于序列可能很長，而字符只有4個（核酸），所以會有很多隨機性的沒有生物學意義的相似性，這些是比對中的噪聲。使用滑動窗口代替一次一個位點的比較是解決噪聲問題的有效方法。假設窗口大小為10，相似度閾值為8，則每次比較取10個連續(xù)的字符，如相同的字符超過8個，則標記。基于滑動窗口的點矩陣方法可以明顯地降低點陣圖的噪聲，并且明確無誤的指示出了兩條序列間具有顯著相似性的區(qū)域。37滑動窗口的過濾不連續(xù)的匹配可能是噪聲，需要用滑動窗口過濾，滑動窗口有兩個參數(shù)，一是窗口大小，二是閾值，也就是不匹配的字符個數(shù)。例如我們這個例子由于字符個數(shù)很少，用（3，0）的參數(shù)。TGCTGCTCCG010010000C000000000T000000000A000000000G000000000A000000000T000000000A000000000A000000000滑動窗口是這樣使用的：從（1，1）位置出發(fā)，將序列1的1～3個字符與序列2的1～3個字符比較，如果都相同，則在（1，1）位置處做標記，一直到完成整個表。例如如上表中的（1，5）位置做了標記，是因為序列1的1～3個元素和序列2的5～7個元素是相同的。38（a）對人類（Homosapiens）與黑猩猩（Pongo

pygmaeus）的β球蛋白基因序列進行比較的完整點陣圖。（b）利用滑動窗口對以上的兩種球蛋白基因序列進行比較的點陣圖，其中窗口大小為10個核苷酸，相似度閾值為8。(a)(b)39點陣圖的一個例子

1AAGGTCAGGAACAAAGAAACAGCTGAATACCAAACAGGATATCTGTGGTAAGCGGTTCCT61GCCCCGGCTCAGGGCCAAGAACAGATGAGACAGCTGAGTGATGGGCCAAACAGGATATCT121GTGGTAAGCAGTTCCTGCCCCGGCTCGGGGCCAAGAACAGATGGTCCCCAGATGCGGTCChttp:///molkit/dnadot/

兩條相同序列的比對40課堂練習GGGATCACGTATGCATTAGCATACATCACGCGGCCGCGTGATGTATGCTAATGCATACGTGATCCC第二條序列是第一條序列的反向互補序列，通過點陣圖分析尋找序列可能的發(fā)夾狀結(jié)構(gòu)。思考：點陣法為什么可以發(fā)現(xiàn)RNA序列的發(fā)夾狀結(jié)構(gòu)？發(fā)夾結(jié)構(gòu)41雙序列比對的動態(tài)規(guī)劃算法進行雙序列比對最直接的方法是生成兩序列的所有可能的比對，分別計算得分，然后挑選一個得分最高的比對作為最終結(jié)果。但可能的比對是序列長度的指數(shù)函數(shù)。AATCGTAGTCGAAATCGT--ATCGTAAATCGT------CGTCGA42N-W算法是一種全局比對動態(tài)規(guī)劃算法，于1970年被提出，得到了非常廣泛的應用。首先假設我們要對兩條序列a和b進行比對，它們的長度分別為M和N，序列a的第i個字符（殘基）為ai，序列b的第j個字符為bj

。動態(tài)規(guī)劃算法由四部分組成：1）存儲子問題的最優(yōu)化的動態(tài)規(guī)劃矩陣；2）最優(yōu)化的遞歸計算方法；3）給出自問題最優(yōu)解的矩陣填充過程和4）尋找最優(yōu)化比對路徑的回溯方法。Needleman-Wunsch算法序列a:AAGGTCAGGAA43采用簡單打分系統(tǒng)匹配得4分，不匹配得－3分，空位得－4分，或者用前面講過的計分矩陣。為了量化，我們必須對各種配對情況給一個分數(shù)。441）用來存儲子問題的最優(yōu)化動態(tài)規(guī)劃矩陣－ATTCCAAG－TTCGAGT序列a矩陣中每一元素的值S（i,j）代表b序列前i個字符與a序列前j個字符的最優(yōu)比對得分。序列b45假設我們已經(jīng)得到了：

①長M-1的a序列和長N-1的b序列的最優(yōu)比對②長M-1的a序列和長N的b序列的最優(yōu)比對③長M的a序列和長N-1的b序列的最優(yōu)比對那么對于長M的a序列和長N的b序列能否簡單的得到最優(yōu)比對呢？。。。。。。。。。。。。。。。。。。。。。。。MN序列a序列b？M-1N-13個紅色圈的最佳值已知。2）最優(yōu)化的遞歸計算方法46長M的a序列和長N的b序列的最佳比對排列只能從三種方式中產(chǎn)生：兩個字符和出現(xiàn)在同一列中。。。AAGT。。。。ACG與一個空位出現(xiàn)在同一列中。。。AAGT。ACG。。－與一個空位出現(xiàn)在同一列中。。。AAG－。ACG。。G①在長M-1的a序列和長N-1的b序列的最優(yōu)比對基礎上，a、b兩序列各增加一個字符。②在長M-1的a序列和長N的b序列的最優(yōu)比對基礎上，a序列增加一個字符、b兩序列增加一個空格。③在長M的a序列和長N-1的b序列的最優(yōu)比對基礎上，a序列增加一個空格、b兩序列增加一個字符。47兩個字符和出現(xiàn)在同一列中。。。AAGT。。。。ACG這種情況下比對得分情況是怎么樣的呢？表示兩條序列各去掉最后一個字符的最佳得分表示兩個字符配對的分值，見前面的打分系統(tǒng)。這段比對得分已知48這種情況下比對得分情況是怎么樣的呢？與一個空位出現(xiàn)在同一列中。。。AAGT。ACG。。－d表示空位罰分值。與一個空位出現(xiàn)在同一列中的時候序列a，b的最優(yōu)比對得分是上述三種情況的最大值。49據(jù)此，我們可以寫出一個概括性的公式。。。AAGT。。。。ACG。。。AAGT。。ACG。－50。。。。。。。。。。。。。。。。。。。。。。。MN序列a序列b？M-1N-1513）給出子問題最優(yōu)解的矩陣填充過程－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28①第一行、第一列初始化，第一行填入-id，第一列填入-jd，d為空位罰分。52②其他矩陣元素按以下公式計算填入，并記錄傳遞路線：534）矩陣回溯以尋找最優(yōu)比對路徑一旦整個矩陣填充完畢，就可以得到最優(yōu)比對得分，即矩陣中最后一個得分，要找出最優(yōu)比對排列方式，我們還需要對整個矩陣進行回溯。從矩陣的最后一個單元（M,N）開始，根據(jù)填充記錄的路徑，直到回溯到第一個單元（0，0）。斜線，則兩條序列各順序加一字符；橫線，則a序列順序加字符，b序列加空格；豎線，則a序列順序加空格，b序列順序加字符。54例題講解利用Needleman-Wunsch算法對兩條DNA序列進行全局比對。a＝ATTCCAAG，b＝TTCGAGT，得分系統(tǒng)是（4，－3，－4）求解這個問題分3步。（1）給動態(tài)規(guī)劃矩陣賦初值（2）按照最優(yōu)分的遞歸算法填充動態(tài)規(guī)劃矩陣（3）從最后一個單元格開始，回溯最優(yōu)化比對路徑55（1）給動態(tài)規(guī)劃矩陣賦初值－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28012345678

0123456756（2）按照最優(yōu)分的遞歸算法填充動態(tài)規(guī)劃矩陣－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28－30－7－4得分系統(tǒng)是（4，－3，－4）－8－12－16－20－24145758（3）從最后一個單元格開始，回溯最優(yōu)化比對路徑ATTCCAAG－－TTCGA－GT5960作業(yè)找出例題中其它的最佳比對結(jié)果（總共4個比對，還有2個）用動態(tài)規(guī)劃法找出兩序列的所有最佳比對，要求寫出詳細過程。打分矩陣采用{（4，－3，－4}，即匹配得4分，不匹配得－3分，空位得－4分。序列1：AAAG，序列2：ACG61總結(jié)動態(tài)規(guī)劃算法是一種高效的給出最優(yōu)比對的算法。它的基本思想就是將待解決問題分成若干個子問題，先求解子問題，并存儲子問題的解而避免重復計算，然后從這些子問題的解得到原問題的解。動態(tài)規(guī)劃算法能保證在給定得分系統(tǒng)下產(chǎn)生最優(yōu)的比對結(jié)果（optimalalignment）。但是這種方法對參數(shù)非常敏感，記分系統(tǒng)參數(shù)的選擇在很大程度上決定著比對的結(jié)果。最優(yōu)比對結(jié)果往往不止一個，次優(yōu)結(jié)果也有可能更具有生物學意義，最優(yōu)只是數(shù)學上的概念，而且是跟記分系統(tǒng)參數(shù)相關的。62Smith-Waterman算法局部比對的應用范圍比全局比對更廣。S-W算法與N-W算法的區(qū)別在于多了一個去頭去尾的操作。去頭，在動態(tài)規(guī)劃矩陣的每個單元格的計算增加一條路徑。也就是如果當前比對分數(shù)小于0，那么之前的比對全部去掉，比對從目前位置重新開始。去尾，回溯的時候不是從最后開始，而是從最大的分數(shù)開始，直到遇到0。63例題3.3利用S-W算法對兩條DNA序列進行局部比對。a=ATTCCAAG，b=TTCGAGT，得分系統(tǒng)：｛4，-3，-4｝一、給動態(tài)規(guī)劃矩陣賦初值。0000000000000000-ATTCCAAG-TTCGAGT64例題3.3（2）按照最優(yōu)化的遞歸算法填充動態(tài)規(guī)劃矩陣。00000000000440000000484000