序列分析PPT資料

第四章序列(xùliè)分析第一頁，共62頁。第三節(jié)序列(xùliè)多重比對第二頁，共62頁。目的：發(fā)現(xiàn)(fāxiàn)多個序列的共性發(fā)現(xiàn)(fāxiàn)與結(jié)構(gòu)和功能相關(guān)的保守序列片段設(shè)：有k個序列s1,s2,...,sk，每個序列由同一個字母表中的字符組成，k大于2。通過插入操作，使得各序列達(dá)到一樣的長度。第三頁，共62頁。1、SP（Sum-of-Pairs）模型(móxíng)評價(jià)多重序列(xùliè)比對的結(jié)果第四頁，共62頁。按照每個對比的列進(jìn)行打分，然后加和處理每一列： —k個變量的打分函數(shù) —用一個k維數(shù)組來表示該顯式函數(shù)（類似于打分矩陣）期望： 函數(shù)在形式上應(yīng)該簡單 具有(jùyǒu)統(tǒng)一的形式 不隨序列的個數(shù)而發(fā)生形式變化第五頁，共62頁。其中，c1,c2,…,ck是一列(yīliè)中的k個字符，p是關(guān)于一對字符相似性的打分函數(shù)。逐對加和SP（sum-of-pairs）函數(shù)(hánshù)逐對計(jì)算p(1,2)，p(1,3)，...，p(1,8)，p(2,3)，p(2,4)，...，p(2,8)，...，p(7,8)的所有(suǒyǒu)得分（-7-6-5-4-3-2-1）+2=-26第六頁，共62頁。另一種計(jì)算方式：先處理每一個序列(xùliè)對 在處理序列(xùliè)對時(shí)，逐個計(jì)算字符對，最后加和 則SP得分模型的計(jì)算公式如下：是一個(yīɡè)多重比對ij是由推演出來的序列si和sj的兩兩比對第七頁，共62頁。第八頁，共62頁。2、多重比對的動態(tài)規(guī)劃(guīhuà)算法

多重序列比對的最終目標(biāo)是通過(tōngguò)處理得到一個得分最高（或代價(jià)最?。┑男蛄袑Ρ扰帕校瑥亩治龈餍蛄兄g的相似性和差異。第九頁，共62頁。

前趨節(jié)點(diǎn)(jiédiǎn)的個數(shù)等于2k-1第十頁，共62頁。

假設(shè)以k維數(shù)組A存放超晶格，則計(jì)算(jìsuàn)過程如下：a[0,0,…,0]=0a[i]=max{a[i-b]+SP-score(Column(s,i,b))}(3-37)(3-38)

ifbj=1ifbj=0第十一頁，共62頁。

圖3.17三維晶格節(jié)點(diǎn)計(jì)算(jìsuàn)依賴關(guān)系問題： 計(jì)算量巨大(jùdà) 時(shí)間復(fù)雜度為O(2ki=1,...,ksi) ↓ O(2kNk)第十二頁，共62頁。3、優(yōu)化計(jì)算方法標(biāo)準(zhǔn)動態(tài)規(guī)劃算法存在的問題：搜索空間大剪枝技術(shù)：將搜索空間限定在一個較小的區(qū)域(qūyù)范圍內(nèi)。若問題是搜索一條得分最高（或代價(jià)最?。┑穆窂剑瑒t在搜索時(shí)如果當(dāng)前路徑的得分低于某個下限（或累積代價(jià)已經(jīng)超過某個上限），則對當(dāng)前路徑進(jìn)行剪枝，即不再搜索當(dāng)前路徑的后續(xù)空間。第十三頁，共62頁。經(jīng)過特定斷點(diǎn)的最優(yōu)比對算法：設(shè)有兩條序列s、t，已知它們的兩個斷點(diǎn)分別是i、j經(jīng)過特定斷點(diǎn)（i、j）的最優(yōu)比對可分為(fēnwéi)兩個部分：——0:s:i與0:t:j的最優(yōu)比對——i:s:m與j:t:n的最優(yōu)比對序列(xùliè)S:序列(xùliè)t:

