生物信息學(xué)多序列比對(duì)和并行策略

1、生物信息學(xué)多序列比對(duì)和并行策略生物信息學(xué)多序列比對(duì)和并行策略O(shè)utline多序列比對(duì)的意義多序列比對(duì)算法原理常見(jiàn)多序列比對(duì)應(yīng)用程序介紹多序列比對(duì)的并行策略生物信息學(xué)多序列比對(duì)和并行策略什么是多序列比對(duì)定義：有k個(gè)序列s1, s2, . ,sk，每個(gè)序列由同一個(gè)字母表中的字符組成，k2，序列所有字符的相對(duì)位置保持不變，通過(guò)插入“空位”操作，使得各序列達(dá)到一樣的長(zhǎng)度，從而形成這些序列的多重比對(duì)。多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略多序列比對(duì)的應(yīng)用尋找蛋白質(zhì)家族，識(shí)別多個(gè)序列的保守區(qū)域發(fā)現(xiàn)直系同源(Orthologs)與旁系同源(Paralogs)基因?qū)ふ彝椿?相似的序列往往具有同源性)輔助

2、預(yù)測(cè)新序列的二級(jí)或三級(jí)結(jié)構(gòu)可以直觀地看到基因的哪些區(qū)域?qū)ν蛔兠舾蠵CR引物設(shè)計(jì)分析多個(gè)序列的一致序列系統(tǒng)發(fā)育方法構(gòu)建進(jìn)化樹(shù)，用于進(jìn)化分析尋找個(gè)體之間單核苷酸多態(tài)性(SNPs)多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略多序列比對(duì)的應(yīng)用多序列比對(duì)與進(jìn)化研究例子多序列比對(duì)圖中NYLS為樹(shù)根生物信息學(xué)多序列比對(duì)和并行策略多序列比對(duì)的應(yīng)用多序列比對(duì)與進(jìn)化研究例子多序列比對(duì) 共變位點(diǎn)保守位點(diǎn)保守區(qū)域生物信息學(xué)多序列比對(duì)和并行策略O(shè)utline多序列比對(duì)的意義多序列比對(duì)算法原理常見(jiàn)多序列比對(duì)應(yīng)用程序介紹多序列比對(duì)的并行策略生物信息學(xué)多序列比對(duì)和并行策略多序列比對(duì)算法原理多重比對(duì)的動(dòng)態(tài)規(guī)劃算法SP方法優(yōu)化算法星

3、型比對(duì)樹(shù)形比對(duì)CLUSTALW算法（漸進(jìn)算法）隱馬爾可夫模型多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原理 動(dòng)態(tài)規(guī)劃算法多序列比對(duì)多重序列比對(duì)的最終目標(biāo)是通過(guò)處理得到一個(gè)得分最高（或代價(jià)最?。┑男蛄袑?duì)比排列，從而分析各序列之間的相似性和差異。兩條序列比對(duì)的計(jì)算復(fù)雜度是N2多序列比對(duì)的計(jì)算復(fù)雜度呈指數(shù)增長(zhǎng)，計(jì)算量巨大，無(wú)法實(shí)際應(yīng)用生物信息學(xué)多序列比對(duì)和并行策略算法原理 動(dòng)態(tài)規(guī)劃算法多序列比對(duì)的動(dòng)態(tài)規(guī)劃算法多序列比對(duì)Sequence 1Sequence 2Sequence 3生物信息學(xué)多序列比對(duì)和并行策略算法原理 動(dòng)態(tài)規(guī)劃算法多序列比對(duì)的動(dòng)態(tài)規(guī)劃算法多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原

4、理 動(dòng)態(tài)規(guī)劃算法多序列比對(duì)的動(dòng)態(tài)規(guī)劃算法多序列比對(duì)Sequence 1Sequence 2Sequence 3生物信息學(xué)多序列比對(duì)和并行策略算法原理 SP方法為了找到最佳比對(duì)，并解決解決動(dòng)態(tài)規(guī)則算法的計(jì)算復(fù)雜問(wèn)題，Carrillo & Lipman (1988)建立了SP(Sum of Pairs)方法SP (Sum-of-Pairs) 方法：通過(guò)對(duì)一個(gè)隨機(jī)矩陣中氨基酸對(duì)的所有可能組合的記分求和來(lái)獲得矩陣得分SP計(jì)算可分為兩種方法。多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原理 SP方法SP計(jì)算方法1：先計(jì)算多重比對(duì)結(jié)果的每一列字符的得分多序列比對(duì)其中，c1,c2,ck是一列中的k個(gè)字符，

