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