生物序列比對(duì)中的算法課件

生物序列比對(duì)中的算法中科院計(jì)算所生物信息學(xué)實(shí)驗(yàn)室華大—曙光聯(lián)合實(shí)驗(yàn)室張法提綱背景知識(shí)序列相似性的比較兩條序列的比對(duì)問(wèn)題多序列的比對(duì)問(wèn)題一些啟發(fā)式的算法生物序列比對(duì)中的并行算法DNA(1)脫氧核糖核酸DNA的分子組成核甘(nucleotides)磷酸鹽(phosphate)糖(sugar)一種堿基腺嘌呤(Adenine)鳥(niǎo)嘌呤(Guanine)胞嘧啶(Cytosine)胸腺嘧啶(Thymine)DNA(2)堿基的配對(duì)原則A(腺嘌呤)—T(胸腺嘧啶)C(鳥(niǎo)嘌呤)—G(胞嘧啶)一個(gè)嘌呤基與一個(gè)嘧啶基通過(guò)氫鍵聯(lián)結(jié)成一個(gè)堿基對(duì)。DNA分子的方向性5'→3'DNA(3)DNA的雙螺旋結(jié)構(gòu)

堿基對(duì)之間的互補(bǔ)能力DNA(4)DNA的復(fù)制在DNA解旋酶的作用下兩條鏈分離開(kāi)，分別作為一個(gè)模板，在聚合酶的作用下合成一條新鏈。RNA、轉(zhuǎn)錄和翻譯RNA(核糖核酸)：?jiǎn)捂溄Y(jié)構(gòu)、尿嘧啶U代替胸腺嘧啶T、位于細(xì)胞核和細(xì)胞質(zhì)中。轉(zhuǎn)錄：DNA鏈→RNA鏈信使RNA(mRNA)，啟動(dòng)子。翻譯：mRNA上攜帶遺傳信息在核糖體中合成蛋白質(zhì)的過(guò)程。變異進(jìn)化過(guò)程中由于不正確的復(fù)制，使DNA內(nèi)容發(fā)生局部的改變。變異的種類主要有以下三種：替代(substitution)插入或刪除(insertionordeletion)

indel重排(rearrangement)蛋白質(zhì)由氨基酸依次鏈接形成在生物體中總共有20種氨基酸。蛋白有十分復(fù)雜的三維結(jié)構(gòu)。其三維機(jī)構(gòu)決定了蛋白質(zhì)的功能?；蚴裁词腔?？DNA上具有特定功能的一個(gè)片斷，負(fù)責(zé)一種特定性狀的表達(dá)。一般來(lái)講，一個(gè)基因只編碼一個(gè)蛋白質(zhì)?；蚪M任何一條染色體上都帶有許多基因，一條高等生物的染色體上可能帶有成千上萬(wàn)個(gè)基因，一個(gè)細(xì)胞中的全部基因序列及其間隔序列統(tǒng)稱為genomes（基因組）。DNA上的基因

基因基因的編碼基因編碼是一個(gè)邏輯的映射，表明存儲(chǔ)在DNA和mRNA中的基因信息決定什么樣的蛋白質(zhì)序列。每個(gè)堿基三元組稱為一個(gè)密碼子(codon)堿基組成的三元組的排列共有43＝64種，而氨基酸共有20種類型，所以不同的密碼子可能表示同一種氨基酸。