5、p是關(guān)于一對(duì)字符相似性的打分函數(shù)。 SP_score(c1,c2,ck)是多重序列比對(duì)中某一列 的得分.生物信息學(xué)多序列比對(duì)和并行策略算法原理 SP方法SP計(jì)算方法1：計(jì)算多重比對(duì)每一列的SP得分多序列比對(duì)打分函數(shù)： P（a,a）=0 P（a,b）= -1 （ab） P（a,-）=P（-,b）= -1 P（-,-）=0逐對(duì)計(jì)算p(1,2)，p (1,3)，.，p(1,8)，p (2,3)，p(2,4)，.p(2,8) .，p(7,8) 的所有得分：（-7-6-5-4-3-2-1）+2 = -26然后將一個(gè)多重比對(duì)所有列的得分全部加起來(lái)，其和即為該多重比對(duì)的得分。將所有多重比對(duì)的得分計(jì)算出來(lái)進(jìn)行

6、比較，得分最高的，應(yīng)該是最好的。 生物信息學(xué)多序列比對(duì)和并行策略算法原理 SP方法SP計(jì)算方法2：先計(jì)算多重序列結(jié)果的序列兩兩比對(duì)得分多序列比對(duì) 是一個(gè)多重比對(duì)ij是由推演出來(lái)的序列si和sj的兩兩比對(duì) 方法1和方法2等價(jià)的條件：P(-,-)=0生物信息學(xué)多序列比對(duì)和并行策略算法原理 SP方法基于SP方法的多序列比對(duì)流程：多序列比對(duì)計(jì)算所有雙序列比對(duì)的分?jǐn)?shù)用這些分?jǐn)?shù)構(gòu)建進(jìn)化樹(shù)基于進(jìn)化樹(shù)計(jì)算雙序列比對(duì)權(quán)重基于進(jìn)化樹(shù)構(gòu)建一個(gè)啟發(fā)式多序列比對(duì)算法 計(jì)算每一對(duì)雙序列比對(duì)的最大權(quán)重計(jì)算比對(duì)的空間位置以達(dá)到最佳比對(duì)完成最佳比對(duì) 輸出與最大權(quán)重比較所獲得的慢且消耗大量?jī)?nèi)存最大可以比對(duì)8-9 個(gè)長(zhǎng)約250的氨

7、基酸殘基生物信息學(xué)多序列比對(duì)和并行策略算法原理 漸進(jìn)算法啟發(fā)式算法：不一定保證最終能得到最優(yōu)解，但在大多數(shù)情況下，其計(jì)算結(jié)果接近于最優(yōu)結(jié)果；啟發(fā)式算法：能夠大大減少所需的計(jì)算時(shí)間，加快計(jì)算速度漸進(jìn)算法：多重序列比對(duì)中常用的啟發(fā)式方法。其基本思想是將序列多重比對(duì)轉(zhuǎn)化為序列兩兩比對(duì)，逐漸將兩兩比對(duì)組合起來(lái)，最終形成完整的多序列比對(duì)。星形結(jié)構(gòu)和樹(shù)形結(jié)構(gòu)多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原理 星形比對(duì)星形比對(duì)的基本思想：多序列比對(duì)首先由Gusfield 提出。在給定的若干序列中，選擇一個(gè)核心序列，通過(guò)該序列與其它序列的兩兩比對(duì)形成所有序列的多重比對(duì) ，從而使得 在核心序列和任何一個(gè)其它序列方

