【正文】 Bioputing technology— Multiple sequence alignment 第 4章 多重序列比對(duì)分析 目的要求： 1 掌握多重序列比對(duì)的基本概念及意義。 2 掌握多重序列比對(duì)的星形比對(duì)、樹(shù)形比對(duì)及隱馬爾可夫模型。 3 了解多重序列比對(duì)的動(dòng)態(tài)規(guī)劃算法、 CLUSTAL W 算法。 教學(xué)內(nèi)容： 多重序列比對(duì)的意義 多重序列比對(duì)算法原理 Multiple sequence alignment 多重序列比對(duì)的意義 目的： ? 發(fā)現(xiàn)多個(gè)序列的共性 ? 發(fā)現(xiàn)與結(jié)構(gòu)和功能相關(guān)的保守序列片段 定義： 設(shè)：有 k個(gè)序列 s1, s2, ... ,sk，每個(gè)序列由同一個(gè)字母表中的字符組成， k大于 2，通過(guò)插入“空位”操作，使得各序列達(dá)到 一樣的長(zhǎng)度 ，從而形成這些序列的多重比對(duì)。 Bioputing technology— Multiple sequence alignment 8條免疫球蛋白序列片段的多重比對(duì)： 半光氨酸 色氨酸 疏水殘基 保守區(qū)域 SP得分 Bioputing technology— Multiple sequence alignment Bioputing technology— Multiple sequence alignment 通過(guò)序列的多重比對(duì)，可以得到一個(gè)序列家族的序列 特征。當(dāng)給定一個(gè)新序列時(shí)，根據(jù)序列特征，可以判斷這 個(gè)序列是否屬于該家族。 對(duì)于多序列比對(duì)，現(xiàn)有的大多數(shù)算法都基于漸進(jìn)比對(duì) 的思想，在序列兩兩比對(duì)的基礎(chǔ)上逐步優(yōu)化多序列比對(duì)的 結(jié)果。 進(jìn)行多序列比對(duì)后，可以對(duì)比對(duì)結(jié)果進(jìn)行進(jìn)一步處理， 例如構(gòu)建序列的特征模式，將序列聚類、構(gòu)建分子進(jìn)化樹(shù)等。 多重序列比對(duì)算法原理 SP模型 多重比對(duì)的動(dòng)態(tài)規(guī)劃算法 優(yōu)化算法 星型比對(duì) 樹(shù)形比對(duì) CLUSTALW算法 Bioputing technology— Multiple sequence alignment SP 模型 (SumofPairs) 逐對(duì)加和函數(shù) 作用 ：評(píng)價(jià)多重序列比對(duì)的結(jié)果 SP計(jì)算的兩種方法： Bioputing technology— Multiple sequence alignment 方法 1：先計(jì)算多重比對(duì)結(jié)果的每一列字符的得分， 然后求整體多重比對(duì)得分 Bioputing technology— Multiple sequence alignment 假設(shè) : 得分函數(shù) (代價(jià)函數(shù) ) 具有加和性，即多重比對(duì)的得分 是各列得分總和。 思路 : 如何給比對(duì)的每一列打分，然后將各列的和加起來(lái)， 成為一個(gè)總得分。 每一列的處理方式 : 尋找一個(gè)具有 k 個(gè)變量的打分函數(shù) ，每一個(gè)變量或者是 一個(gè)來(lái)自特定字母表中的字符，或者是一個(gè)空位。 k 是參與多重比對(duì)的序列的個(gè)數(shù)。 Bioputing technology— Multiple sequence alignment 顯式函數(shù)應(yīng)滿足如下條件： 1. 函數(shù)形式簡(jiǎn)單，具有統(tǒng)一的形式，不隨序列的個(gè)數(shù) 而發(fā)生形式的變化。 2. 根據(jù)得分函數(shù)的意義，函數(shù)值應(yīng)獨(dú)立于各參數(shù)的順序， 即與待比較的序列先后次序無(wú)關(guān)。 3. 對(duì)相同的或相似字符的比對(duì)，獎(jiǎng)勵(lì)的得分值高，而對(duì) 于不相關(guān)的字符比對(duì)或空白，則進(jìn)行懲罰（得分為負(fù)值）。 滿足上述條件的一個(gè)函數(shù)就是常用的逐對(duì)加和函數(shù)， SP函數(shù) 。 方法 1：先計(jì)算多重比對(duì)結(jié)果的每一列字符的得分， 然后求整體多重比對(duì)得分 ? ??? ???1k1ik1ijjik21 )c,p ( c)c, . . . ,c,S P _ s c o r e ( c其中， c1,c2,…,ck是一列中的 k個(gè)字符， p是關(guān)于一對(duì)字符相似性的打分函數(shù)。 SP_score(c1,c2,…,ck)是多重序列比對(duì)中某一列 的得分 . Bioputing technology— Multiple sequence alignment 例：圖 3列的 SP得分： 26GSGPALLs c o r eSP ??????????????????????? 打分函數(shù)： P（ a,a） =0 P（ a,b） = 1 （ a≠b） 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) 的所有得分： （ 7654321） +2 = 26 然后將一個(gè)多重比對(duì)所有列的得分全部加起來(lái)，其和即為該多重比對(duì)的得分。 將所有多重比對(duì)的得分計(jì)算出來(lái)進(jìn)行比較，得分最高的，應(yīng)該是最好的。 Bioputing technology— Multiple sequence alignment 多重比對(duì)在兩條特定序列上的投影 Bioputing technology— Multiple sequence alignment 方法 2：先計(jì)算多重序列結(jié)果的序列兩兩比對(duì)得分， 然后計(jì)算整體多重比對(duì)得分。 ? 是一個(gè)多重比對(duì) ?ij是由 ?推演出來(lái)的序列 si和 sj的兩兩比對(duì) 方法 1和方法 2等價(jià)的條件： P(,)=0 Bioputing technology— Multiple sequence alignment ????jiijαs c o r e ( α)SP 多重比對(duì)的動(dòng)態(tài)規(guī)劃算法 ? 多重序列比對(duì)的最終目標(biāo)是通過(guò)處理得到一個(gè)得分最高（或代價(jià)最?。┑男蛄袑?duì)比排列，從而分析各序列之間的相似性和差異 。 Bioputing technology— Multiple sequence alignment 多重比對(duì)的動(dòng)態(tài)規(guī)劃算法 s1:VSNS s2:SNA s3:AS Bioputing technology— Multiple sequence alignment 前趨節(jié)點(diǎn)的個(gè)數(shù)等于 2k 1 問(wèn)題： 計(jì)算量巨大 時(shí)間復(fù)雜度為 O(2k?i=1,...,k ?si?) ↓ O(2kNk) Bioputing technology— Multiple sequence alignment NP完全問(wèn)題的定義 Bioputing technology— Multiple sequence alignment P 類問(wèn)題為多項(xiàng)式界的問(wèn)題； NP 類問(wèn)題是這樣一類問(wèn)題，如果有一個(gè)復(fù)雜度為多 項(xiàng)式的算法解決其中的某個(gè)問(wèn)題，則所有這些問(wèn)題都在 P類中； 而 NP完全問(wèn)題是這樣一類問(wèn)題，如果其中的某個(gè)問(wèn)題存在 多項(xiàng)式界的算法，則 NP 類中的每一個(gè)問(wèn)題都存在一個(gè)多項(xiàng) 式界算法。 NP 完全問(wèn)題通常被認(rèn)為是一些人們難以在有限的時(shí)間、 空間內(nèi)對(duì)問(wèn)題求出最佳解的問(wèn)題，幾乎所有專家都認(rèn)為不可 能在多項(xiàng)式時(shí)間內(nèi)準(zhǔn)確求解 NP完全問(wèn)題。 NP完全問(wèn)題的近似求解方法 Bioputing technology— Multiple sequence alignment 1. 舍去尋找最優(yōu)解的要求，尋找對(duì)一般問(wèn)題比較接近 最優(yōu)解的近似解； 2. 利用非常規(guī)的求解技術(shù)求解，例如，利用神經(jīng)網(wǎng)絡(luò)、 遺傳算法等方法進(jìn)行問(wèn)題求解。 生物信息學(xué)中 NP完全問(wèn)題的近似求解方法 Bioputing technology— Multiple sequence alignment 1. 只求解規(guī)模比較小的問(wèn)題； 2. 利用動(dòng)態(tài)規(guī)劃、分支約束等技術(shù)減小搜索空間，提高 求解問(wèn)題的效率； 3. 針對(duì)具體問(wèn)題的特點(diǎn)，根據(jù)實(shí)際輸入情況，設(shè)計(jì)實(shí)用 求解算法，這樣的算法雖然在最壞的情況下其時(shí)間復(fù) 雜度是非多項(xiàng)式的，但是算法執(zhí)行的平均效率和復(fù)雜 度與多項(xiàng)式的算法相當(dāng)； 4. 采用近似算法或者啟發(fā)式方法，如局部搜索、模擬退火、 遺傳算法等。 對(duì)基于 SP 模型尋找最優(yōu)多重序列比對(duì)這樣一個(gè)問(wèn)題， 可以用近似的方法求解，其算法的時(shí)間復(fù)雜度可用多項(xiàng)式表示。 優(yōu)化計(jì)算方法 標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法存在的問(wèn)題： 搜索空間大 剪枝技術(shù)：將搜索空間限定在一個(gè)較小的區(qū)域范圍內(nèi)。 若問(wèn)題是搜索一條得分最高（或代價(jià)最小）的路徑，則在搜索時(shí)如果當(dāng)前路徑的得分低于某個(gè)下限（或累積代價(jià)已經(jīng)超過(guò)某個(gè)上限），則對(duì)當(dāng)前路徑進(jìn)行剪枝，即不再搜索當(dāng)前路徑的后續(xù)空間。 Bioputing technology— Multiple sequence alignment Bioputing technology— Multiple sequence alignment 在序列兩兩比對(duì)中 , Fickett 和 Ukkonen 設(shè)計(jì)了一種 稱為 定界約束過(guò)程 (bounding procedure)的方法來(lái)縮小搜 索空間 ,減少計(jì)算量 , 其中距離矩陣的上界和下界可以預(yù)先 確定或動(dòng)態(tài)變化。 為了在多維空間上使用動(dòng)態(tài)規(guī)劃算法， Carrillo 和 Lipman 將這種思想引入到多重序列比對(duì)，即先進(jìn)行初步 的序列雙重比對(duì)，以限制進(jìn)一步做多重序列全面比對(duì)所需 要的多維空間的大小和計(jì)算量，從而克服了多序列的維數(shù)、 空間和運(yùn)算量之間的矛盾 CarrilloLipman的優(yōu)化計(jì)算方法 Bioputing technology— Multiple sequence alignment 設(shè) k 條序列的長(zhǎng)度分別為 n1n2……nk，按照 SP 得分模 型計(jì)算這些序列的最優(yōu)比對(duì)。依然采用動(dòng)態(tài)規(guī)劃方法，但 并不計(jì)算超晶格空間中所有的節(jié)點(diǎn)，而是僅處理 與最優(yōu)路 徑“相關(guān)”的節(jié)點(diǎn) 。但是，哪些節(jié)點(diǎn)是相關(guān)的呢？這需要觀 察節(jié)點(diǎn)在兩條序列上的投影。 確定相關(guān)節(jié)點(diǎn)的方法： 假設(shè) α 是關(guān)于 k 條序列 s1s2……sk 的最優(yōu)多重比對(duì)。 從某個(gè)節(jié)點(diǎn)向任何兩條序列所在的平面投影，如果該投影 是這兩條序列兩兩最優(yōu)比對(duì)的一部分（前面一部分），則 該節(jié)點(diǎn)是與最優(yōu)比對(duì)相關(guān)的節(jié)點(diǎn)。 問(wèn)題的提出 : 一種計(jì)算兩條序列經(jīng)過(guò)特定斷點(diǎn)的最優(yōu)比對(duì)的算法 Bioputing technology— Multiple sequence alignment 設(shè)有兩條序列 s