帶來(lái)的問(wèn)題序列排列問(wèn)題基因組的重排問(wèn)題蛋白質(zhì)結(jié)構(gòu)和功能的預(yù)測(cè)基因(外顯子、內(nèi)含子)查找問(wèn)題序列裝配(SequenceAssembly)問(wèn)題動(dòng)機(jī)在生物學(xué)的研究中，將未知序列同已知序列進(jìn)行比較分析已經(jīng)成為一種強(qiáng)有力的研究手段，生物序列相似性比較中絕大部分的問(wèn)題在計(jì)算機(jī)科學(xué)領(lǐng)域中主要體現(xiàn)為字符串的匹配和查找。圖譜分析生物序列片斷的拼接基因區(qū)域的預(yù)測(cè)生物序列同源的比較蛋白質(zhì)結(jié)構(gòu)和功能預(yù)測(cè)兩條序列比對(duì)問(wèn)題的分類全局比對(duì)(GlobalAlignment)局部比對(duì)(LocalAlignment)空位罰分(GapPenalty)全局比對(duì)(1)－定義定義1：兩個(gè)任意的字符x和y，(x,y)表示表x和y比較時(shí)的分值。

(x,x)=2,(x,y)=(x,-)=(-,y)=-1定義2：S=s1…sn和T=t1…tm，其全局比對(duì)A可以用序列S′和T′來(lái)表示，其中：(1)|S′

|=|T′|；

(2)將S′和T′中的空字符除去后所得到的序列分別為S和T；比對(duì)A的分值Score為：全局比對(duì)(2)－原始算法輸入：序列S和T，其中|S|=|T|=n

輸出：S和T的最優(yōu)比對(duì)fori=0tondofor(S的所有的子序列A，其中|A|=i)dofor(T的所有的子序列B，其中|B|=i)do

……全局比對(duì)(3)動(dòng)態(tài)規(guī)劃(DynamicProgramming)Bellman在50年代提出的理論基礎(chǔ)－最優(yōu)化原理弱點(diǎn)：thecurseofdimensionalitySmith-WatermanAlgorithm全局比對(duì)(4)Smith-Waterman算法計(jì)算出兩個(gè)序列的相似分值，存于一個(gè)矩陣中。(editmatrix、DP矩陣)根據(jù)此矩陣，按照回溯的方法尋找最優(yōu)的比對(duì)序列。全局比對(duì)(5)前提條件遞歸關(guān)系計(jì)算editmatrix：fori=0tondoforj=0tomdoCalculateV(i,j)usingV(i-1,j-1),V(i,j-1),V(i-1,j)end全局比對(duì)(6)計(jì)算完editmatrix后，得到序列比對(duì)的最優(yōu)分值，通過(guò)回溯（Traceback）的方法可獲得序列的最優(yōu)比對(duì)序列。回溯的算法：for(i=|S|，j=|T|;i>0&&j>0;){if(V[i,j]=V[i–1,j–1]+σ(S[i],T[j])){i––;j––;}elseif(V[i,j]=V[i–1,j]+σ(S[i],–)){i––;insert(‘–’,T,j);}elseif(V[i,j]=V[i,j–1]+σ(–,T[i])){j––;insert(‘–’,S,i);}}例：S=“acgctg”和T=“catgt”

(x,x)=2,(x,y)=(x,-)=(-,y)=-1

ji01c2a3t4g5t00-1-2-3-4-51a-1-110-1-22c-2100-1-23g-300-1214c-4-1-1-1115t-5-2-21036g-6-3-3032三種可能的最優(yōu)比對(duì)序列：S:acgctg-T:-c–atgtS:acgctg-T:-ca–tgtS:-acgctgT:catg-t-

局部比對(duì)(1)兩條序列在一些局部的區(qū)域內(nèi)具有很高的相似度。在生物學(xué)中局部比對(duì)比全局比對(duì)更具有實(shí)際的意義。局部比對(duì)(2)前提條件：

V(i,0)=0;

V(0,j)=0;遞歸關(guān)系：

找出i*和j*，使得：

局部比對(duì)(3)對(duì)全局比對(duì)策略稍作修改可得到局部最優(yōu)比對(duì)算法。比對(duì)的路徑不需要到達(dá)搜索圖的盡頭,如果某種比對(duì)的分值不會(huì)因?yàn)樵黾颖葘?duì)的數(shù)量而增加時(shí)，這種比對(duì)就是最佳的。依賴于記分系統(tǒng)的性質(zhì)：因?yàn)槟撤N路徑的記分會(huì)在不匹配的序列段減少,當(dāng)分值降為零時(shí)，路徑的延展將會(huì)終止，一個(gè)新的路徑就會(huì)產(chǎn)生。局部比對(duì)(4)S=“abcxdex”，T=“xxxcde”記分函數(shù)(x,y)：