8、向的投影是最優(yōu)的兩兩比對(duì)。只要是空位，則永遠(yuǎn)是空位；逐步增加sc中的空位字符，以適應(yīng)其他的比對(duì)；決不刪除sc中已存在的空位字符。生物信息學(xué)多序列比對(duì)和并行策略算法原理 星形比對(duì)星形比對(duì)算法示意圖多序列比對(duì)scs1s2sk(sc, s1) (sc, s2) (sc, sk)生物信息學(xué)多序列比對(duì)和并行策略算法原理 星形比對(duì)如何選擇核心序列？多序列比對(duì)方法1：嘗試將每一個(gè)序列分別作為核心序列， 進(jìn)行星形多重序列比對(duì)，取比對(duì)結(jié)果最 好的一個(gè)。即SP得分最高的為最好。方法2：是計(jì)算所有的兩兩比對(duì)，取下式值最大 的一個(gè)：生物信息學(xué)多序列比對(duì)和并行策略算法原理 星形比對(duì)多序列比對(duì) 有5個(gè)序列： s1 = A

9、TTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 =ACTGACCsc=s1ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATTATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC- (s1,s2) (s1,s3) (s1,s4) (s1,s5)ATTGCCATT-ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC- 生物信息學(xué)多序列比對(duì)和并行策略算法原理 樹(shù)形比對(duì)星形比對(duì)的基本思想：多序列比對(duì)k個(gè)待比對(duì)的序列 具有k個(gè)葉節(jié)點(diǎn)的樹(shù)每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一

10、條序列將序列賦予樹(shù)內(nèi)部節(jié)點(diǎn)，計(jì)算樹(shù)中每個(gè)分支的權(quán)值，權(quán)值代表對(duì)應(yīng)分支連接的兩個(gè)序列之間的相似性。所有權(quán)值的和就是這棵樹(shù)的得分。樹(shù)形比對(duì)：尋找一種樹(shù)的內(nèi)部節(jié)點(diǎn)序列賦予方式， 使得樹(shù)的得分最大。生物信息學(xué)多序列比對(duì)和并行策略算法原理 樹(shù)形比對(duì)多序列比對(duì)將CT、CG、CT分別賦予節(jié)點(diǎn) x、y、z，則樹(shù)的得分為8。CTCGCT多重序列比對(duì) 兩兩序列比對(duì) 合并兩個(gè)比對(duì)（比對(duì)的比對(duì)） Aligment of AlignmentAA算法 P（a,a）=1 P（a,b）= 0 （ab） P（a,-）=P（-,b）= -1111122G - TC A TC - GC T G比對(duì)結(jié)果：打分函數(shù)生物信息學(xué)多序列比對(duì)

11、和并行策略算法原理 樹(shù)形比對(duì)AA算法概述-1：多序列比對(duì)假設(shè)有兩個(gè)多重比對(duì)1和2 1代表序列s1,s2,si的多重比對(duì) 2代表序列t1,t2,tj的多重比對(duì)并且,( s1,s2,si ) ( t1,t2,tj )= 代表s1和t1的兩兩比對(duì), 則計(jì)算與相一致的1 和2比對(duì)的算法如下:生物信息學(xué)多序列比對(duì)和并行策略算法原理 樹(shù)形比對(duì)AA算法概述-2：多序列比對(duì)標(biāo)定1的各列中不為空位的字符:a1,a2,al1 s1=l1 標(biāo)定2的各列中不為空位的字符:b1,b2,bl2 t1=l2對(duì)a1,a2,al1 和b1,b2,bl2 進(jìn)行比對(duì),在所得到的比對(duì)中,對(duì)于1、2和中原來(lái)有插入或刪除操作的位置, 恢

12、復(fù)其原有的實(shí)際字符或空位字符”-”.a1 a2a3a4b1 b2b3b4b5生物信息學(xué)多序列比對(duì)和并行策略算法原理 樹(shù)形比對(duì)多序列比對(duì)對(duì)于n個(gè)序列的樹(shù)形比對(duì)的基本算法過(guò)程如下：（1）初始化，對(duì)于每個(gè)序列，生成一個(gè)葉節(jié)點(diǎn)（2）利用AA算法合并兩個(gè)節(jié)點(diǎn)，形成一個(gè)新節(jié)點(diǎn)， 合并的結(jié)果放在新節(jié)點(diǎn)中，原來(lái)的兩個(gè)節(jié)點(diǎn)作為 新節(jié)點(diǎn)的子節(jié)點(diǎn)（3）反復(fù)執(zhí)行（2），直到形成n個(gè)葉節(jié)點(diǎn)的樹(shù)根為止， 根節(jié)點(diǎn)中的序列即為最終的多重比對(duì)結(jié)果。 s1 s2 s3 s412生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法多序列比對(duì)CLUSTAL 算法是一種漸進(jìn)的比對(duì)方法，它是由和 P.M.Sharp 于1988年首

