生物信息學(xué)概論第二章數(shù)據(jù)庫(kù)搜索與兩兩比對(duì)

1、第二章 數(shù)據(jù)搜索與兩兩比對(duì) 本章描述了 如何比對(duì)兩條或多條相關(guān)核苷酸或多肽序列，如何比對(duì)兩條或多條相關(guān)核苷酸或多肽序列， 如何搜索存儲(chǔ)序列信息的數(shù)據(jù)庫(kù)。如何搜索存儲(chǔ)序列信息的數(shù)據(jù)庫(kù)。通過(guò)比對(duì)得到預(yù)測(cè)蛋白質(zhì)、新基因結(jié)構(gòu)和功能以及基因間、蛋白質(zhì)間乃至物種之間進(jìn)化關(guān)系的重要信息。2.1 點(diǎn)陣圖 評(píng)估兩條序列相似度最簡(jiǎn)單的方法之一是利用點(diǎn)陣圖點(diǎn)陣圖。 第一條被比較的序列排列在點(diǎn)陣圖空間的橫軸，第二條序列則排列在縱軸。點(diǎn)陣空間中兩條序列中的殘基相同時(shí)，在對(duì)應(yīng)的位點(diǎn)上畫(huà)上圓點(diǎn)，兩條序列間連續(xù)相同的區(qū)域在圖中會(huì)形成由圓點(diǎn)組成的上斜線。具有連續(xù)相似區(qū)域的兩條具有連續(xù)相似區(qū)域的兩條DNA序列的簡(jiǎn)單點(diǎn)陣圖序列的簡(jiǎn)

2、單點(diǎn)陣圖滑動(dòng)窗口技術(shù)滑動(dòng)窗口技術(shù) 使用滑動(dòng)窗口滑動(dòng)窗口代替一次一個(gè)位點(diǎn)的比較是解決這 個(gè)問(wèn)題的有效方法。 假設(shè)窗口大小窗口大小為10，相似度閾值相似度閾值為8，則每次比較取10個(gè)連續(xù)的字符，如相同的字符超過(guò)8個(gè)，則標(biāo)記 基于滑動(dòng)窗口滑動(dòng)窗口的點(diǎn)矩陣點(diǎn)矩陣方法可以明顯地降低點(diǎn)陣圖的噪聲，并且明確無(wú)誤的指示出了兩條序列間具有顯著相似性的區(qū)域。 （a）對(duì)人類(lèi)（）對(duì)人類(lèi)（Homo sapiens）與黑猩猩（）與黑猩猩（Pongo pygmaeus）的）的球蛋球蛋白基因序列進(jìn)行比較的完整點(diǎn)陣圖。（白基因序列進(jìn)行比較的完整點(diǎn)陣圖。（b）利用滑動(dòng)窗口對(duì)以上的兩種球）利用滑動(dòng)窗口對(duì)以上的兩種球蛋白基因序列進(jìn)行

3、比較的點(diǎn)陣圖，其中窗口大小為蛋白基因序列進(jìn)行比較的點(diǎn)陣圖，其中窗口大小為10個(gè)核苷酸，相似度閾個(gè)核苷酸，相似度閾值為值為8。 (a) (b) 2.2 2.2 簡(jiǎn)單比對(duì)簡(jiǎn)單比對(duì) 比對(duì)比對(duì)就是兩條序列字符間簡(jiǎn)單的兩兩匹配。比對(duì)可以反映出兩條或多條同源序列間的進(jìn)化關(guān)系. 最簡(jiǎn)單的情況下即不考慮空位，當(dāng)兩條序列對(duì)比時(shí)，要做的僅是為較短的序列選擇比對(duì)的起始點(diǎn)。 考慮這樣的兩條核苷酸序列： AATCTATA和AAGATA 僅有三種比對(duì)方式不考慮空位的簡(jiǎn)單比對(duì)，它的打分函數(shù)是有對(duì)比獎(jiǎng)勵(lì)和罰分的和來(lái)決定上例中三個(gè)比對(duì)從左至右分別是 4、 1、 3匹配得分：匹配得分：1失配得分：失配得分：02.3 空位空位 兩