(x,x)=2,(x,y)=(x,-)=(-,y)=-1

ji01x2x3x4c5d6e000000001a00000002b00000003c00002104x02221105d01111326e00000257x0222114S=“abcxdex”，T=“xxxcde”

局部最優(yōu)比對(duì)是：

cxde

c-de或

x-de

xcde

空位罰分(1)空位:序列中任意連續(xù)的盡可能長(zhǎng)的空格?？瘴坏囊胧菫榱搜a(bǔ)償那些插入或缺失，但是在序列的比對(duì)中引入的空位不能太多，否則會(huì)使序列的排列變得面目全非。每引入一個(gè)空位，比對(duì)的分值都會(huì)有所扣除，常見(jiàn)的罰分規(guī)則主要有兩種：權(quán)值恒定模型仿射罰分模型空位罰分(2)權(quán)值恒定模型：在每個(gè)空位中的空格的分值為零，即：(x,-)=(-,y)=0

比對(duì)的分值為：其中，Wg為開(kāi)放一個(gè)空位的罰分空位罰分(3)仿射罰分模型(AffineGapModel)

用一個(gè)附加的罰分比例去乘空位的長(zhǎng)度Wg+q×Ws

比對(duì)的分值為：空位罰分(4)初始條件：

V(0,0)=0;

V(i,0)=E(i,0)=Wg

+iWs;

V(0,j)=F(0,j)=Wg

+jWs;遞歸條件：

V(i,j)=max{G(i,j),E(i,j),F(i,j)};

G(i,j)=V(i-1,j-1)+σ(S[i],T[j]);

E(i,j)=max{E(i,j-1)+Ws,V(i,j-1)+Wg+Ws}

F(i,j)=max{F(i-1,j)+Ws,V(i-1,j)+Wg+Ws}.利用動(dòng)態(tài)規(guī)劃計(jì)算序列最優(yōu)比對(duì)的算法的復(fù)雜度分析：時(shí)間復(fù)雜度；O(mn)

多序列比對(duì)(1)兩條序列比對(duì)問(wèn)題的一般化推廣動(dòng)機(jī)：攜帶更多的消息。DNA或蛋白質(zhì)數(shù)據(jù)庫(kù)容量的指數(shù)級(jí)的增長(zhǎng)，即使使用很簡(jiǎn)單的記分函數(shù)也很難找到一種在有效時(shí)間內(nèi)的解決方法，而幾乎所有的近似算法和許多的啟發(fā)式算法，實(shí)際上都是在算法的計(jì)算速度和獲得最佳比對(duì)結(jié)果的敏感性之間尋找一種權(quán)衡策略。多序列比對(duì)(2)rigorous算法兩條序列多條序列，NPhardtree_based算法和iterative算法首先從序列中找出兩條相似度最大的比對(duì)，然后按照相似度遞減的順序連續(xù)添加一些序列到最優(yōu)的比對(duì)序列中。序列非常接近原始算法基礎(chǔ)上的近似算法，但是它們也是非常耗時(shí)的。多序列比對(duì)(3)記分方法：用函數(shù)δ(x,y)來(lái)計(jì)算字符x和y之間的距離，兩個(gè)序列的比對(duì)的距離分值我們用V來(lái)表示：

k條序列比對(duì)的分值：為k條序列中任意兩條序列(共有Ck2條)的分值(距離)V之和，用SP(Sum_of_Pairs)來(lái)表示:動(dòng)態(tài)規(guī)劃的方法在多序列比對(duì)中的時(shí)間復(fù)雜度為O(2n)k中心星算法輸入：一組含有k條序列的集合?