ji第十四頁，共62頁。為了得到特定斷點(diǎn)的最優(yōu)比對，用兩個矩陣A和B a[i,j]=sim(0:s:i,0:t:j) b[i,j]=sim(i:s:m,j:t:n)矩陣A的計(jì)算和標(biāo)準(zhǔn)算法(suànfǎ)一樣矩陣B的計(jì)算則是反方向的，即先對B的最后一行和最后一列進(jìn)行初始化，然后反向推進(jìn)到（0，0）。矩陣A與B的和C=A+B包含了在特定斷點(diǎn)（i、j）的最優(yōu)比對得分。稱C矩陣為總得分矩陣，而A、B分別是前綴和后綴的得分矩陣。根據(jù)C的最大值，可非常容易地找出最優(yōu)比對所對應(yīng)的路徑。第十五頁，共62頁。-ATTCGGGATTC--

（c）圖（a）前綴(qiánzhuì)矩陣；（b）總得分矩陣；（c）最優(yōu)比對（a） （b）第十六頁，共62頁。定理3-1：設(shè)是關(guān)于(guānyú)s1,s2,...,sk的最優(yōu)比對，如果SP-score()L，則score(ij)Lij 其中Lij=L-(sim(sx,sy)) x<y,(x,y)(i,j)分析(fēnxī)一個節(jié)點(diǎn)是否處于可能最有路徑上即判斷一個節(jié)點(diǎn)是否是相關(guān)的判斷依據(jù)： C=A+B元素的值 超晶格中的一個節(jié)點(diǎn)i=(i1,i2,…,ik) 如果對于所有的1x<yk，i滿足 cxy[ix,iy]Lxy 則i是相關(guān)的第十七頁，共62頁。4、星形比對星形比對的基本思想是：在給定的若干序列中，選擇一個(yīɡè)核心序列，通過該序列與其它序列的兩兩比對形成所有序列的多重比對，從而使得在核心序列和任何一個(yīɡè)其它序列方向的投影是最優(yōu)的兩兩比對。利用標(biāo)準(zhǔn)的動態(tài)規(guī)劃方法求出所有si和sc的最優(yōu)兩兩比對時(shí)間為O（kn2）將這些兩兩比對聚集起來并采用“只要是空白，則永遠(yuǎn)是空白”的原則。第十八頁，共62頁。scs1s2…sk(sc,s1)(sc,s2)…(sc,sk)兩兩比對多重比對第十九頁，共62頁。如何選擇核心序列？嘗試將每一個序列分別作為(zuòwéi)核心序列，進(jìn)行星形多重序列比對，取比對結(jié)果最好的一個。另一種方法是計(jì)算所有的兩兩比對，取下式值最大的一個：sim(si,sc) 第二十頁，共62頁。例如(lìrú)，有5個序列：s1=ATTGCCATTs2=ATGGCCATTs3=ATCCAATTTTs4=ATCTTCTTs5=ACTGACC sc=s1ATTGCCATTATTGCCATT--ATTGCCATTATTGCCATTATGGCCATTATC-CAATTTTATCTTC-TTACTGACC--