4、條或多條序列比對(duì)時(shí)，如果考慮到插入與刪除時(shí)間發(fā)生地可能性，那么候選的比對(duì)數(shù)量就會(huì)大大增加，也就導(dǎo)致了比對(duì)的復(fù)雜性。上節(jié)中兩條核苷酸序列，在不考慮空位時(shí)僅有三種比對(duì)，而較短的那條加入了兩個(gè)空位后，變產(chǎn)生了28種不同的比對(duì)，例如：等等2.3.1 簡(jiǎn)單空位罰分簡(jiǎn)單空位罰分 對(duì)含有空位的比對(duì)打分時(shí)，空位罰分空位罰分就必須包含到打分函數(shù)中，空位比對(duì)的簡(jiǎn)單打分公式如下：例如：假設(shè)匹配得分為1，失配得分為0，空位罰分為-1三種空位比對(duì)的得分從左至右分別是1、3、32.3.2 起始罰分與長(zhǎng)度罰分起始罰分與長(zhǎng)度罰分 使用簡(jiǎn)單空位罰分對(duì)兩條序列進(jìn)行比對(duì)時(shí)，經(jīng)常能找到若干同格式最優(yōu)的比對(duì)。進(jìn)一步區(qū)分這些比對(duì)的方法是

5、找出哪些比對(duì)包含較多的不連續(xù)空位，哪些包含較少長(zhǎng)度較長(zhǎng)的空位片段。插入插入/刪除事件刪除事件 假設(shè)兩條序列長(zhǎng)度分別是12和9 假設(shè)這兩條序列是真正的同源序列，那么它們之間長(zhǎng)度的差異可以解釋為 (1)較長(zhǎng)的序列有核苷酸的插入，或者 (2) 較短的序列發(fā)生了核苷酸的刪除，或者(3) 兩者都發(fā)生了。 在不知道原始父輩序列的情況下，無(wú)法判斷導(dǎo)致空位的原因是由于一條序列的插入事件還是另一條的刪除事件，通常把這類(lèi)事件稱為插入插入/刪除事件刪除事件。 多聯(lián)核苷酸的插入刪除事件插入刪除事件相對(duì)于單個(gè)核苷酸來(lái)說(shuō)會(huì)較經(jīng)常發(fā)生。 統(tǒng)計(jì)結(jié)果表明，兩條序列長(zhǎng)度上的差異更可能是單個(gè)三聯(lián)核苷酸的插入刪除事件導(dǎo)致的，而多個(gè)不

6、連續(xù)核苷酸插入刪除事件的可能性比較小?？瘴涣P分空位罰分 由序列中產(chǎn)生的新空位串引起的起始罰分起始罰分和根據(jù)缺少的字符數(shù)而定的長(zhǎng)度罰分長(zhǎng)度罰分。預(yù)設(shè)長(zhǎng)度罰分小于起始罰分，以此建立的打分函數(shù)便能獎(jiǎng)勵(lì)空位連在一起的比對(duì)。 假設(shè)起始罰分為-2，長(zhǎng)度罰分為-1，匹配得分為+1，失配得分為0，則對(duì)于這三個(gè)比對(duì)，從左至右比對(duì)的得分分別是-3，-1，+1在后兩種比對(duì)在使用簡(jiǎn)單空位罰分時(shí)，最后得分都是在后兩種比對(duì)在使用簡(jiǎn)單空位罰分時(shí)，最后得分都是+3，現(xiàn)在卻得到了不同的分?jǐn)?shù)。，現(xiàn)在卻得到了不同的分?jǐn)?shù)。2.4打分矩陣打分矩陣 正如空位罰分空位罰分可以獎(jiǎng)勵(lì)與進(jìn)化相關(guān)的的比對(duì)，失配罰分失配罰分也可以用來(lái)進(jìn)一步區(qū)分相似