找出序列St，St∈?，使得∑i≠tD(

Si,St)的值最小，令A(yù)={St}逐次地添加Si∈?-{St}到A中，并使Si與St的比對(duì)的值最??；假設(shè)S1，S2，…Si-1已添加到A中，由于在分別和St進(jìn)行比對(duì)的過(guò)程中需要加入一些空格，故此時(shí)A為：A={S1’，S2’，…Si-1’，S’t}。添加Si到A中，按照兩條序列比對(duì)的動(dòng)態(tài)規(guī)劃算法比較S’t和Si，分別產(chǎn)生新的序列St’’和Si’，再按照St’’中添加空格的位置調(diào)節(jié)序列S1’，S2’，…Si+1’為S1’’，S2’’，…Si-1’’，并用St’’替換St。啟發(fā)式算法-FASTA基本思想是：一個(gè)能夠揭示出真實(shí)的序列關(guān)系的比對(duì)至少包含一個(gè)兩個(gè)序列都擁有的字(片斷)，把查詢序列中的所用字編成索引，然后在數(shù)據(jù)庫(kù)搜索時(shí)查詢這些索引，以檢索出可能的匹配，這樣那些命中的字很快被鑒定出來(lái)。

確定參數(shù)ktup，在兩個(gè)序列中查找長(zhǎng)度為ktup的、相匹配的片段(增強(qiáng)點(diǎn))。為了提高速度，可以通過(guò)查詢表格或hash表來(lái)完成，然后在表格中搜索與另一條序列相匹配的、長(zhǎng)度為ktup的片段。在同一條對(duì)角線中臨近的增強(qiáng)點(diǎn)成為一個(gè)增強(qiáng)段。每一個(gè)增強(qiáng)點(diǎn)都賦予一個(gè)正的分值，一個(gè)增強(qiáng)段中相鄰的兩個(gè)增強(qiáng)點(diǎn)之間的不匹配區(qū)域賦予一定的負(fù)值。一個(gè)增強(qiáng)段對(duì)應(yīng)于一段相匹配的子序列，分值最高的段被標(biāo)記為init1。

引入indel。把那些沒(méi)有重疊(non-overlap)的增強(qiáng)段拼接起來(lái)(增強(qiáng)段的分值之和減去空位處罰)。分值最高的區(qū)域記為initn。對(duì)最有可能的匹配序列進(jìn)一步評(píng)分：以增強(qiáng)段init1所在的對(duì)角線為中心，劃分出一個(gè)較狹窄的對(duì)角線帶，利用S-W算法，來(lái)獲得分值最高的局部比對(duì)，記作opt。決定采用initn或opt的分值，前者敏感度低但速度快。FASTA對(duì)每一個(gè)檢索到的比對(duì)都提供一個(gè)統(tǒng)計(jì)學(xué)顯著性的評(píng)估，以判斷該比對(duì)的意義。FASTA對(duì)DNA序列搜索的結(jié)果要比對(duì)蛋白質(zhì)序列搜索的結(jié)果更敏感。它對(duì)數(shù)據(jù)庫(kù)的每一次搜索都只有一個(gè)最佳的比對(duì)，一些有意義的比對(duì)可能被錯(cuò)過(guò)。