ATTGCCATT--ATGGCCATT--ATC-CAATTTTATCTTC-TT--ACTGACC----第二十一頁，共62頁。引理：對于(duìyú)所有的1≤i，j≤k，,ij,有 dc(si,sj)≤D(si,sc)+D(sc,sj)（3-43）定理(dìnglǐ)（3-44）星形比對是一種近似的方法，可以證明，用該方法所得到多重序列(xùliè)比對的代價(jià)不會大于最優(yōu)多重序列(xùliè)比對代價(jià)的兩倍第二十二頁，共62頁。5、樹形比對k個待比對的序列→具有k個葉節(jié)點(diǎn)的樹每個葉節(jié)點(diǎn)對應(yīng)一個序列將序列賦予(fùyǔ)樹的內(nèi)部節(jié)點(diǎn)，可以計(jì)算樹中每個分支的權(quán)值。權(quán)值代表對應(yīng)分支連接的兩個序列之間的相似性。所有權(quán)值的和就是這棵樹尋找一種樹的內(nèi)部節(jié)點(diǎn)序列賦予(fùyǔ)方式，使得樹的得分最大。第二十三頁，共62頁。將CT、CG、CT分別賦予節(jié)點(diǎn)x、y、z，則樹的得分為(fēnwéi)8。這里假設(shè)如果a=b，則p(a,b)=1，否則p(a,b)=0，p(a,-)=-1。CTCGCT多重序列(xùliè)比對→兩兩序列(xùliè)比對 →合并兩個比對（比對的比對）第二十四頁，共62頁。 Alignmentofalignments,AA算法假設(shè)(jiǎshè)：有兩個多重序列比對1、2，1代表序列s1、s2、…、si的多重比對，2代表序列t1、t2、…、tj的多重比對，（s1，s2，…，si）（t1，t2，…，tj）=代表s1和t1的兩兩比對，則計(jì)算與相一致的1和2比對的算法如下：（1）標(biāo)定1的各列，如果s1在比對中對應(yīng)位置的編輯操作不是插入或刪除，則這些列分別標(biāo)記為s1對應(yīng)位置上的字符a1、a2、…、als1（ls1為序列s1的長度）；（2）標(biāo)定2的各列，如果t1在比對中對應(yīng)的位置編輯操作不是插入或刪除，則這些列分別標(biāo)記為t1對應(yīng)位置上的字符b1、b2、…、blt1（lt1為序列t1的長度）；（3）對a1、a2、…、als1和b1、b2、…、blt1進(jìn)行比對；（4）在所得到的比對中，對于1、2和中原來有插入或刪除操作的位置，恢復(fù)其原有的實(shí)際字符或空位字符“-”。第二十五頁，共62頁。例：1:s1-H-LVV2:t1L-HCLV：s1-H-LVVs2G-VLVCt2VLHCL-t1LHCLV-s3GN-LVVAA算法的輸出(shūchū)為 --H--LVV -G--VLVG -GN--LVV L-HC-LV- V-HC-L—分別對第1、2列和4、5列進(jìn)行壓縮，則最后結(jié)果為

—H—LVV G—VLVG GN—LVV LHCLV- VHCL--

第二十六頁，共62頁。對于n個序列的樹形比對的基本算法過程如下：（1）初始化，對于每個序列，生成一個葉節(jié)點(diǎn)（2）利用AA算法合并兩個節(jié)點(diǎn)，形成一個新節(jié)點(diǎn)，合并的結(jié)果放在新節(jié)點(diǎn)中，原來的兩個節(jié)點(diǎn)作為新節(jié)點(diǎn)的子節(jié)點(diǎn)（3）反復(fù)(fǎnfù)執(zhí)行（2），直到形成n個葉節(jié)點(diǎn)的樹根為止，根節(jié)點(diǎn)中的序列即為最終的多重比對結(jié)果。

s1s2s3s4α1α2α第二十七頁，共62頁。6、其它(qítā)多重序列比對算法一般漸進(jìn)式比對方法所采用的過程：（1）先將多個序列進(jìn)行兩兩比對，基于這些比較，計(jì)算得到一個距離矩陣，該矩陣反映每對序列的關(guān)系；（2）利用距離矩陣，建立一棵“相關(guān)樹”；（3）從最接近的一對序列出發(fā)(chūfā)，逐步歸并形成比對的聚類，直到所有序列處理完。第二十八頁，共62頁。例：((LYCES,SPIOL84),(YEAST,(XENLA,(((RAT,MOUSE96),HUMAN83),CHICK71)66),DROVI58))第二十九頁，共62頁。相關(guān)(xiāngguān)樹第三十頁，共62頁。多序列(xùliè)比對第三十一頁，共62頁。目前使用(shǐyòng)最廣泛的多重序列比對程序是ClustalWClustalW是一種漸進(jìn)的比對方法，先將多個序列進(jìn)行兩兩比對，基于這些比較，計(jì)算得到一個距離矩陣，該矩陣反映了每對序列的關(guān)系EBI的CLUSTALW是：

第三十二頁，共62頁。第三十三頁，共62頁。7、統(tǒng)計(jì)(tǒngjì)特征分析對于所得到(dédào)的多重序列比對，我們往往需要進(jìn)行歸納分析，總結(jié)這些序列的特征，或者給出這些序列共性的表示

—H—LVV G—VLVG GN—LVV LHCLV- VHCL--

