第二章數(shù)據(jù)搜索與

兩兩比對序列的比對、比較以及相似序列的數(shù)據(jù)庫搜索等技術(shù)已經(jīng)成為了生物學的基礎(chǔ)任何兩條或多條核苷酸或氨基酸序列之間的比對，從真正意義上講，代表著有關(guān)這些序列進化歷史的明確假設(shè)。直接對相關(guān)氨基酸和核苷酸序列比較的結(jié)果，使得近來對基因序列的信息含量以及功能的了解有了新的進展。序列比對為解決許多關(guān)鍵性的問題提供了重要的信息，這些問題包括：確定新發(fā)現(xiàn)基因的功能；確定基因間、蛋白質(zhì)間乃至物種之間的進化關(guān)系；預測蛋白質(zhì)的結(jié)構(gòu)和功能等本章內(nèi)容點陣圖——圖形方式、直觀地、不考慮空位簡單比對——數(shù)值方式比較兩序列相似度空位打分矩陣動態(tài)規(guī)劃——高效地序列比對全局比對與局部比對——根據(jù)特定需要，對動態(tài)規(guī)劃的改進方法數(shù)據(jù)庫搜索多重序列比對2.1點陣圖

評估兩條序列相似度最簡單的方法之一是利用點陣圖。

第一條被比較的序列排列在點陣圖空間的橫軸，第二條序列則排列在縱軸。點陣空間中兩條序列中的殘基相同時，在對應的位點上畫上圓點，兩條序列間連續(xù)相同的區(qū)域在圖中會形成由圓點組成的上斜線。具有連續(xù)相似區(qū)域的兩條DNA序列的簡單點陣圖AGTCCTGACTGAAGTC相同區(qū)域滑動窗口技術(shù)當對長且相似的序列進行比較時，這樣的點陣圖很快就會變得非常復雜和擁擠。使用滑動窗口代替一次一個位點的比較是解決這個問題的有效方法。假設(shè)窗口大小為10，相似度閾值為8，則每次比較取10個連續(xù)的字符，如相同的字符超過8個，則標記為圓點基于滑動窗口的點矩陣方法可以明顯地降低點陣圖的噪聲，并且明確無誤的指示出了兩條序列間具有顯著相似性的區(qū)域。（a）對人類（Homosapiens）與黑猩猩（Pongopygmaeus）的β球蛋白基因序列進行比較的完整點陣圖。（b）利用滑動窗口對以上的兩種球蛋白基因序列進行比較的點陣圖，其中窗口大小為10個核苷酸，相似度閾值為8。(a)(b)2.2簡單比對比對就是兩條序列字符間簡單的兩兩匹配。比對可以反映出兩條或多條同源序列間的進化關(guān)系。兩天序列的相似度可以用一個數(shù)值來衡量序列給定位置可能發(fā)生的3種變異：插入刪除替換由于在被比較的序列中沒有與被插入或刪除核苷酸序列同源的序列，因此通常在比對時加入空位來反映此類變化最簡單的情況下即不考慮空位，當兩條序列對比時，要做的僅是為較短的序列選擇比對的起始點?？紤]這樣的兩條核苷酸序列：AATCTATA和AAGATA僅有三種比對方式不考慮空位的簡單比對，它的打分函數(shù)是由對比獎勵和罰分的和來決定上例中三個比對從左至右分別是4、1、3匹配得分：1失配得分：02.3空位兩條或多條序列比對時，如果考慮到插入與刪除事件發(fā)生的可能性，那么候選的比對數(shù)量就會大大增加，也就導致了比對的復雜性。上節(jié)中兩條核苷酸序列，在不考慮空位時僅有三種比對，而較短的那條加入了兩個空位后，變產(chǎn)生了28種不同的比對，例如：等等……2.3.1簡單空位罰分對含有空位的比對打分時，空位罰分就必須包含到打分函數(shù)中，空位比對的簡單打分公式如下：例如：假設(shè)匹配得分為1，失配得分為0，空位罰分為-1三種空位比對的得分從左至右分別是1、3、32.3.2起始罰分與長度罰分使用簡單空位罰分對兩條序列進行比對時，經(jīng)常能找到若干同是最優(yōu)的比對。進一步區(qū)分這些比對的方法是找出哪些比對包含較多的不連續(xù)空位，哪些包含數(shù)量較少而長度較長的空位片段?？紤]到競爭假說，那些不可能事件出現(xiàn)較少的比對就最可能是正確的比對。插入/刪除事件假設(shè)兩條序列長度分別是12和9假設(shè)這兩條序列是真正的同源序列，那么它們之間長度的差異可以解釋為(1)較長的序列有核苷酸的插入，或者(2)較短的序列發(fā)生了核苷酸的刪除，或者(3)兩者都發(fā)生了。在不知道原始父輩序列的情況下，無法判斷導致空位的原因是由于一條序列的插入事件還是另一條的刪除事件，通常把這類事件稱為插入/刪除事件。多聯(lián)核苷酸的插入刪除事件相對于單個核苷酸來說會較經(jīng)常發(fā)生。統(tǒng)計結(jié)果表明，兩條序列長度上的差異更可能是單個三聯(lián)核苷酸的插入刪除事件導致的，而多個不連續(xù)核苷酸插入刪除事件的可能性比較小。具有較長連續(xù)空位的比對更能體現(xiàn)進化的觀點，所以在建立比對打分函數(shù)時偏向于通過降低空位罰分來進行獎勵空位罰分（由兩部分相加組成）起始罰分：由序列中產(chǎn)生的新空位串引起長度罰分：根據(jù)缺少的字符數(shù)而定的。預設(shè)長度罰分小于起始罰分，以此建立的打分函數(shù)便能獎勵空位連在一起的比對。假設(shè)起始罰分為-2，長度罰分為-1，匹配得分為+1，失配得分為0，則對于這三個比對，從左至右比對的得分分別是-3，-1，+1在后兩種比對在使用簡單空位罰分時，最后得分都是+3，現(xiàn)在卻得到了不同的分數(shù)。2.4打分矩陣正如空位罰分可以獎勵與進化相關(guān)的的比對，失配罰分也可以用來進一步區(qū)分相似比對。統(tǒng)計結(jié)果表明，兩條同源的序列比對時，某些替換比其他替換常見的多。例：