7、比對(duì)。 統(tǒng)計(jì)結(jié)果表明，兩條同源的序列比對(duì)時(shí)，某些替換比其他替換常見(jiàn)的多。例例： 兩條蛋白質(zhì)序列，其中一條在某一個(gè)位置上是丙氨酸，如果該位點(diǎn)被替換成另一個(gè)較小的且疏水的氨基酸，比如纈氨酸對(duì)蛋白質(zhì)的影響很小，如果被替換成較大且?guī)щ姷臍埢热缳嚢彼?，那么?duì)蛋白質(zhì)的影響可能就會(huì)非常大。直觀的講，比較保守的替換比隨機(jī)替換更可能維持蛋白質(zhì)的功能，更不容易被淘汰，因此在打分上更傾向于丙氨酸而不是賴氨酸。打分矩陣（打分矩陣（Scoring Matrix） 核酸打分矩陣設(shè)DNA序列所用的字母表為 = A，C，G，T a. 單位矩陣 b. BLAST矩陣 c. 轉(zhuǎn)換-顛換矩陣（transition，transv

8、ersion） （嘌呤：腺嘌呤A，鳥(niǎo)嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T） ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51單位矩陣單位矩陣轉(zhuǎn)換轉(zhuǎn)換-顛換矩陣顛換矩陣BLAST矩陣矩陣 PAM矩陣（矩陣（Point Accepted Mutation） 基于進(jìn)化的點(diǎn)突變模型基于進(jìn)化的點(diǎn)突變模型 一個(gè)一個(gè)PAM就是一個(gè)進(jìn)化的變異單位就是一個(gè)進(jìn)化的變異單位, 即即1%的氨基酸改變的氨基酸改變相對(duì)突變率相對(duì)突變率僅僅是某種氨基酸僅僅是某種氨基酸 被其他任意氨基

9、酸替換的次數(shù)被其他任意氨基酸替換的次數(shù)例如：ma是指丙氨酸與非丙氨酸殘基比對(duì)的次數(shù)，是指丙氨酸與非丙氨酸殘基比對(duì)的次數(shù)，Ma為概率為概率然而我們針對(duì)每個(gè)氨基酸對(duì)然而我們針對(duì)每個(gè)氨基酸對(duì)i 和和j，計(jì)算氨基酸，計(jì)算氨基酸j 被氨基酸被氨基酸i 替換的次數(shù)替換的次數(shù) Aij例如：Acm 是被比對(duì)序列中，甲硫氨酸被半胱氨酸替換的次數(shù)是被比對(duì)序列中，甲硫氨酸被半胱氨酸替換的次數(shù)以以Aij除以除以ma 利用每個(gè)氨基酸出現(xiàn)的頻度對(duì)起進(jìn)行標(biāo)準(zhǔn)化，得到利用每個(gè)氨基酸出現(xiàn)的頻度對(duì)起進(jìn)行標(biāo)準(zhǔn)化，得到PAM-1矩矩陣中的元素陣中的元素Rij式中Mab為任意氨基酸b替代a的概率式中pa為氨基酸a未被替換的概率100個(gè)

10、殘基發(fā)生一次替換的PAM-1矩陣針對(duì)不同的進(jìn)化距離采用針對(duì)不同的進(jìn)化距離采用PAM 矩陣矩陣序列相似度序列相似度 = 40% 50% 60% | | |打分矩陣打分矩陣 = PAM120 PAM80 PAM 60PAM250 14% - 27% 2.5 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃: Needleman 和和 Wunsch 算法算法 一旦選定了序列比對(duì)打分的方法，就可以為尋找最佳比對(duì)設(shè)計(jì)算法了。 最顯而易見(jiàn)的方法就是對(duì)每個(gè)可能的比對(duì)進(jìn)行窮窮舉搜索舉搜索，但這一般是不可行的。 我們可以用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題，即把一個(gè)問(wèn)題分解成計(jì)算量合理的子問(wèn)題，并使用這些子問(wèn)題的結(jié)果來(lái)計(jì)算最終答案。 S. Need