啟發(fā)式算法-BLAST基本思想是：通過(guò)產(chǎn)生數(shù)量更少的但質(zhì)量更好的增強(qiáng)點(diǎn)來(lái)提高速度。BALST算法是建立在嚴(yán)格的統(tǒng)計(jì)學(xué)的基礎(chǔ)之上的。它集中于發(fā)現(xiàn)具有較高的相似性的局部比對(duì)，且局部比對(duì)中不能含有空位。由于局部比對(duì)的限制條件，在大多數(shù)情況下比對(duì)會(huì)被分解為若干個(gè)明顯的HSP(High-scoreSequencePairs)。首先確定一個(gè)終止值S、步長(zhǎng)參數(shù)w和一個(gè)閾值t，S值通常是基于統(tǒng)計(jì)學(xué)的原理指明一個(gè)預(yù)期的終止E值，然后軟件會(huì)在考慮搜索背景性質(zhì)的基礎(chǔ)上計(jì)算出合適的S值。使要比對(duì)的序列中包含一個(gè)分值不小于S的HSP。引入鄰近字串的思想：不需要字串確切地匹配，當(dāng)有一個(gè)字串的分值高于t時(shí)，BALST就宣稱找到了一個(gè)選中的字串。為了提高速度，允許較長(zhǎng)的字串長(zhǎng)度W。W值很少變化，這樣，t值就成為權(quán)衡速度和敏感度的參數(shù)。一個(gè)字串選中后，程序會(huì)進(jìn)行沒(méi)有空位的局部尋優(yōu)，比對(duì)的最低分值是S，當(dāng)比對(duì)延伸時(shí)會(huì)遇到一些負(fù)的分值，使得比對(duì)的分值下降，當(dāng)下降的分值小于S時(shí)，命中的延伸就會(huì)終止。這樣系統(tǒng)會(huì)減少消耗于毫無(wú)指望的選中延伸的時(shí)間，使系統(tǒng)的性能得以改進(jìn)。BLAST的改進(jìn)在1997年提出了對(duì)BLAST程序的改進(jìn)算法，提高了搜索速度、敏感度和實(shí)用性?？商幚黹g隔(gap)的gappedBLAST算法PSI-BLAST算法對(duì)一個(gè)選中字串長(zhǎng)度標(biāo)準(zhǔn)的延伸利用profile(表頭文件)的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行搜索算法算法擴(kuò)大步長(zhǎng)，以步長(zhǎng)為2w來(lái)搜索。允許位于不同的對(duì)角線的兩個(gè)片段拼接在一起。位于不同對(duì)角線的兩個(gè)片段拼接在一起的前提條件是：拼接后片段的分值不小于某一個(gè)終止值。執(zhí)行通常的BLAST算法，使用一種不同的記分方式，根據(jù)高度顯著比對(duì)(HSPs)的最高分值建立一個(gè)最初的profile。根據(jù)該profile反復(fù)利用BLAST算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索，這一步實(shí)際上是根據(jù)表頭文件的統(tǒng)計(jì)結(jié)果擴(kuò)展局部比對(duì)。這一過(guò)程是反復(fù)進(jìn)行的，直到再?zèng)]有發(fā)現(xiàn)新的有意義的匹配為止。由于在每一輪都會(huì)有新的片段加入，因此在操作過(guò)程中profile需要在每一個(gè)循環(huán)結(jié)束之后更新。為適應(yīng)同源比較的不通情況，BLAST得到了各種各樣的補(bǔ)充和發(fā)展，形成了一個(gè)程序家族。程序名檢索序列數(shù)據(jù)庫(kù)序列BLASTP蛋白質(zhì)蛋白質(zhì)BLASTN核苷酸核苷酸BLASTX核苷酸蛋白質(zhì)TBLASTN蛋白質(zhì)核苷酸