兩條蛋白質(zhì)序列，其中一條在某一個位置上是丙氨酸，如果該位點被替換成另一個較小的且疏水的氨基酸，比如纈氨酸對蛋白質(zhì)的影響很小，如果被替換成較大且?guī)щ姷臍埢?，比如賴氨酸，那么對蛋白質(zhì)的影響可能就會非常大。直觀的講，比較保守的替換比隨機替換更可能維持蛋白質(zhì)的功能，更不容易被淘汰，因此在打分上更傾向于丙氨酸而不是賴氨酸。打分矩陣（ScoringMatrix）核酸打分矩陣設(shè)DNA序列所用的字母表為

={A，C，G，T}a.單位矩陣b.BLAST矩陣c.轉(zhuǎn)換-顛換矩陣（transition，transversion）（嘌呤：腺嘌呤A，鳥嘌呤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)換-顛換矩陣BLAST矩陣為氨基酸序列比對設(shè)計打分矩陣時，要考慮若干個因素?；瘜W/物理的相似性以及替換率是最常見的兩個：打分矩陣統(tǒng)一可以根據(jù)殘基的疏水性、帶電性、電負性以及大小來得到。例如，具有芳香族功能基團的氨基酸之間配對可能得分很高，而具有非極性功能基團的氨基酸與具有帶電功能基團的氨基酸配對時，就要罰分。另一種基于相似度的矩陣是根據(jù)遺傳編碼來得到：當一種殘基轉(zhuǎn)變成為另一種殘基時，根據(jù)編碼它們的密碼子所對應的核苷酸必須被替換的最小數(shù)目來為殘基打分為了得到打分矩陣，更常用的方法是統(tǒng)計自然界各種氨基酸參加的相互替換率。如果兩者特定的氨基酸間替換發(fā)生的比較頻繁，那么對這兩種殘基比對位點的打分會比較優(yōu)待；反之就要被罰分了常用氨基酸打分矩陣點接受突變（PAM）矩陣：（PointAcceptedMutation）一種基于統(tǒng)計替換率的常用打分矩陣BLOSUM矩陣：通過統(tǒng)計聚類技術(shù)來對相關(guān)蛋白質(zhì)的無空位比對進行分類PAM矩陣構(gòu)建：構(gòu)建一個序列間相似度很高（>85%）的比對計算每個氨基酸j的相對突變率mj相對突變率：某種氨基酸被其他任意氨基酸替換的次數(shù)針對每個氨基酸對i和j，計算氨基酸j被氨基酸i替換的次數(shù)Aij將替換次數(shù)Aij除以相對替換率mj利用每個氨基酸出現(xiàn)的頻度對其進行標準化，并將以上結(jié)果取自然對數(shù)，于是得到PAM-1矩陣中的元素Rij對矩陣中元素進行標準化可以使PAM矩陣通過一個進化的固定單位反映氨基酸間替換發(fā)生的可能性。對于PAM-1，這個單位就是每100個殘基發(fā)生一次替換，即一個PAM單位將PAM矩陣與自身相乘，可以近似得到高階PAM矩陣：PAM2，PAM3…針對不同的進化距離選擇PAM矩陣序列相似度=40%50%60%

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