11、leman與C. Wunsch首次運(yùn)用動(dòng)態(tài)規(guī)劃方動(dòng)態(tài)規(guī)劃方法法來(lái)進(jìn)行序列分析。 假設(shè)兩條序列：CACGA和CGA，使用統(tǒng)一的空位空位和失配罰分失配罰分 則：1、給第一條序列加一個(gè)空位 2、給第二條序列加一個(gè)空位 3、兩條序列都不加空位如果知道了ACGA與GA最佳比對(duì)的得分，就可以立即計(jì)算出表中第一行的得分。同樣地，如果知道了表中第二、第三行剩余序列的最佳比對(duì)的得分，就可以計(jì)算出起始位點(diǎn)的不同的三種比對(duì)得分。動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法通過(guò)計(jì)算部分序列比對(duì)得分并填入一個(gè)表格，直到整個(gè)序列比對(duì)被計(jì)算出來(lái)， 由此得到最優(yōu)比對(duì)。第一位點(diǎn) 得分待對(duì)比的剩余序列CC+1ACGAGA-C-1CACGAGAC-1

12、ACGACGA（匹配得分為1，失配得分為0，空位罰分為-1）動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃比對(duì)ACAGTAG與ACTCG空位罰分為 -1匹配獎(jiǎng)勵(lì)為 +1失配得分為 00-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG用空位罰分的倍數(shù)用空位罰分的倍數(shù)對(duì)表格第一行與第對(duì)表格第一行與第一列進(jìn)行初始化一列進(jìn)行初始化填充表格填充表格0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG表格中表格中橫向移動(dòng)橫向移動(dòng)表示在表示在縱軸序列中加入一個(gè)空縱軸序列中加入一個(gè)空位位縱向移動(dòng)縱向移動(dòng)表示在橫軸序表示在橫軸序列中加入一個(gè)空位列中加入一個(gè)空位斜對(duì)角向移動(dòng)斜對(duì)

13、角向移動(dòng)表示兩序表示兩序列各自相應(yīng)的核苷酸進(jìn)列各自相應(yīng)的核苷酸進(jìn)行了比對(duì)行了比對(duì)橫向移動(dòng)橫向移動(dòng)縱向移動(dòng)縱向移動(dòng)斜對(duì)角向移動(dòng)斜對(duì)角向移動(dòng)0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG-1-1=-2，表示在橫向序列中插，表示在橫向序列中插入一個(gè)空位，然后與縱向序列入一個(gè)空位，然后與縱向序列中的中的A比較，空位罰分比較，空位罰分-1。-1-1=-2，表示在縱，表示在縱向序列中插入一個(gè)向序列中插入一個(gè)空位，然后與橫向空位，然后與橫向序列中的序列中的A比較，比較，空位罰分空位罰分-1。0+1=1，表示兩序，表示兩序列的第一個(gè)列的第一個(gè)A進(jìn)行進(jìn)行對(duì)比，匹配獎(jiǎng)勵(lì)對(duì)比，

14、匹配獎(jiǎng)勵(lì)1。0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG1-1=0，表示在橫向序列中插入，表示在橫向序列中插入一個(gè)空位，然后與縱向序列中一個(gè)空位，然后與縱向序列中的的C比較，空位罰分比較，空位罰分-1。-2-1=-3，表示在縱，表示在縱向序列中插入一個(gè)向序列中插入一個(gè)空位，然后與橫向空位，然后與橫向序列中的序列中的A比較，比較，空位罰分空位罰分-1。-1+0=-1，表示橫向，表示橫向序列的序列的A與縱向序與縱向序列的列的C進(jìn)行比較，進(jìn)行比較，失配得分失配得分0。0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG-2-1=