13、次提出的。目的： 對(duì)來(lái)自不同物種的功能相同或相似的蛋白進(jìn)行比對(duì)和聚類(lèi)分析，可對(duì)這些物種的親緣關(guān)系進(jìn)行判斷，并且對(duì)這些蛋白在生物進(jìn)化過(guò)程中的保守性作出估計(jì)。 生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法Clustal算法包括三個(gè)階段：多序列比對(duì)1. 先將多重序列進(jìn)行兩兩比對(duì)?；谶@些比對(duì)，計(jì)算得到 一個(gè)距離矩陣，該矩陣反映每對(duì)序列之間的關(guān)系。2. 根據(jù)距離矩陣計(jì)算產(chǎn)生系統(tǒng)發(fā)育樹(shù)，以此來(lái)確定被比較 序列間相似的程度3. 有了這棵系統(tǒng)發(fā)育樹(shù)的指導(dǎo)，從關(guān)系最緊密的兩條序列 開(kāi)始，逐步引入鄰近的序列或序列組，并不斷重新構(gòu)建 比對(duì)，直到所有序列都被加入為止。生物信息學(xué)多序列比對(duì)和并行策略算法

14、原理 CLUSTAL算法實(shí)例：多序列比對(duì)Hbb_Human : 人的-球蛋白Hbb_Horse : 馬的-球蛋白 Hba_Human : 人的-球蛋白Hba_Horse : 馬的-球蛋白 Myg_phyca : 抹香鯨的血紅蛋白 Glb5_petma : 七鰓鰻藍(lán)血紅蛋白Lgb2_Luplu : 羽扇豆的豆血紅蛋白已知三級(jí)結(jié)構(gòu)的七個(gè)球蛋白序列，分別為： 生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法實(shí)例：多序列比對(duì)兩兩比對(duì)，構(gòu)建距離矩陣系統(tǒng)發(fā)育樹(shù)的構(gòu)建漸進(jìn)比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法Clustal算法第1階段：產(chǎn)生距離矩陣樹(shù)多序列比對(duì)用完全動(dòng)態(tài)規(guī)劃

15、法計(jì)算的7個(gè)球蛋白序列之間的77的距離矩陣 生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法Clustal算法第2階段：構(gòu)建系統(tǒng)發(fā)育樹(shù)多序列比對(duì)根據(jù)第一階段結(jié)果中的距離矩陣，用鄰近歸并法來(lái)計(jì)算產(chǎn)生一棵有分枝長(zhǎng)度和序列權(quán)重的有根樹(shù)。生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法Clustal算法第3階段：漸進(jìn)的比對(duì)多序列比對(duì) 通過(guò)一系列兩兩比對(duì)來(lái)構(gòu)建更大的比對(duì)序列組。按照指導(dǎo)樹(shù)中的分支順序，從有根樹(shù)的末梢到樹(shù)根逐漸進(jìn)行(1)對(duì)(2)(3)對(duì)(4)(8)對(duì)(9)(5)對(duì)(10)(6)對(duì)(11)(7)對(duì)(12) (13)生物信息學(xué)多序列比對(duì)和并行策略算法原理 CLUSTAL算法

16、實(shí)例：多序列比對(duì)生物信息學(xué)多序列比對(duì)和并行策略算法原理 Tcoffee算法Tcoffee算法包括四個(gè)階段：多序列比對(duì)采用Clustal計(jì)算兩兩序列之間的全局最優(yōu)比對(duì)結(jié)果；采用LALIGN計(jì)算兩兩序列之間的局部最優(yōu)比對(duì)；設(shè)計(jì)加權(quán)系統(tǒng)，綜合考慮以上兩類(lèi)結(jié)果的因素，構(gòu)建指導(dǎo)庫(kù)；最后，采用漸進(jìn)式比對(duì)算法，得到最終的結(jié)果。生物信息學(xué)多序列比對(duì)和并行策略算法原理 Tcoffee算法多序列比對(duì)同時(shí)進(jìn)行全局和局部的兩兩序列比對(duì)對(duì)以上打分的結(jié)果設(shè)計(jì)權(quán)重系統(tǒng)，找到序列中最保守的部分漸進(jìn)方法的比對(duì)，基于上述計(jì)算的primary library生物信息學(xué)多序列比對(duì)和并行策略算法原理 漸進(jìn)算法漸進(jìn)算法存在的問(wèn)題：多序列