BLOSUM矩陣另一種常用打分矩陣，通過統(tǒng)計聚類技術(shù)來對相關(guān)蛋白質(zhì)的無空位比對進行分類與PAM矩陣類似，可以根據(jù)親緣關(guān)系的不同來選擇不同的BLOSUM矩陣進行序列比較。然而，BLOSUM矩陣的意義與PAM矩陣正好相反：低階BLOSUM矩陣更多是用來比較親緣較遠的序列。一般來說，BLOSUM-62矩陣適用于比較大約62%相似度的序列；BLOSUM-80更適用于比較相似度為80%左右的序列2.5動態(tài)規(guī)劃:Needleman和Wunsch算法一旦選定了序列比對打分的方法，就可以為尋找最佳比對設(shè)計算法了。最顯而易見的方法就是對每個可能的比對進行窮舉搜索，但這一般是不可行的。比對的目的：在給定打分矩陣的情況下，僅僅獲取最佳比對值僅僅獲取與最佳比對值相對應的序列我們可以用動態(tài)規(guī)劃解決這個問題，即把一個問題分解成計算量合理的子問題，并使用這些子問題的結(jié)果來計算最終答案。S.Needleman與C.Wunsch首次運用動態(tài)規(guī)劃方法來進行序列分析。假設(shè)兩條序列比對：CACGA和CGA，使用統(tǒng)一的空位和失配罰分

，則對于第一個元素比對時，有以下3種可能：給第一條序列加一個空位給第二條序列加一個空位兩條序列都不加空位CACGACGACACGACGACACGACGA如果知道了ACGA與GA最佳比對的得分，就可以立即計算出表中第一行的得分。同樣地，如果知道了表中第二、第三行剩余序列的最佳比對的得分，就可以計算出起始位點的不同的三種比對得分。

動態(tài)規(guī)劃算法通過計算部分序列比對得分并填入一個表格，直到整個序列比對被計算出來，由此得到最優(yōu)比對。第一位點得分待對比的剩余序列CC+1ACGAGA-C-1CACGAGAC--1ACGACGA（匹配得分為1，失配得分為0，空位罰分為-1）動態(tài)規(guī)劃比對ACAGTAG與ACTCG空位罰分為-1匹配獎勵為+1失配得分為00-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG用空位罰分的倍數(shù)對表格第一行與第一列進行初始化每一個格子保存子序列最優(yōu)比對值填充表格0-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG表格中橫向移動表示在縱軸序列中加入一個空位縱向移動表示在橫軸序列中加入一個空位斜對角向移動表示兩序列各自相應的核苷酸進行了比對橫向移動縱向移動斜對角向移動0-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG-1-1=-2，表示在橫向序列中插入一個空位，然后與縱向序列中的A比較，空位罰分-1。-1-1=-2，表示在縱向序列中插入一個空位，然后與橫向序列中的A比較，空位罰分-1。0+1=1，表示兩序列的第一個A進行對比，匹配獎勵1。-2-2110-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG1-1=0，表示在橫向序列中插入一個空位，然后與縱向序列中的C比較，空位罰分-1。-2-1=-3，表示在縱向序列中插入一個空位，然后與橫向序列中的A比較，空位罰分-1。-1+0=-1，表示橫向序列的A與縱向序列的C進行比較，失配得分0。-3-11000-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG-2-1=-3，表示在橫向序列中插入一個空位，然后與縱向序列中的A比較，空位罰分-1。1-1=0，表示在縱向序列中插入一個空位，然后與橫向序列中的C比較，空位罰分-1。-1+0=-1，表示橫向序列的C與縱向序列的A進行比較，失配得分0。0-11-3000-1-2-3-4-5-1-2-3-4-5-6-7ACTCGACAGTAG0-1=-1，表示在橫向序列中插入一個空位，然后與縱向序列中的C比較，空位罰分-1。0-1=-1，表示在縱向序列中插入一個空位，然后與橫向序列中的C比較，空位罰分-1。1+1=2，表示橫向序列的C與縱向序列的C進行比較，匹配獎勵1。-1100-122●●●●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-102ACTCGACAGTAG為了利用打分表重建比對，需要找出一條由表格中最右下角到最左上角的路徑！動態(tài)規(guī)劃途中箭頭指示了部分打分表中的合法路徑，每條路徑代表若干等價最優(yōu)比對路徑自右下至左上排列自來分別是↖↖↖↑↑↖↖