SubstitutionMatrixPAM250BLOSUM62在SUN10000上進(jìn)行BLAST的測(cè)試：8CPU8GmemoryVERSION:BLASTN2.2.1[Jul-12-2001]blastall-pblastn-i$query.seq–d/mnt/database/public/NCBI/ftp.ncbi.nlm.nih.gov/BLAST/nt/2001-12-02/nt-e1e-10-o$result.out-a4>rzy_63001.y1.abdCHROMAT_FILE:rzy_63001.y1.abdPHD_FILE:rzy_63001.y1.abd.phd.1CHEM:termDYE:ETTIME:ThuJun2116:03:572001TAAAGGAGAATGACTCTTTTAAGTCATAGCTTGCTGNCATTAGTCGTTTGAAAGGTCGAGTGCTCAATATCTTAACCCTTTTACCTTTTTTGAAAAACACTAGGCTAGATAGATGCCATATCGGATTGAGGGGTTATTATTGGAGATTTGGAGGGGCATTTTTTTTTAGTTATTTTTTTTCTAAATTTTTTGGATGGTGAGGCTATATGAGGTGCTCTTGAAGATGCTCTCCCTTTATGTCCGAGTGATTGAATGGTATAATTTGCAACACACAAGCTTGCTTTTACAGAACTCATGGACTTCTTTACTTATATCGTATAATTCGCAGGAATATTTCGCGAAATGGGGAGAGCAAGGCACGGTGGATCTGAAACGCGAGCTCGACCTCCTCATCCTGACGATCGCGAGCCGCGTCCTCCTCGGCAAGGAGGTTAGGGAGACCATGTTCGCCGACGTCGTGGCATCCTTCCACGAGCTCATGGACAACAGCATGCACCTCATCAGCCTCTGCTTCCCCAACCTCCCGATCCCGCGGCACCGCCGGCGCGACACGGCGTCCGCTAGGCTCAAGGAGCTCTTCTCCCGTGCCATCCAGCTTCGCCGCGGCTCCGGCCGCGCCGAGGACGACGTGCTCCAGCGGTTCTTGGATCCAGGTACAGGGACGGCntdatabase:

mnt/database/public/NCBI/ftp.ncbi.nlm.nih.gov/BLAST/nt/2001-12-02/ntSize:4.8G1′030′000個(gè)reads

借助于一些比最初的動(dòng)態(tài)規(guī)劃算法更快的啟發(fā)式算法。借助硬件來(lái)完成動(dòng)態(tài)規(guī)劃的算法采用高性能計(jì)算系統(tǒng)，把問(wèn)題有效地分配到多個(gè)處理器上運(yùn)行，最后再把各處理器的運(yùn)算結(jié)果收集起來(lái)生物序列比對(duì)中的

并行算法兩條序列比對(duì)的并行算法根據(jù)序列的相似性比較，找出兩者的最佳匹配找出從一條序列轉(zhuǎn)化到另一條序列的最佳路徑核心：動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃中的數(shù)據(jù)相關(guān)Lander的處理方法如果已知第i-1和i-2行反對(duì)角線上的各項(xiàng)值，那么第i行反對(duì)角線上各項(xiàng)的值可以并行計(jì)算?！鳌睢鳌睢鳌睢鳌睢??????D12D21D31D11D22D13Dm,n●●●處理器01m時(shí)間步12m+n-2m+n-1Smith-Waterman的并行處理Row-Wavefront算法和DiagonalWavefront算法

Row-Wavefront算法是讓每個(gè)處理器順序處理動(dòng)態(tài)規(guī)劃矩陣中的每一行，當(dāng)一個(gè)處理器檢測(cè)到它所需要的上一行矩陣的元素還沒(méi)有計(jì)算出來(lái)時(shí)，該處理器就阻塞自己，直到所需要的元素計(jì)算出來(lái)。

處理器1處理器2處理器3序列S序列TSmith-Waterman的并行處理Row-Wavefront算法和DiagonalWavefront算法

DiagonalWavefront算法中所有的處理器同時(shí)沿著矩陣的一條反對(duì)角線進(jìn)行計(jì)算，當(dāng)一條反對(duì)角線的元素全部計(jì)算完，才轉(zhuǎn)到下一條反對(duì)角線計(jì)算。當(dāng)一個(gè)處理器空閑的時(shí)候，它從當(dāng)前的反對(duì)角線上尋找一個(gè)還沒(méi)有計(jì)算的元素進(jìn)行計(jì)算。這種算法沒(méi)有嚴(yán)格的處理器計(jì)算順序序列T序列SHuang的處理方法采用了分而治之的策略對(duì)回溯算法進(jìn)行了改進(jìn):按照中間的一條反對(duì)角線來(lái)分割動(dòng)態(tài)規(guī)劃矩陣。(0,0)r(