（1）保守序列 表示序列每個位置上最可能出現(xiàn)的字符（或者(huòzhě)所有可能出現(xiàn)的字符） ATNTSC(N-A,T,C,G;S-G,C)第三十四頁，共62頁。（2）特征統(tǒng)計(jì)圖（Profile）令P=(P1,P2,…,PL)，P表示在的每一列上各種字符出現(xiàn)(chūxiàn)的概率分布 Pj=(pj0,pj1,…,pj|A|) A代表字母表，Pjk代表字母表A中第k個字符在第j列出現(xiàn)(chūxiàn)的概率。第0個字符是特殊的空位符號“-”。第三十五頁，共62頁。

ATTAT AACTT CTTAT ACTTT AGAAT

12345(位置(wèizhi))（堿基）第三十六頁，共62頁。利用保守序列或者特征統(tǒng)計(jì)圖可以判斷一個(yīɡè)序列是否滿足一定的特征給定一個(yīɡè)序列s=a1a2…am，定義字符a在第j位的代價(jià)為

其中，|A|代表字母表A的長度，Ak代表A的第k個字符，特別地A0代表空缺字符“-”。整個序列s的代價(jià)為一條序列與特征統(tǒng)計(jì)圖相對(xiāngduì)照，如果代價(jià)值小，說明該序列具有相應(yīng)的特征，否則該序列不具備相應(yīng)的特征。第三十七頁，共62頁。第四節(jié)DNA片段(piànduàn)組裝大規(guī)模基因組測序得到待測序列的一系列序列片段這些序列片段覆蓋待測序列序列片段之間也存在著相互覆蓋或者(huòzhě)重疊。目標(biāo)序列(xùliè)序列(xùliè)碎片第三十八頁，共62頁。1、片段組裝(zǔzhuānɡ)問題 定義： 給定一組取自特定字母表的字符串集合F，尋找一個最短的字符串s，使得F中的每一個字符串都是s的一個連續(xù)子串。這里，集合F的字符串相當(dāng)于待組裝(zǔzhuānɡ)的序列片段，而s則是序列片段組裝(zǔzhuānɡ)的結(jié)果。

Input

AnswerACCGT--ACCGT--CGTGC----CGTGCTTACTTAC-----TACCGT-TACCGT-- TTACCGTGC第三十九頁，共62頁。（1）堿基標(biāo)識(biāozhì)錯誤4個主要(zhǔyào)問題第四十頁，共62頁。（2）不知道(zhīdào)片段的方向第四十一頁，共62頁。（3）存在重復(fù)(chóngfù)區(qū)域

.

.第四十二頁，共62頁。（4）缺少(quēshǎo)覆蓋第四十三頁，共62頁。2、序列片段組裝(zǔzhuānɡ)模型 序列片段組裝過程：三個步驟（1）首先進(jìn)行序列片段的兩兩比較，確定(quèdìng)可能的片段之間的覆蓋（或者重疊）；（2）確定(quèdìng)所有片段統(tǒng)一的覆蓋模式，即確定(quèdìng)各個序列片段的相對位置；（3）最后確定(quèdìng)片段組裝結(jié)果，即確定(quèdìng)目標(biāo)序列。第四十四頁，共62頁。（1）最短公共(gōnggòng)超串模型三種片段組裝(zǔzhuānɡ)模型給定一個字符串集合F，求出一個最短的字符串S，使得對于所有屬于F的字符串f，S是f的超串（或者f是S的子串）。設(shè)F={ACT，CTA，AGT}則S=ACTAGT是F的超串由于S必須(bìxū)是各片段嚴(yán)格的超串，因此不允許片段的實(shí)驗(yàn)誤差，各片段的方向必須(bìxū)是已知的。第四十五頁，共62頁。（2）重建(zhònɡjiàn)模型考慮到片段的誤差和未知方向的問題 近似子串假設(shè)(jiǎshè)f、g是代表兩條序列的字符串，f作為g近似子串的代價(jià)為：S(g)代表(dàibiǎo)g所有子串的集合，d為一般編輯距離。第四十六頁，共62頁。設(shè)f=GCGATAG,g=CAGTCGCTGATCGTACG, 則最佳(zuìjiā)的子序列比對如下 -----GC-GATAG---- CAGTCGCTGATCGTACG設(shè)是一個介于0和1之間的數(shù)，稱串f是在誤差下S的近似子串，如果 ds(f,S)f 重建模型：給定一個字符串集合F，求一個最短的字符串S，使得對于所有屬于F的字符串f，下式成立： min(ds(f,S),ds(f’,S))f 其中(qízhōng)f’是f的反向互補(bǔ)串。第四十七頁，共62頁。（3）多重連續(xù)區(qū)模型(móxíng)稱一個多重序列比對是t-contig，如果其最弱連接的交疊長度至少為t。如果能夠(nénggòu)根據(jù)序列片段集合F構(gòu)造一個t-contig，稱F允許一個t-contig。多重連續(xù)區(qū)模型：給定一個片段集合F和一個整數(shù)t（0），將F分割為最小數(shù)目的子集Ci，1ik，每個Ci允許一個t-contig。目標(biāo)序列(xùliè)序列(xùliè)碎片不連續(xù)區(qū)域第四十八頁，共62頁。設(shè)F={GTAC，TAATG，TGTAA}