根據(jù)這條線路，可以重建比對，可以得到以下這個得分為2的最優(yōu)比對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-102ACTCGACAGTAG2.6全局對比與局部比對

2.6.1準全部比對到目前為止，所有討論的基本比對算法僅是做了全局比對。而比對兩序列時，這并不總是可取的。假如從AAACACGTGTCT中搜尋段序列ACGT。在若干種兩序列比對中，我們需要的是區(qū)別對待末端空位與序列內(nèi)部空位這種比對稱為準全局比對(semiglobalalignment)準全局比對(1)通過初始化部分打分表，表格第一行與第一列為零；(2)允許表格最后一行與一列橫向與縱向的移動不被罰分；Needleman和Wunsch算法的改進（準全局比對）2.6.2Smith-Waterman算法準全局比對有時有點不能為序列搜索提供所需的適應性，比如給定一條很長的DNA序列，要求找出其中與酵母基因組具有相似部分的任何一條子序列需要進行局部比對例如：兩條序列AACCTATAGCT和GCGATATA，用準全局比對算法，空位罰分為-1，匹配獎勵為+1，失配得分為-1，得：2.6.2Smith-Waterman算法局部比對1981年，由F.Smith和M.Waterman首次提出；動態(tài)規(guī)劃方法通過較少的改動便可以用來識別匹配的子序列，并且忽略匹配區(qū)域之前或之后的失配和空位;局部比對時，表中小于零的位置用零代替;得到的局部比對代表了被比兩條序列間的最佳的匹配子序列；局部比對方法可以識別子序列的匹配，而這是全局與準全局比對不可能做到的。局部比對時，表中小于零的位置用零代替AACCTATAGCTGCGATATA