15、-3，表示在橫向序列中插，表示在橫向序列中插入一個(gè)空位，然后與縱向序列入一個(gè)空位，然后與縱向序列中的中的A比較，空位罰分比較，空位罰分-1。1-1=0，表示在縱，表示在縱向序列中插入一個(gè)向序列中插入一個(gè)空位，然后與橫向空位，然后與橫向序列中的序列中的C比較，比較，空位罰分空位罰分-1。-1+0=-1，表示橫向，表示橫向序列的序列的C與縱向序與縱向序列的列的A進(jìn)行比較，進(jìn)行比較，失配得分失配得分0。0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG0-1=-1，表示在橫向序列中插，表示在橫向序列中插入一個(gè)空位，然后與縱向序列入一個(gè)空位，然后與縱向序列中的中的C比

16、較，空位罰分比較，空位罰分-1。0-1=-1，表示在縱，表示在縱向序列中插入一個(gè)向序列中插入一個(gè)空位，然后與橫向空位，然后與橫向序列中的序列中的C比較，比較，空位罰分空位罰分-1。1+1=2，表示橫向，表示橫向序列的序列的C與縱向序與縱向序列的列的C進(jìn)行比較，進(jìn)行比較，匹配獎(jiǎng)勵(lì)匹配獎(jiǎng)勵(lì)1。 0-1-2-3-4-5-110-1-2-3-20210-1-3-11210-4-20122-5-3-1112-6-4-2011-7-5-3-102A C T C GACAGTAG為了利用打分表重建比對(duì)重建比對(duì)， 需要找出一條由表格中最右下角到最左上角的路徑！ 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 途中箭頭指示了部分打分表中的合

17、法路徑，每條路徑代表若干等價(jià)最優(yōu)比對(duì) 路徑自右下至左上排列自來(lái)分別是 根據(jù)這條線路，可以重建比對(duì)，可以得到以下這個(gè)得分為2的最優(yōu)比對(duì)0-1-2-3-4-5-110-1-2-3-20210-1-3-11210-4-20122-5-3-1112-6-4-2011-7-5-3-102A C T C GACAGTAG2.6 全局對(duì)比與局部比對(duì)全局對(duì)比與局部比對(duì)2.6.1 準(zhǔn)全部比對(duì)準(zhǔn)全部比對(duì) 到目前為止，所有討論的基本比對(duì)算法僅是做了全局全局比對(duì)比對(duì)。而比對(duì)兩序列時(shí)，這并不總是可取的。假如從AAACACGTGTCT中搜尋段序列ACGT。在若干種兩序列比對(duì)中，我們需要的是區(qū)別對(duì)待末端空位與序列內(nèi)部空位這

18、種比對(duì)稱為準(zhǔn)全局比對(duì)準(zhǔn)全局比對(duì) (semiglobal alignment)準(zhǔn)全局比對(duì)準(zhǔn)全局比對(duì)(1) 通過(guò)初始化部分打分表，表格第一行與第一列為零；(2) 允許表格最后一行與一列橫向與縱向的移動(dòng)不被罰分；Needleman 和和 Wunsch 算法的改進(jìn)算法的改進(jìn) （準(zhǔn)全局比對(duì)）（準(zhǔn)全局比對(duì)）2.6.2 Smith-Waterman算法算法 準(zhǔn)全局比對(duì)有時(shí)有點(diǎn)不能為序列搜索提供所需的適應(yīng)性 需要進(jìn)行局部比對(duì)局部比對(duì) 例如：兩條序列 AACCTATAGCT 和 GCGATATA，用準(zhǔn)全局比對(duì)算法，空位罰分為-1， 匹配獎(jiǎng)勵(lì)為+1，失配得分為-1，得：局部比對(duì)時(shí)，表中小于零的位置用零代替局部比對(duì)