第四十九頁，共62頁。3、序列片段(piànduàn)覆蓋圖 覆蓋多圖OM（F）是一個有向圖 其中圖中的各個頂點(diǎn)代表F的一個字符串 如果f、gF，并且f的t個字符的后綴(hòuzhuì)與g的t個字符的前綴相同，則圖中存在一條權(quán)值為t的有向邊。 產(chǎn)生超串的路徑第五十頁，共62頁。第五十一頁，共62頁。設(shè)P是OM（P）中的一條(yītiáo)路徑，A是該路徑上對應(yīng)片段的集合，P有A-1條邊。將根據(jù)P所得到的超串記為S（P）。A的總長度、路徑權(quán)值及超串的長度關(guān)系如下：

‖A‖=w(P)+S(P) ‖A‖=aAa是A中序列的總長度 w(P)是路徑P權(quán)值的和第五十二頁，共62頁。任何一條路徑對應(yīng)于一個公共超串一條路徑是否通過圖中所有的頂點(diǎn)？ —哈密頓路徑A=F的共同超串

S(P)=‖F(xiàn)‖-w(P) ‖F(xiàn)‖是常數(shù)(chángshù) S(P)取最小等價(jià)于對w(P)取最大求最短的公共超串等價(jià)于取權(quán)值最大的哈密頓路徑第五十三頁，共62頁。最短超串是否總是對應(yīng)于一條路徑呢？ 答案是肯定的定理設(shè)F是一個無子串的串集合，則對于F的任何一個公共的超串S，在OM（F）中存在一條哈密頓路徑P，使得S（P）是S的子序列。（與子串有區(qū)別）推論設(shè)F是一個無子串的串集合，如果S是F最短的公共超串，則在OM（F）中有一條哈密頓路徑P，使得S=S（P）。引理兩個(liǎnɡɡè)等價(jià)的無子串的串集合相同。定理設(shè)F是一個串集合，則存在一個唯一的無子串集合G，使G等價(jià)于F。第五十四頁，共62頁。根據(jù)(gēnjù)上述的各個定理，片段組裝的一般過程如下：（1）對于給定的片段集合F，首先去掉那些是子串的序列，形成新的片段集合F’；（2）根據(jù)(gēnjù)F’生成覆蓋多圖；（3）求權(quán)值最高的哈密頓路徑，由此得到最短的公共超串；（4）最終形成組裝結(jié)果。 但是，如何在一個覆蓋多圖中找出權(quán)值最高的哈密頓路徑呢？

第五十五頁，共62頁。4、貪婪(tānlán)算法簡化覆蓋多圖，對每一對頂點(diǎn)僅考慮權(quán)值最大的邊，而去掉其它的邊。稱經(jīng)過處理后的新圖為F的覆蓋圖，記為OG（F）。貪婪算法的核心思想就是逐步(zhúbù)加入滿足哈密頓路徑條件的最大權(quán)值的邊無回路節(jié)點(diǎn)出度為1節(jié)點(diǎn)入度為1第五十六頁，共62頁。ATCACATGCAT22TGCATATCACATGCATCA3CATGAG問題(wèntí)？？？TGCATATCACATCAGTGCATCAGATCA期望(qīwàng)結(jié)果TGCATATCACATGAGTGCATCATCAG第五十七頁，共62頁。5、非循環(huán)(xúnhuá