AACCTATAGCT2.7數(shù)據(jù)庫搜索盡管序列比對是比較兩條已知序列的極為重要的工具，然而序列比對的更為常見的用途是用來搜索大量序列的數(shù)據(jù)庫，以找到與特定序列相似的那些序列。在數(shù)據(jù)庫搜索過程中，由于被搜索序列很長，而且數(shù)量巨大，用簡單而直接的方法將數(shù)據(jù)庫中的每條序列與查詢序列進行比對并返回得分最高的序列難以奏效。作為替代方法，各種索引方法與啟發(fā)方式被用來加快搜索的過程，雖然不能保證與查詢序列比對的最好的，但是能返回大部分與查詢序列比對較好的，而且這些方法的效率很高。2.7.1BLAST及其家族序列數(shù)據(jù)庫搜索最著名且常用的工具之一是BLAST算法，原始的BLAST算法是通過搜索序列數(shù)據(jù)庫來找出最優(yōu)的無空位局部比對。BLASTP是BLAST算法的一種變種為了有效地搜索大型數(shù)據(jù)庫，BLASTP首先將查詢序列打碎成一個個單詞，通過查詢序列上滑動與單詞等長的窗口，來獲取查詢序列中所有可能的單詞。那些由最常見氨基酸組成的單詞會被棄之一邊，然后從數(shù)據(jù)庫中搜索余下單詞出現(xiàn)的情況每當從數(shù)據(jù)庫中找到一個單詞的匹配，就從單詞兩端延伸該匹配，直到比對得分低于給定的閾值為止除了BLASTP，還有BLASTN和BLASTX等等….BLASTP搜索算法概述2.7.2FASTA及其相關(guān)算法FASTA算法及家族成員能夠進行序列間含空位的局部比對。FASTA搜索非常細致，需要時間也長的多。FASTA搜索也是將搜索序列打碎成單詞。對于基因組序列，單詞一般只4至6個核苷酸，而對于多肽，單詞長度一般為1至2個殘基。下一步為查詢序列建立一個表格，表格中記錄了各個單詞在序列中出現(xiàn)的位置對于氨基酸序列FAMLGFIKYLPGCM，假設(shè)單詞長度為1，那么：為了與目標序列比較，我們建立了第二個表格，該表格用來比較目標序列與查詢序列中氨基酸的相對位置目標序列TGFIKYLPGACT，那么123456789101112TGFIKYLPGACT3-2333-33-4-8210333單詞ACDEFGHIKLMNPQRSTVWY位置2131578431196121014對照表格發(fā)現(xiàn)，甘氨酸（G）在第一個表中位置為5、12，在第二個表中為-4、3，再觀察其它出現(xiàn)了很多距離為3的情況，這一現(xiàn)象暗示了一個可能的合理比對。通過兩條序列的偏移表，即可發(fā)現(xiàn)相同的區(qū)域。然后利用Smith-Waterman算法對它們進行比對。因為這是對相似序列的已知區(qū)域進行比對，所以比起完全使用動態(tài)規(guī)劃算法來進行查詢序列與所有可能目標序列直接的比對，F(xiàn)ASTA要快很多123456789101112TGFIKYLPGACT3-2333-33-4-82103332.7.3數(shù)據(jù)庫搜索的比對得分與統(tǒng)計顯著性數(shù)據(jù)庫搜索總會產(chǎn)生一個結(jié)果的，如果沒有更多的信息，被找出的序列不能認為與搜索序列有關(guān)比對得分可以基本說明搜索結(jié)果與查詢序列間的相似度，然而由于數(shù)據(jù)庫搜索算法不同，比對打分標準并不統(tǒng)一，而且得分本身并不能充分指明兩序列間的關(guān)系假設(shè)某個數(shù)據(jù)庫搜索結(jié)果的比對得分為S，那么可以問這樣一個合理的問題：“假如有一組與查詢序列不相關(guān)的序列（甚至是隨機序列），那么在這些序列中隨機找到一個得分同為S的比對的概率有大的？”為了回答這個問題，數(shù)據(jù)庫搜索引擎一般都為每個搜索結(jié)果提供P得分和E得分E得分指的就是隨機找出的序列的期望數(shù)目，這些序列與查詢序列比對得分能大于等于SP得分指的是對于隨機找出的一條或多條序列，其比對得分大于等于S的可能性P與E的值比較低說明該結(jié)果與查詢序列具有進化上的關(guān)系。當E值不高于10-3時，搜索結(jié)果通常被認為具有統(tǒng)計上的顯著性。對搜索算法來講，得到的匹配所具有的E值在數(shù)量級上為10-50，這一點并不罕見，它意味著查詢序列與搜索結(jié)果間具有進化關(guān)系的可能性非常大2.8多重序列比對

(multiplesequencealignment)到目前為止，所討論的比對算法都是為進行序列兩兩比較而設(shè)計的，然而同時比對多條序列也是很重要的。當統(tǒng)計一組序列的替換率時，多重序列比對通常比兩兩比對更合適，因為多重比對盡可能地多考慮到了序列中的空位。多重比對對于打分矩陣的建立也很重要，比如本章前面討論的PAM與BLOSUM矩陣。但是由于隨著比對序列數(shù)量的增大，多重比對算法的復雜度呈指數(shù)級增加，就算是使用超級計算機或者工作站的分布式網(wǎng)絡(luò)，要對20條以上具有一般長度與復雜度的序列進行比對，仍是非常棘手的問題。因此，利用啟發(fā)式的比對方法被提出來，這類方法不能保證產(chǎn)生一個最優(yōu)比對，但是能找出一個近似最優(yōu)的比對。本章總結(jié)兩條或多條基因或氨基酸序列間的比對代表著一個有關(guān)這些序列從共同祖先開始的進化路徑的假設(shè)。盡管真正的進化路徑無法被明確無誤的推斷出，但序列比對算法可以識別隨機發(fā)生率很低的那些比對，多種技術(shù)可以用來左右打分函數(shù)，例如PAM與BLOSUM。Needleman與Wunsch首先提出的全局比對算法以及Smith與Waterman提出的局部比對算法已經(jīng)成為了眾多數(shù)據(jù)庫搜索算法的基礎(chǔ)，包括BLASTX等工具。這些算法利用了索引、啟發(fā)式和快速比較等技術(shù)，使得整個數(shù)據(jù)庫中的序列能與查詢序列在很短的時間內(nèi)完成。習題2.1

在怎樣的情況下，分子生物學家會希望進行序列兩兩