17、比對(duì)如果有兩組序列AB和CD，他們的距離非常接近，哪組最先比對(duì)？以誰(shuí)為基準(zhǔn)？Seq1: ARKCVSeq2: ARCVSeq3: AKCV若Seq1,2先比對(duì)，再加入Seq3：ARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV若Seq1,3先比對(duì)，再加入Seq3：若Seq2,3先比對(duì)，再加入Seq1：生物信息學(xué)多序列比對(duì)和并行策略算法原理 迭代算法PRRP多序列比對(duì)1. 先用“漸進(jìn)”算法進(jìn)行多序列比對(duì);2. 基于多序列比對(duì)的結(jié)果構(gòu)建進(jìn)化樹(shù)；3. 重新計(jì)算序列之間的距離，再用“漸進(jìn)”算法進(jìn)行多序列比對(duì)；4. 重復(fù)上述步驟，直到結(jié)果不再發(fā)生改變?yōu)橹?。生物信?/p>

18、學(xué)多序列比對(duì)和并行策略算法原理 迭代算法DiAlign多序列比對(duì)1. 對(duì)所有序列進(jìn)行兩兩之間的局部最優(yōu)化的比對(duì);2. 找到所有能夠匹配的部分M1；將重疊的、前后連續(xù)的匹配部分連接起來(lái)(diagonals)，為M2；3. 將剩下的未比對(duì)的序列重新比對(duì)，再發(fā)現(xiàn)能夠匹配的部分，構(gòu)成新M1，將連續(xù)部分構(gòu)成M2；4. 重復(fù)上述步驟，直到結(jié)果收斂。生物信息學(xué)多序列比對(duì)和并行策略算法原理 統(tǒng)計(jì)學(xué)方法隱馬爾科夫模型：多序列比對(duì)定義：一種統(tǒng)計(jì)模型，它考慮有關(guān)匹配、錯(cuò)配和間隔的所有可能的組合來(lái)生成一組序列排列HMM用來(lái)序列分析、產(chǎn)生概形HMM、分析序列組成和模式并通過(guò)預(yù)測(cè)開(kāi)放閱讀框(Open Reading Fr

19、ame, ORF）來(lái)定位基因及預(yù)測(cè)蛋白質(zhì)結(jié)構(gòu)原理：先產(chǎn)生一個(gè)序列家族模型，并用先驗(yàn)信息初始化，然后用一組序列(序列條數(shù)20) 來(lái)訓(xùn)練HMM模型。訓(xùn)練過(guò)程中包括的序列越多，分析的精確性越高生物信息學(xué)多序列比對(duì)和并行策略算法原理 統(tǒng)計(jì)學(xué)方法隱馬爾科夫模型：多序列比對(duì)優(yōu)點(diǎn)：植根于概率論，無(wú)須序列的順序信息，無(wú)需插入/缺失和罰分，可以用到很多先驗(yàn)信息缺點(diǎn)：需要至少20條序列，有時(shí)需要更多才能了解進(jìn)化歷史分析工具：HMMER()Pfam: (protein domain alignments and pro)生物信息學(xué)多序列比對(duì)和并行策略算法原理 統(tǒng)計(jì)學(xué)方法隱馬爾科夫模型：多序列比對(duì)圖中: 方形代表匹配狀態(tài)(主狀態(tài))，即輸出的氨基酸和基本序列中對(duì)應(yīng) 的氨基酸匹配; 圓形表示刪除或缺失狀態(tài)，即從原始蛋白質(zhì)序列中去掉一個(gè)特定 的氨基酸。 菱形表示氨基酸的插入，即在原始蛋白質(zhì)序列插入一個(gè)氨基酸。 各狀態(tài)間的箭頭表示狀態(tài)間的轉(zhuǎn)換途徑。 注意: 不同的參數(shù)會(huì)使模型以不同的概率產(chǎn)生新的氨基