19、時(shí)，表中小于零的位置用零代替AACCTATAGCT GCGATATA A A C C T A T A G C T2.6.2 Smith-Waterman算法算法局部比對(duì)局部比對(duì) 1981年，由F. Smith 和 M. Waterman首次提出； 動(dòng)態(tài)規(guī)劃方法通過(guò)較少的改動(dòng)便可以用來(lái)識(shí)別匹配的子序列， 并且忽略匹配區(qū)域之前或之后的失配和空位; 局部比對(duì)時(shí)，表中小于零的位置用零代替; 得到的局部比對(duì)代表了被比兩條序列間的最佳的匹配子序列； 局部比對(duì)方法可以識(shí)別子序列的匹配，而這是全局與準(zhǔn)全局比對(duì)不可能做到的。2.72.7數(shù)據(jù)庫(kù)搜索數(shù)據(jù)庫(kù)搜索 盡管序列比對(duì)是比較兩條已知序列的極為重要的工具，然而序

20、列比對(duì)的更為常見(jiàn)的用途是用來(lái)搜索大量序列的數(shù)據(jù)庫(kù)，以找到與特定序列相似的那些序列。 在數(shù)據(jù)庫(kù)搜索過(guò)程中，由于被搜索序列很長(zhǎng)，而且數(shù)量巨大，用簡(jiǎn)單而直接的方法將數(shù)據(jù)庫(kù)中的每條序列與查詢序列進(jìn)行比對(duì)并返回得分最高的序列難以奏效。作為替代方法，各種索引方法與啟發(fā)方式被用來(lái)加快搜索的過(guò)程，雖然不能保證與查詢序列比對(duì)的最好的，但是能返回大部分與查詢序列比對(duì)較好的，而且這些方法的效率很高。2.7.1 BLAST及其家族及其家族 序列數(shù)據(jù)庫(kù)搜索最著名且常用的工具之一是BLAST算法，原始的BLAST算法是通過(guò)搜索序列數(shù)據(jù)庫(kù)來(lái)找出最優(yōu)的空間局部比對(duì)。 BLASTP是BLAST算法的一種變種 為了有效地搜索大型

21、數(shù)據(jù)庫(kù)，BLASTP首先將查詢序列打碎成一個(gè)個(gè)單詞，查詢序中所有可能的單詞是通過(guò)查詢序列上滑動(dòng)與單詞等長(zhǎng)的窗口來(lái)得到的。 除了BLASTP，還有BLASTN和BLASTX等等.BLASTP搜索算法概述搜索算法概述2.7.2 FASTA及其相關(guān)算法及其相關(guān)算法 FASTA算法及家族成員能夠進(jìn)行序列間含空位的局部比對(duì)。 FASTA搜索非常細(xì)致，需要時(shí)間也長(zhǎng)的多。 FASTA搜索也是將搜索序列打碎成單詞。對(duì)于氨基酸序列FAMLGFIKYLPGCM，假設(shè)單詞長(zhǎng)度為1，那么：目標(biāo)序列TGFIKYLPGACT，那么對(duì)照表格發(fā)現(xiàn)，甘氨酸（ G ）在第一個(gè)表中位置為5、12，在第二個(gè)表中為 -4、3，再觀察其

22、它出現(xiàn)了很多距離為3的情況，這一現(xiàn)象暗示了一個(gè)可能的合理比對(duì)。通過(guò)兩條序列的偏移表，即可發(fā)現(xiàn)相同的區(qū)域。單詞ACDEFGHIKLMNPQRSTVWY位置2131578431196121014123456789101112TGFIKYLPGACT3-2333-33-4-82103332.7.3 2.7.3 數(shù)據(jù)庫(kù)搜索的比對(duì)得分與統(tǒng)計(jì)顯著性數(shù)據(jù)庫(kù)搜索的比對(duì)得分與統(tǒng)計(jì)顯著性 數(shù)據(jù)庫(kù)搜索引擎一般都為每個(gè)搜索結(jié)果提供P得分和E得分 加入搜索結(jié)果的比對(duì)得分為S，那么P和和E得分得分指的是用于隨機(jī)找出的一條或多條序列，比對(duì)得分大于等于S的可能性。 P與E的值比較低說(shuō)明該結(jié)果與查詢序列具有進(jìn)化上的關(guān)系。2.8 2.8 多重序列比對(duì)多重序列比對(duì) (multiple