生物計算技術(shù)-第章多重序列比對分析ppt課件

1、Biocomputing technology Multiple sequence alignment第第4章章 多重序列比對分析多重序列比對分析目的要求：目的要求： 1 1 掌握多重序列比對的基本概念及意義。掌握多重序列比對的基本概念及意義。 2 2 掌握多重序列比對的星形比對、樹形比對及隱馬爾可夫模型。掌握多重序列比對的星形比對、樹形比對及隱馬爾可夫模型。 3 3 了解多重序列比對的動態(tài)規(guī)劃算法、了解多重序列比對的動態(tài)規(guī)劃算法、CLUSTAL W CLUSTAL W 算法。算法。教學(xué)內(nèi)容：教學(xué)內(nèi)容： 4.1 4.1 多重序列比對的意義多重序列比對的意義 4.2 4.2 多重序列比對算法原理

2、多重序列比對算法原理Multiple sequence alignment4.1 多重序列比對的意義多重序列比對的意義目的：目的： 發(fā)現(xiàn)多個序列的共性發(fā)現(xiàn)多個序列的共性 發(fā)現(xiàn)與結(jié)構(gòu)和功能相關(guān)的保守序列片段發(fā)現(xiàn)與結(jié)構(gòu)和功能相關(guān)的保守序列片段定義：定義：設(shè)：有設(shè)：有k個序列個序列s1, s2, . ,sk，每個序列由同一，每個序列由同一個字母表中的字符組成，個字母表中的字符組成，k大于大于2，通過插入，通過插入“空空位位操作，使得各序列達(dá)到一樣的長度，從而形操作，使得各序列達(dá)到一樣的長度，從而形成這些序列的多重比對。成這些序列的多重比對。Biocomputing technology Multip

3、le sequence alignment8條免疫球蛋白序列片段的多重比對：條免疫球蛋白序列片段的多重比對：半光氨酸半光氨酸色氨酸色氨酸疏水殘基疏水殘基保守區(qū)域保守區(qū)域SPSP得分得分Biocomputing technology Multiple sequence alignmentBiocomputing technology Multiple sequence alignment 通過序列的多重比對，可以得到一個序列家族的序列通過序列的多重比對，可以得到一個序列家族的序列特征。當(dāng)給定一個新序列時，根據(jù)序列特征，可以判斷這特征。當(dāng)給定一個新序列時，根據(jù)序列特征，可以判斷這個序列是否屬于該家

4、族。個序列是否屬于該家族。 對于多序列比對，現(xiàn)有的大多數(shù)算法都基于漸進(jìn)比對對于多序列比對，現(xiàn)有的大多數(shù)算法都基于漸進(jìn)比對的思想，在序列兩兩比對的基礎(chǔ)上逐步優(yōu)化多序列比對的的思想，在序列兩兩比對的基礎(chǔ)上逐步優(yōu)化多序列比對的結(jié)果。結(jié)果。 進(jìn)行多序列比對后，可以對比對結(jié)果進(jìn)行進(jìn)一步處理，進(jìn)行多序列比對后，可以對比對結(jié)果進(jìn)行進(jìn)一步處理，例如構(gòu)建序列的特征模式，將序列聚類、構(gòu)建分子進(jìn)化樹等。例如構(gòu)建序列的特征模式，將序列聚類、構(gòu)建分子進(jìn)化樹等。 4.2 多重序列比對算法原理多重序列比對算法原理4.2.1 SP模型模型4.2.2 多重比對的動態(tài)規(guī)劃算法多重比對的動態(tài)規(guī)劃算法4.2.3 優(yōu)化算法優(yōu)化算法4.

5、2.4 星型比對星型比對4.2.5 樹形比對樹形比對4.2.6 CLUSTALW算法算法4.2.7隱馬爾可夫模型隱馬爾可夫模型Biocomputing technology Multiple sequence alignment4.2.1 SP 模型模型 (Sum-of-Pairs) 逐對加和函數(shù)逐對加和函數(shù)作用：評價多重序列比對的結(jié)果作用：評價多重序列比對的結(jié)果SPSP計算的兩種方法：計算的兩種方法：Biocomputing technology Multiple sequence alignment方法方法1 1：先計算多重比對結(jié)果的每一列字符的得分，：先計算多重比對結(jié)果的每一列字符的得分

6、， 然后求整體多重比對得分然后求整體多重比對得分Biocomputing technology Multiple sequence alignment假設(shè)假設(shè): 得分函數(shù)得分函數(shù)(代價函數(shù)代價函數(shù)) 具有加和性，即多重比對的得分具有加和性，即多重比對的得分 是各列得分總和。是各列得分總和。思路思路: 如何給比對的每一列打分，然后將各列的和加起來，如何給比對的每一列打分，然后將各列的和加起來， 成為一個總得分。成為一個總得分。每一列的處理方式每一列的處理方式: 尋找一個具有尋找一個具有k 個變量的打分函數(shù)，每一個變量或者是個變量的打分函數(shù)，每一個變量或者是 一個來自特定字母表中的字符，或者是一個

7、空位。一個來自特定字母表中的字符，或者是一個空位。 k 是參與多重比對的序列的個數(shù)。是參與多重比對的序列的個數(shù)。Biocomputing technology Multiple sequence alignment顯式函數(shù)應(yīng)滿足如下條件：顯式函數(shù)應(yīng)滿足如下條件：函數(shù)形式簡單，具有統(tǒng)一的形式，不隨序列的個數(shù)函數(shù)形式簡單，具有統(tǒng)一的形式，不隨序列的個數(shù) 而發(fā)生形式的變化。而發(fā)生形式的變化。2. 根據(jù)得分函數(shù)的意義，函數(shù)值應(yīng)獨立于各參數(shù)的順序，根據(jù)得分函數(shù)的意義，函數(shù)值應(yīng)獨立于各參數(shù)的順序， 即與待比較的序列先后次序無關(guān)。即與待比較的序列先后次序無關(guān)。3. 對相同的或相似字符的比對，獎勵的得分值高，

8、而對對相同的或相似字符的比對，獎勵的得分值高，而對 于不相關(guān)的字符比對或空白，則進(jìn)行懲罰得分為負(fù)值）。于不相關(guān)的字符比對或空白，則進(jìn)行懲罰得分為負(fù)值）。滿足上述條件的一個函數(shù)就是常用的逐對加和函數(shù)，滿足上述條件的一個函數(shù)就是常用的逐對加和函數(shù)，SP函數(shù)函數(shù) 。 方法方法1 1：先計算多重比對結(jié)果的每一列字符的得分，：先計算多重比對結(jié)果的每一列字符的得分， 然后求整體多重比對得分然后求整體多重比對得分 1k1ik1ijjik21)c,p(c)c,.,c,SP_score(c其中，其中，c1,c2,ck是一列中的是一列中的k個字符，個字符， p是關(guān)于一對字符相似性的打分函數(shù)。是關(guān)于一對字符相似性的

9、打分函數(shù)。 SP_score(c1,c2,ck)是多重序列比對中某一列是多重序列比對中某一列 的得分的得分.Biocomputing technology Multiple sequence alignment例：圖例：圖4.1多重比對的倒數(shù)第多重比對的倒數(shù)第3列的列的SP得分：得分：26GSGPALLscoreSP打分函數(shù)：打分函數(shù)： Pa,a）=0 Pa,b）= -1 （ab） Pa,-）=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) 的所有得分：的所有得分：（-7-6-

10、5-4-3-2-1）+2 = -26然后將一個多重比對所有列的得分全部加起來，其和即為該多重比對的得分。然后將一個多重比對所有列的得分全部加起來，其和即為該多重比對的得分。將所有多重比對的得分計算出來進(jìn)行比較，得分最高的，應(yīng)該是最好的。將所有多重比對的得分計算出來進(jìn)行比較，得分最高的，應(yīng)該是最好的。 Biocomputing technology Multiple sequence alignment多重比對在兩條特定序列上的投影多重比對在兩條特定序列上的投影Biocomputing technology Multiple sequence alignment方法方法2：先計算多重序列結(jié)果的序

11、列兩兩比對得分，：先計算多重序列結(jié)果的序列兩兩比對得分， 然后計算整體多重比對得分。然后計算整體多重比對得分。 是一個多重比對是一個多重比對 ijij是由是由 推演出來的序列推演出來的序列sisi和和sjsj的兩兩比對的兩兩比對 方法方法1和方法和方法2等價的條件：等價的條件：P(-,-)=0Biocomputing technology Multiple sequence alignmentj ji ii ij js sc co or re e( () )S SP P4.2.2 多重比對的動態(tài)規(guī)劃算法多重比對的動態(tài)規(guī)劃算法 多重序列比對的最終目標(biāo)是通過處理得到一個得分最高多重序列比對的最終目

12、標(biāo)是通過處理得到一個得分最高或代價最小的序列對比排列，從而分析各序列之間的或代價最小的序列對比排列，從而分析各序列之間的相似性和差異。相似性和差異。Biocomputing technology Multiple sequence alignment4.2.2 多重比對的動態(tài)規(guī)劃算法多重比對的動態(tài)規(guī)劃算法s1:VSN-Ss2:-SNA-s3:-ASBiocomputing technology Multiple sequence alignment前趨節(jié)點的個數(shù)等于前趨節(jié)點的個數(shù)等于2k - 1 2k - 1 問題：問題：計算量巨大計算量巨大時間復(fù)雜度為時間復(fù)雜度為O(2kO(2ki=1,.,

13、k i=1,.,k sisi) ) O(2kNk) O(2kNk) Biocomputing technology Multiple sequence alignmentNP-完全問題的定義完全問題的定義Biocomputing technology Multiple sequence alignment P 類問題為多項式界的問題；類問題為多項式界的問題； NP 類問題是這樣一類問題，如果有一個復(fù)雜度為多類問題是這樣一類問題，如果有一個復(fù)雜度為多項式的算法解決其中的某個問題，則所有這些問題都在項式的算法解決其中的某個問題，則所有這些問題都在P類中；類中；而而NP-完全問題是這樣一類問題，如果

14、其中的某個問題存在完全問題是這樣一類問題，如果其中的某個問題存在多項式界的算法，則多項式界的算法，則NP 類中的每一個問題都存在一個多項類中的每一個問題都存在一個多項式界算法。式界算法。 NP 完全問題通常被認(rèn)為是一些人們難以在有限的時間、完全問題通常被認(rèn)為是一些人們難以在有限的時間、空間內(nèi)對問題求出最佳解的問題，幾乎所有專家都認(rèn)為不可空間內(nèi)對問題求出最佳解的問題，幾乎所有專家都認(rèn)為不可能在多項式時間內(nèi)準(zhǔn)確求解能在多項式時間內(nèi)準(zhǔn)確求解NP-完全問題。完全問題。 NP-完全問題的近似求解方法完全問題的近似求解方法Biocomputing technology Multiple sequence

15、alignment舍去尋找最優(yōu)解的要求，尋找對一般問題比較接近舍去尋找最優(yōu)解的要求，尋找對一般問題比較接近 最優(yōu)解的近似解；最優(yōu)解的近似解；2. 利用非常規(guī)的求解技術(shù)求解，例如，利用神經(jīng)網(wǎng)絡(luò)、利用非常規(guī)的求解技術(shù)求解，例如，利用神經(jīng)網(wǎng)絡(luò)、 遺傳算法等方法進(jìn)行問題求解。遺傳算法等方法進(jìn)行問題求解。 生物信息學(xué)中生物信息學(xué)中NP-完全問題的近似求解方法完全問題的近似求解方法Biocomputing technology Multiple sequence alignment1. 只求解規(guī)模比較小的問題；只求解規(guī)模比較小的問題；2. 利用動態(tài)規(guī)劃、分支約束等技術(shù)減小搜索空間，進(jìn)步利用動態(tài)規(guī)劃、分支約

16、束等技術(shù)減小搜索空間，進(jìn)步 求解問題的效率；求解問題的效率；3. 針對具體問題的特點，根據(jù)實際輸入情況，設(shè)計實用針對具體問題的特點，根據(jù)實際輸入情況，設(shè)計實用 求解算法，這樣的算法雖然在最壞的情況下其時間復(fù)求解算法，這樣的算法雖然在最壞的情況下其時間復(fù) 雜度是非多項式的，但是算法執(zhí)行的平均效率和復(fù)雜雜度是非多項式的，但是算法執(zhí)行的平均效率和復(fù)雜 度與多項式的算法相當(dāng)；度與多項式的算法相當(dāng)；4. 采用近似算法或者啟發(fā)式方法，如局部搜索、模擬退火、采用近似算法或者啟發(fā)式方法，如局部搜索、模擬退火、 遺傳算法等。遺傳算法等。 對基于對基于SP 模型尋找最優(yōu)多重序列比對這樣一個問題，模型尋找最優(yōu)多重序

17、列比對這樣一個問題，可以用近似的方法求解，其算法的時間復(fù)雜度可用多項式表示?？梢杂媒频姆椒ㄇ蠼?，其算法的時間復(fù)雜度可用多項式表示。4.2.3 優(yōu)化計算方法優(yōu)化計算方法標(biāo)準(zhǔn)動態(tài)規(guī)劃算法存在的問題：標(biāo)準(zhǔn)動態(tài)規(guī)劃算法存在的問題： 搜索空間大搜索空間大剪枝技術(shù)：將搜索空間限定在一個較小的區(qū)域范圍內(nèi)。剪枝技術(shù)：將搜索空間限定在一個較小的區(qū)域范圍內(nèi)。若問題是搜索一條得分最高或代價最小的路徑，則在若問題是搜索一條得分最高或代價最小的路徑，則在搜索時如果當(dāng)前路徑的得分低于某個下限或累積代價已搜索時如果當(dāng)前路徑的得分低于某個下限或累積代價已經(jīng)超過某個上限），則對當(dāng)前路徑進(jìn)行剪枝，即不再搜索經(jīng)超過某個上限），則

18、對當(dāng)前路徑進(jìn)行剪枝，即不再搜索當(dāng)前路徑的后續(xù)空間。當(dāng)前路徑的后續(xù)空間。Biocomputing technology Multiple sequence alignmentBiocomputing technology Multiple sequence alignment 在序列兩兩比對中在序列兩兩比對中, Fickett 和和Ukkonen 設(shè)計了一種設(shè)計了一種稱為定界約束過程稱為定界約束過程 (bounding procedure)的方法來縮小搜的方法來縮小搜索空間索空間,減少計算量減少計算量, 其中距離矩陣的上界和下界可以預(yù)先其中距離矩陣的上界和下界可以預(yù)先確定或動態(tài)變化。確定或動態(tài)變

19、化。 為了在多維空間上使用動態(tài)規(guī)劃算法，為了在多維空間上使用動態(tài)規(guī)劃算法，Carrillo 和和Lipman 將這種思想引入到多重序列比對，即先進(jìn)行初步將這種思想引入到多重序列比對，即先進(jìn)行初步的序列雙重比對，以限制進(jìn)一步做多重序列全面比對所需的序列雙重比對，以限制進(jìn)一步做多重序列全面比對所需要的多維空間的大小和計算量，從而克服了多序列的維數(shù)、要的多維空間的大小和計算量，從而克服了多序列的維數(shù)、空間和運算量之間的矛盾空間和運算量之間的矛盾 Carrillo-Lipman的優(yōu)化計算方法的優(yōu)化計算方法Biocomputing technology Multiple sequence alignme

20、nt 設(shè)設(shè)k 條序列的長度分別為條序列的長度分別為n1n2nk，按照，按照SP 得分模得分模型計算這些序列的最優(yōu)比對。依然采用動態(tài)規(guī)劃方法，但型計算這些序列的最優(yōu)比對。依然采用動態(tài)規(guī)劃方法，但并不計算超晶格空間中所有的節(jié)點，而是僅處理與最優(yōu)路并不計算超晶格空間中所有的節(jié)點，而是僅處理與最優(yōu)路徑徑“相關(guān)相關(guān)的節(jié)點。但是，哪些節(jié)點是相關(guān)的呢？這需要觀的節(jié)點。但是，哪些節(jié)點是相關(guān)的呢？這需要觀察節(jié)點在兩條序列上的投影。察節(jié)點在兩條序列上的投影。確定相關(guān)節(jié)點的方法：確定相關(guān)節(jié)點的方法： 假設(shè)假設(shè)是關(guān)于是關(guān)于k 條序列條序列s1s2sk 的最優(yōu)多重比對。的最優(yōu)多重比對。從某個節(jié)點向任何兩條序列所在的平面

21、投影，如果該投影從某個節(jié)點向任何兩條序列所在的平面投影，如果該投影是這兩條序列兩兩最優(yōu)比對的一部分前面一部分），那么是這兩條序列兩兩最優(yōu)比對的一部分前面一部分），那么該節(jié)點是與最優(yōu)比對相關(guān)的節(jié)點。該節(jié)點是與最優(yōu)比對相關(guān)的節(jié)點。 問題的提出問題的提出: 一種計算兩條序列經(jīng)過特定斷點的最優(yōu)比對的算法一種計算兩條序列經(jīng)過特定斷點的最優(yōu)比對的算法Biocomputing technology Multiple sequence alignment設(shè)有兩條序列設(shè)有兩條序列s、t, |s|=m, |t|=n;位點位點i 將序列將序列s一分為二一分為二, 位點位點j將序列將序列t一分為二一分為二, 那么那么

22、:序列序列s、t 對于經(jīng)過特定斷點對于經(jīng)過特定斷點i、j的最優(yōu)比對可分為兩個部分的最優(yōu)比對可分為兩個部分: 對應(yīng)于兩條序列前綴對應(yīng)于兩條序列前綴0:s:i 與與0:t:j 的最優(yōu)比對的最優(yōu)比對; 對應(yīng)于兩條序列后綴對應(yīng)于兩條序列后綴 i:s:m與與j:t:n 的最優(yōu)比對的最優(yōu)比對; 例例: :Biocomputing technology Multiple sequence alignment比對兩條序列比對兩條序列: s=ATTCGG, t=GATTC打分函數(shù)打分函數(shù): p(a,a)=1, p(a,b)=-1, p(a,-)=p(-,b)=-1Biocomputing technology

23、Multiple sequence alignment 如果超晶格空間中的一個節(jié)點想任意兩條序列所在如果超晶格空間中的一個節(jié)點想任意兩條序列所在的平面投影的平面投影,投影在這些投影在這些” 斷點斷點中中,則超晶格空間中的這則超晶格空間中的這個節(jié)點就是與最優(yōu)路徑相關(guān)的節(jié)點個節(jié)點就是與最優(yōu)路徑相關(guān)的節(jié)點,否則不是相關(guān)節(jié)點否則不是相關(guān)節(jié)點.小結(jié)小結(jié): 在進(jìn)行多重序列比對時在進(jìn)行多重序列比對時, 首先要進(jìn)行序列的兩兩比對首先要進(jìn)行序列的兩兩比對,其目的就是要找到任意兩條序列通過特定斷點的最優(yōu)比對其目的就是要找到任意兩條序列通過特定斷點的最優(yōu)比對,找到這些斷點找到這些斷點,然后然后,將多重比對中的超晶格

24、空間的節(jié)點向?qū)⒍嘀乇葘χ械某Ц窨臻g的節(jié)點向任意兩條序列所在的平面投影任意兩條序列所在的平面投影,看看投影是否在這些斷點上看看投影是否在這些斷點上,如果節(jié)點向各個平面的投影均在相應(yīng)的斷點上如果節(jié)點向各個平面的投影均在相應(yīng)的斷點上,則這個節(jié)點則這個節(jié)點是與多重序列比對的最優(yōu)路徑相關(guān)的節(jié)點是與多重序列比對的最優(yōu)路徑相關(guān)的節(jié)點,否則否則,就不是相就不是相關(guān)節(jié)點關(guān)節(jié)點,要進(jìn)行要進(jìn)行剪枝剪枝處置處置.Biocomputing technology Multiple sequence alignment(1) 設(shè)設(shè) 是關(guān)于是關(guān)于s1s2sk 的最優(yōu)比對，假如的最優(yōu)比對，假如 SP_score( ) L，那

25、么，那么 score( i,j ) Li,j (4-6 )其中，其中， score( i,j ) 是是 在在si 和和sj 所在平面投影的得分所在平面投影的得分, 這里這里,L實際上是最優(yōu)多重序列比對的一個下限實際上是最優(yōu)多重序列比對的一個下限, Lij是序列是序列si 和序列和序列sj 比對得分的一個下限比對得分的一個下限 雖然最優(yōu)多重比對的投影不一定是兩兩最優(yōu)比對，雖然最優(yōu)多重比對的投影不一定是兩兩最優(yōu)比對，但是我們可以為投影的得分設(shè)立一個下限。但是我們可以為投影的得分設(shè)立一個下限。 ) )s,(sim(sLLj)(i,y)(x,y,xyxij判斷超晶格空間中一個節(jié)點是否是相關(guān)節(jié)點的方法：

26、判斷超晶格空間中一個節(jié)點是否是相關(guān)節(jié)點的方法：Biocomputing technology Multiple sequence alignment(2) 現(xiàn)在的問題現(xiàn)在的問題: 需要判斷超晶格中的一個節(jié)點需要判斷超晶格中的一個節(jié)點 i = (i1,i2,ik ) 是是否在否在L 的限制下與最優(yōu)比對相關(guān)。的限制下與最優(yōu)比對相關(guān)。 (3) 簡單地說簡單地說, 如果一個節(jié)點的所有投影滿足如果一個節(jié)點的所有投影滿足(4-6 )式的式的 條件，則該節(jié)點是相關(guān)的。若條件不滿足，條件，則該節(jié)點是相關(guān)的。若條件不滿足， 即即score( i,j )小，則該節(jié)點不可能是相關(guān)的，小，則該節(jié)點不可能是相關(guān)的， 因

27、而，因而，i 肯定不會處于最優(yōu)路徑上?？隙ú粫幱谧顑?yōu)路徑上。 (4) 公式公式(4-6)的條件只是一個必要條件，但不是充分條件。的條件只是一個必要條件，但不是充分條件。 滿足條件只是說明滿足條件只是說明i 可能處于最優(yōu)路徑，但不一定處于可能處于最優(yōu)路徑，但不一定處于 最優(yōu)路徑。公式最優(yōu)路徑。公式(4-6)條件的作用是限制搜索空間，進(jìn)步條件的作用是限制搜索空間，進(jìn)步 算法的實施效率。算法的實施效率。 Biocomputing technology Multiple sequence alignment(5) 將判斷條件公式將判斷條件公式(4-6)進(jìn)一步具體化，進(jìn)一步具體化， 則對于所有的則對于

28、所有的1xyk，如果，如果i 滿足滿足 Cx,y ix,iy Lx,y （4-7 ） 則則i 是相關(guān)的。是相關(guān)的。 這里，這里， Cx,y是序列是序列sx 和和sy 的總得分矩陣的總得分矩陣; Cx,y ix,iy 表示在點表示在點 ix,iy 處的值處的值,即即 經(jīng)過經(jīng)過ix,iy斷點的斷點的sx和和sy的最優(yōu)比對得分的最優(yōu)比對得分 ; ix,iy是斷點是斷點; Lx,y是是sx 和和sy 的比對得分的下限的比對得分的下限 注意注意: 盡管不是所有的相關(guān)節(jié)點均參與最優(yōu)比對盡管不是所有的相關(guān)節(jié)點均參與最優(yōu)比對, 但只有與最優(yōu)路徑相關(guān)的節(jié)點才參與最優(yōu)比對但只有與最優(yōu)路徑相關(guān)的節(jié)點才參與最優(yōu)比對.

29、Biocomputing technology Multiple sequence alignment(6) 判斷非相關(guān)節(jié)點的方法判斷非相關(guān)節(jié)點的方法: 假設(shè)假設(shè)是關(guān)于是關(guān)于s1s2sk 的最優(yōu)比對，其所對應(yīng)的的最優(yōu)比對，其所對應(yīng)的路徑通過節(jié)點路徑通過節(jié)點 i= ( i1,i2,ix,iy,ik ),那么那么: Cx,y ix,iy Score(i,j) Lx,y反之反之, 假如假如 Cx,y ix,iy Lx,y ,則多重序列最優(yōu)比對則多重序列最優(yōu)比對路徑不會經(jīng)過節(jié)點路徑不會經(jīng)過節(jié)點 i= ( i1,i2,ix,iy,ik ), 因而因而,該超該超晶格節(jié)點是非相關(guān)節(jié)點晶格節(jié)點是非相關(guān)節(jié)點.

30、Biocomputing technology Multiple sequence alignment 為了得到一個合理的下限為了得到一個合理的下限 L，我們可以任選一個包含，我們可以任選一個包含所有序列的多重比對，計算其得分，以此作為所有序列的多重比對，計算其得分，以此作為 L。若選取。若選取的的 L 接近于最優(yōu)值，算法速度將大大提高。接近于最優(yōu)值，算法速度將大大提高。注意：注意：L 的值不能超過最優(yōu)值，否則算法出錯。的值不能超過最優(yōu)值，否則算法出錯。 在實現(xiàn)上述優(yōu)化計算方法時，必須非常仔細(xì)。不可能在實現(xiàn)上述優(yōu)化計算方法時，必須非常仔細(xì)。不可能對超晶格中的每一個節(jié)點都進(jìn)行上述判斷，否則，計算

31、時對超晶格中的每一個節(jié)點都進(jìn)行上述判斷，否則，計算時間不會有多大的減少。我們需要一種完全消除無關(guān)單元的間不會有多大的減少。我們需要一種完全消除無關(guān)單元的方法方法, 以便不需再處理它們。以便不需再處理它們。下面介紹一種可能的策略下面介紹一種可能的策略:Biocomputing technology Multiple sequence alignment 在計算機(jī)中實現(xiàn)在計算機(jī)中實現(xiàn)“剪枝剪枝技術(shù)的措施技術(shù)的措施-1: 從超晶格的零點從超晶格的零點0 = (0, 0, , 0) 動身動身, 此節(jié)點總此節(jié)點總 是相關(guān)的是相關(guān)的, 并影響依賴于它的節(jié)點并影響依賴于它的節(jié)點. 每個這樣的節(jié)點每個這樣的節(jié)

32、點 又有它自己的受影響的節(jié)點又有它自己的受影響的節(jié)點, 如此展開如此展開, 直至達(dá)到在直至達(dá)到在 最終角落的節(jié)點最終角落的節(jié)點( n1n2nk ).(2) 以數(shù)組以數(shù)組a 保存各節(jié)點的計算結(jié)果保存各節(jié)點的計算結(jié)果. 如果在計算如果在計算a j 時用到時用到i, 稱節(jié)點稱節(jié)點i 影響另一個節(jié)點影響另一個節(jié)點j, 又稱又稱,節(jié)點節(jié)點j 依賴于節(jié)點依賴于節(jié)點i。 每個節(jié)點依賴于至多每個節(jié)點依賴于至多2k-1個其它節(jié)點個其它節(jié)點,也至多影響也至多影響 2k-1個其它節(jié)點個其它節(jié)點.(3) 節(jié)點節(jié)點i 和節(jié)點和節(jié)點j 關(guān)系的另一特征是：關(guān)系的另一特征是：b=j- i b是一個非零的二進(jìn)向量是一個非零的二

33、進(jìn)向量.Biocomputing technology Multiple sequence alignment在計算機(jī)中實現(xiàn)在計算機(jī)中實現(xiàn)“剪枝剪枝技術(shù)的措施技術(shù)的措施-2:(4) 為了便于處理，設(shè)置一個緩沖區(qū)，該緩沖區(qū)內(nèi)僅存放為了便于處理，設(shè)置一個緩沖區(qū)，該緩沖區(qū)內(nèi)僅存放 相關(guān)節(jié)點的后續(xù)節(jié)點。相關(guān)節(jié)點的后續(xù)節(jié)點。(5) 首先將首先將0 放入其中。放入其中。(6) 當(dāng)節(jié)點當(dāng)節(jié)點i 進(jìn)入緩沖區(qū)時，其對應(yīng)的值進(jìn)入緩沖區(qū)時，其對應(yīng)的值a i 被初始化，被初始化， 然后然后a i 的值在隨后的階段中被更新。的值在隨后的階段中被更新。 當(dāng)節(jié)點當(dāng)節(jié)點i 離開緩沖區(qū)時，其值即為該點真正的值，并用離開緩沖區(qū)時

34、，其值即為該點真正的值，并用 于其他節(jié)點于其他節(jié)點(依賴于此節(jié)點依賴于此節(jié)點)的計算。的計算。(7) 節(jié)點節(jié)點i 的后續(xù)節(jié)點是否要計算，還取決于的后續(xù)節(jié)點是否要計算，還取決于i 是否為相關(guān)是否為相關(guān) 節(jié)點，若不是，則不再計算其后續(xù)的其他節(jié)點。節(jié)點，若不是，則不再計算其后續(xù)的其他節(jié)點。具體實現(xiàn)過程具體實現(xiàn)過程:Biocomputing technology Multiple sequence alignment設(shè)節(jié)點設(shè)節(jié)點j 是一個依賴于節(jié)點是一個依賴于節(jié)點i 的相關(guān)節(jié)點，的相關(guān)節(jié)點，如果如果j 不在緩沖區(qū)內(nèi)，則將其放入緩沖區(qū)，并計算不在緩沖區(qū)內(nèi)，則將其放入緩沖區(qū)，并計算 a j a i +SP

35、_Score( Colum(s, i, b) )(3) 如果如果j 早已在緩沖區(qū)中，則按下式更新早已在緩沖區(qū)中，則按下式更新 a j max( a j , a i +SP_Score( Colum(s,i, b) ) )注意注意: Carrilo-Lipman 算法要求待比較的多個序列具有較大算法要求待比較的多個序列具有較大 的相似性，并且序列數(shù)不能太多。的相似性，并且序列數(shù)不能太多。4.2.4 星形比對星形比對Biocomputing technology Multiple sequence alignment* 啟發(fā)式方法作為首選。啟發(fā)式方法作為首選。* 啟發(fā)式方法不一定保證最終能得到最優(yōu)

36、解，但在大多數(shù)啟發(fā)式方法不一定保證最終能得到最優(yōu)解，但在大多數(shù) 情況下，其計算結(jié)果接近于最優(yōu)結(jié)果。情況下，其計算結(jié)果接近于最優(yōu)結(jié)果。* 啟發(fā)式這類方法能夠大大減少所需的計算時間，加快計啟發(fā)式這類方法能夠大大減少所需的計算時間，加快計 算速度。算速度。 * 漸進(jìn)法是多重序列比對中常用到的啟發(fā)式方法。其基本漸進(jìn)法是多重序列比對中常用到的啟發(fā)式方法。其基本 思想是將序列多重比對轉(zhuǎn)化為序列兩兩比對，逐漸將兩思想是將序列多重比對轉(zhuǎn)化為序列兩兩比對，逐漸將兩 兩比對組合起來，最終形成完整的多序列比對。兩比對組合起來，最終形成完整的多序列比對。 * 組合兩兩序列比對的方法有：組合兩兩序列比對的方法有： 星形

37、結(jié)構(gòu)或者樹形結(jié)構(gòu)。星形結(jié)構(gòu)或者樹形結(jié)構(gòu)。 1. 星形比對的基本思想：星形比對的基本思想： 星形比對是一種啟發(fā)式方法，首先由星形比對是一種啟發(fā)式方法，首先由Gusfield 提出。提出。 在給定的若干序列中，選擇一個核心序列，通過該序在給定的若干序列中，選擇一個核心序列，通過該序列與其它序列的兩兩比對形成所有序列的多重比對列與其它序列的兩兩比對形成所有序列的多重比對 ，從，從而使得而使得 在核心序列和任何一個其它序列方向的投影是最在核心序列和任何一個其它序列方向的投影是最優(yōu)的兩兩比對。優(yōu)的兩兩比對。Biocomputing technology Multiple sequence alignme

38、nt2. 星形比對算法概述星形比對算法概述-1Biocomputing technology Multiple sequence alignment* 設(shè)設(shè)s1,s2,sk是是k 條待比對的序列。條待比對的序列。* 假設(shè)已知核心序列是假設(shè)已知核心序列是sc，1c k，則可以利用標(biāo)準(zhǔn)的，則可以利用標(biāo)準(zhǔn)的 動態(tài)規(guī)劃算法求出所有動態(tài)規(guī)劃算法求出所有sc 和和si 的最優(yōu)兩兩比對。的最優(yōu)兩兩比對。 這個工作的時間復(fù)雜度為這個工作的時間復(fù)雜度為O(kn2), 假設(shè)所有序列的長度約為假設(shè)所有序列的長度約為n。* 將這些序列的兩兩比對聚集起來，并采用將這些序列的兩兩比對聚集起來，并采用“只要是空位，那么只要

39、是空位，那么 永遠(yuǎn)是空位永遠(yuǎn)是空位的原則。的原則。* 聚集過程從某一個兩兩比對開始，然后逐步加上其他的兩聚集過程從某一個兩兩比對開始，然后逐步加上其他的兩 兩比對。在這個過程中，逐步增加兩比對。在這個過程中，逐步增加sc中的空位字符，以適應(yīng)中的空位字符，以適應(yīng) 其他的比對，但決不刪除其他的比對，但決不刪除sc中已存在的空位字符。中已存在的空位字符。2. 星形比對算法概述星形比對算法概述-2Biocomputing technology Multiple sequence alignment* 隨著后續(xù)比對的不斷加入隨著后續(xù)比對的不斷加入, 一方面我們有一個由一方面我們有一個由sc指導(dǎo)的、指導(dǎo)的

40、、 已經(jīng)建立好的部分序列的多重比對，另一方面我們有已經(jīng)建立好的部分序列的多重比對，另一方面我們有sc與與 一個新序列之間的比對。在兩種比對中我們插入盡可能少一個新序列之間的比對。在兩種比對中我們插入盡可能少 而必要的空位而必要的空位, 以保持與擴(kuò)展的以保持與擴(kuò)展的sc序列相匹配。然后序列相匹配。然后,將新將新 擴(kuò)展的序列加入序列群中擴(kuò)展的序列加入序列群中, 且它和其它擴(kuò)展的序列具有相且它和其它擴(kuò)展的序列具有相 同的長度。同的長度。 * 這個過程一直進(jìn)行到所有的兩兩比對都加入以后結(jié)束，這這個過程一直進(jìn)行到所有的兩兩比對都加入以后結(jié)束，這 一步所需的計算量為一步所需的計算量為O(k2n)。* 算法

41、總的時間復(fù)雜度為算法總的時間復(fù)雜度為O(kn2+k2n)。scs1s2sk(sc, s1) (sc, s2) (sc, sk)兩兩比對兩兩比對 多重比對多重比對Biocomputing technology Multiple sequence alignment方法方法1：嘗試將每一個序列分別作為核心序列，：嘗試將每一個序列分別作為核心序列， 進(jìn)行星形多重序列比對，取比對結(jié)果最進(jìn)行星形多重序列比對，取比對結(jié)果最 好的一個。即好的一個。即SP得分最高的為最好。得分最高的為最好。方法方法2：是計算所有的兩兩比對，取下式值最大：是計算所有的兩兩比對，取下式值最大 的一個：的一個：3. 如何選擇核心序

42、列？如何選擇核心序列？Biocomputing technology Multiple sequence alignmentcici)s,ssim( 4.舉例舉例 有有5 5個序列：個序列： s1 = ATTGCCATTs1 = ATTGCCATT s2 = ATGGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s3 = ATCCAATTTT s4 = ATCTTCTT s4 = ATCTTCTT s5 =ACTGACC s5 =ACTGACCsc=s1ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATTATGGCCATT ATC-CAA

43、TTTT ATCTTC-TT ACTGACC- (s1,s2) (s1,s3) (s1,s4) (s1,s5)ATTGCCATT-ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC- Biocomputing technology Multiple sequence alignment 星形比對是一種多重序列比對近似的方法，然星形比對是一種多重序列比對近似的方法，然而是一種比較好的近似方法。如果用代價來評判多而是一種比較好的近似方法。如果用代價來評判多重序列的比對結(jié)果，則可以證明，用該方法所得到重序列的比對結(jié)果，則可以證明，用該方法所得到多重序列比對的代價不會大

44、于最優(yōu)多重序列比對代多重序列比對的代價不會大于最優(yōu)多重序列比對代價的兩倍。價的兩倍。 Biocomputing technology Multiple sequence alignment4.2.5 樹形比對樹形比對k k個待比對的序列個待比對的序列 具有具有k k個葉節(jié)點的樹個葉節(jié)點的樹每個葉節(jié)點對應(yīng)一條序列每個葉節(jié)點對應(yīng)一條序列將序列賦予樹的內(nèi)部節(jié)點，可以計算樹中每個分支的權(quán)值。將序列賦予樹的內(nèi)部節(jié)點，可以計算樹中每個分支的權(quán)值。權(quán)值代表對應(yīng)分支連接的兩個序列之間的相似性。權(quán)值代表對應(yīng)分支連接的兩個序列之間的相似性。所有權(quán)值的和就是這棵樹的得分所有權(quán)值的和就是這棵樹的得分樹形比對的問題：尋

45、找一種樹的內(nèi)部節(jié)點序列賦予方式，樹形比對的問題：尋找一種樹的內(nèi)部節(jié)點序列賦予方式， 使得樹的得分最大。使得樹的得分最大。星型比對可以看作是樹形比對的一種特例。星型比對可以看作是樹形比對的一種特例。Biocomputing technology Multiple sequence alignment將將CT、CG、CT分別賦予節(jié)點分別賦予節(jié)點 x、y、z，則樹的得分為，則樹的得分為8。CTCGCT多重序列比對多重序列比對 兩兩序列比對兩兩序列比對 合并兩個比對比對的比對）合并兩個比對比對的比對） Aligment of AlignmentAA算法算法打分函數(shù)：打分函數(shù)： Pa,a）=1 Pa,b

46、）= 0 （ab） Pa,-）=P（-,b）= -1111122G - TG - TC A TC A TC - GC - GC T GC T G比對結(jié)果：比對結(jié)果：Biocomputing technology Multiple sequence alignmentAA算法概述算法概述-1Biocomputing technology Multiple sequence alignment假設(shè)有兩個多重比對假設(shè)有兩個多重比對1和和2 1代表序列代表序列s1,s2,si的多重比對的多重比對 2代表序列代表序列t1,t2,tj的多重比對的多重比對并且并且,( s1,s2,si ) ( t1,t2,

47、tj )= 代表代表s1和和t1的兩兩比對的兩兩比對, 那么那么計算與計算與相一致的相一致的1 和和2比對的算法如下比對的算法如下:AA算法概述算法概述-2Biocomputing technology Multiple sequence alignment標(biāo)定標(biāo)定1的各列的各列, 如果如果s1在比對中對應(yīng)位置的編輯操作不是在比對中對應(yīng)位置的編輯操作不是插入或刪除插入或刪除,則這些列分別標(biāo)記為則這些列分別標(biāo)記為s1對應(yīng)位置上的字符對應(yīng)位置上的字符: a1,a2,al1 s1=l1 標(biāo)定標(biāo)定2的各列的各列, 如果如果t1在比對中對應(yīng)位置的編輯操作不在比對中對應(yīng)位置的編輯操作不是是 插入或刪除插入

48、或刪除,則這些列分別標(biāo)記為則這些列分別標(biāo)記為t1對應(yīng)位置上的字符對應(yīng)位置上的字符: b1,b2,bl2 t1=l2 對對a1,a2,al1 和和b1,b2,bl2 進(jìn)行比對進(jìn)行比對, 在所得到的比對中在所得到的比對中,對于對于1、2和和中原來有插入或刪除中原來有插入或刪除操操 作的位置作的位置, 恢復(fù)其原有的實際字符或空位字符恢復(fù)其原有的實際字符或空位字符”-”.Biocomputing technology Multiple sequence alignmenta1 a2a3a4b1 b2b3b4b5對于對于n n個序列的樹形比對的基本算法過程如下：個序列的樹形比對的基本算法過程如下：（1

49、1初始化，對于每個序列，生成一個葉節(jié)點初始化，對于每個序列，生成一個葉節(jié)點（2 2利用利用AAAA算法合并兩個節(jié)點，形成一個新節(jié)點，算法合并兩個節(jié)點，形成一個新節(jié)點， 合并的結(jié)果放在新節(jié)點中，原來的兩個節(jié)點作為合并的結(jié)果放在新節(jié)點中，原來的兩個節(jié)點作為 新節(jié)點的子節(jié)點新節(jié)點的子節(jié)點（3 3反復(fù)執(zhí)行反復(fù)執(zhí)行2 2），直到形成），直到形成n n個葉節(jié)點的樹根為止，個葉節(jié)點的樹根為止， 根節(jié)點中的序列即為最終的多重比對結(jié)果。根節(jié)點中的序列即為最終的多重比對結(jié)果。 s1 s2 s3 s41122Biocomputing technology Multiple sequence alignment4.2

50、.6 CLUSTAL 算法算法Biocomputing technology Multiple sequence alignment CLUSTAL 算法是一種漸進(jìn)的比對方法，它是由算法是一種漸進(jìn)的比對方法，它是由D.G.Higgins和和 P.M.Sharp 于于1988年首次提出的。年首次提出的。目的：目的： 對來自不同物種的功能相同或相似的蛋白進(jìn)行比對對來自不同物種的功能相同或相似的蛋白進(jìn)行比對和聚類分析，可對這些物種的親緣關(guān)系進(jìn)行判斷，并且和聚類分析，可對這些物種的親緣關(guān)系進(jìn)行判斷，并且對這些蛋白在生物進(jìn)化過程中的保守性作出估計。對這些蛋白在生物進(jìn)化過程中的保守性作出估計。 Clust

51、al算法包括三個階段：算法包括三個階段：1. 1. 先將多重序列進(jìn)行兩兩比對?；谶@些比對，計算得到先將多重序列進(jìn)行兩兩比對?；谶@些比對，計算得到 一個距離矩陣，該矩陣反映每對序列之間的關(guān)系。一個距離矩陣，該矩陣反映每對序列之間的關(guān)系。2. 2. 根據(jù)距離矩陣計算產(chǎn)生系統(tǒng)發(fā)育樹，以此來確定被比較根據(jù)距離矩陣計算產(chǎn)生系統(tǒng)發(fā)育樹，以此來確定被比較 序列間相似的程度序列間相似的程度3. 3. 有了這棵系統(tǒng)發(fā)育樹的指導(dǎo)，從關(guān)系最緊密的兩條序列有了這棵系統(tǒng)發(fā)育樹的指導(dǎo)，從關(guān)系最緊密的兩條序列 開場，逐步引入鄰近的序列或序列組，并不斷重新構(gòu)建開場，逐步引入鄰近的序列或序列組，并不斷重新構(gòu)建 比對，直到所

52、有序列都被加入為止。比對，直到所有序列都被加入為止。Biocomputing technology Multiple sequence alignment舉例：舉例：Biocomputing technology Multiple sequence alignment已知三級結(jié)構(gòu)的七個球蛋白序列，分別為：已知三級結(jié)構(gòu)的七個球蛋白序列，分別為： Hbb_Human : 人的人的-球蛋白球蛋白Hbb_Horse : 馬的馬的-球蛋白球蛋白 Hba_Human : 人的人的-球蛋白球蛋白Hba_Horse : 馬的馬的-球蛋白球蛋白 Myg_phyca : 抹香鯨的血紅蛋白抹香鯨的血紅蛋白 Glb5

53、_petma : 七鰓鰻藍(lán)血紅蛋白七鰓鰻藍(lán)血紅蛋白Lgb2_Luplu : 羽扇豆的豆血紅蛋白羽扇豆的豆血紅蛋白第一階段：兩兩比對產(chǎn)生距離矩陣第一階段：兩兩比對產(chǎn)生距離矩陣Biocomputing technology Multiple sequence alignment 用完全動態(tài)規(guī)劃法計算的用完全動態(tài)規(guī)劃法計算的7個球蛋白序列之間的個球蛋白序列之間的77的距離矩陣的距離矩陣 第二階段：產(chǎn)生指導(dǎo)樹第二階段：產(chǎn)生指導(dǎo)樹Biocomputing technology Multiple sequence alignment 根據(jù)第一階段結(jié)果中的距離矩陣，用鄰近歸并法來根據(jù)第一階段結(jié)果中的距離矩陣

54、，用鄰近歸并法來計算產(chǎn)生一棵有分枝長度和序列權(quán)重的有根樹。計算產(chǎn)生一棵有分枝長度和序列權(quán)重的有根樹。 第三階段：漸進(jìn)的比對第三階段：漸進(jìn)的比對Biocomputing technology Multiple sequence alignment 這一階段基本的步驟是通過一系列兩兩比對來構(gòu)建更這一階段基本的步驟是通過一系列兩兩比對來構(gòu)建更大的比對序列組。按照指導(dǎo)樹中的分支順序，從有根樹的大的比對序列組。按照指導(dǎo)樹中的分支順序，從有根樹的末梢到樹根逐漸進(jìn)行。根據(jù)圖末梢到樹根逐漸進(jìn)行。根據(jù)圖4.22的有根樹，通過下面的的有根樹，通過下面的順序?qū)π蛄羞M(jìn)行比對：順序?qū)π蛄羞M(jìn)行比對：(1)對對(2)(3)

55、對對(4)(8)對對(9) (5)對對(10)(6)對對(11)(7)對對(12)。* 每一階段使用了有殘基權(quán)重矩陣和空位開放及空位擴(kuò)展罰每一階段使用了有殘基權(quán)重矩陣和空位開放及空位擴(kuò)展罰 分的完全動態(tài)規(guī)劃算法。分的完全動態(tài)規(guī)劃算法。* 每一階段都由對兩個已經(jīng)存在的排列或序列進(jìn)行比對組成。每一階段都由對兩個已經(jīng)存在的排列或序列進(jìn)行比對組成。* 在先前比對中出現(xiàn)的空位仍然是固定的在先前比對中出現(xiàn)的空位仍然是固定的 圖4.23Biocomputing technology Multiple sequence alignment序列權(quán)重的作用序列權(quán)重的作用: 計算多重序列比對得分計算多重序列比對得分

56、Biocomputing technology Multiple sequence alignment peeksavtalpeeksavtal geekaavlalgeekaavlal padktnvkaapadktnvkaa aadktnvkaaaadktnvkaa egewqlvlhvegewqlvlhv aaektkirsaaaektkirsa多重序列比對的統(tǒng)計特征分析多重序列比對的統(tǒng)計特征分析 對于所得到的多重序列比對，我們往往需要進(jìn)行歸納分對于所得到的多重序列比對，我們往往需要進(jìn)行歸納分析，總結(jié)這些序列的特征，或者給出這些序列共性的表示。析，總結(jié)這些序列的特征，或者給出這些序列共性

57、的表示。表示方式表示方式1 1：保守序列表示方式：保守序列表示方式 表示出序列每個位置上最可能出現(xiàn)的字符表示出序列每個位置上最可能出現(xiàn)的字符 或所有可能出現(xiàn)的字符或所有可能出現(xiàn)的字符表示方式表示方式2 2；特征統(tǒng)計圖譜；特征統(tǒng)計圖譜profileprofile表示方式表示方式 （或特征統(tǒng)計矩陣表示方法）（或特征統(tǒng)計矩陣表示方法）Biocomputing technology Multiple sequence alignment令令P=(P1,P2,Pj,PL )；P表示在多重比對表示在多重比對的每一列上各種的每一列上各種 字符出現(xiàn)的概率分布字符出現(xiàn)的概率分布Pj=(pj0,pj1,pj|A|

58、)；A代表字母表，代表字母表， Pjk代表字母表代表字母表A中第中第k個字符在第個字符在第j列列 出現(xiàn)的概率。出現(xiàn)的概率。 pj0：第：第0個字符是特殊的空位符號個字符是特殊的空位符號“-”。稱稱P為多重序列比對為多重序列比對的特征統(tǒng)計圖譜或特征統(tǒng)計矩陣。的特征統(tǒng)計圖譜或特征統(tǒng)計矩陣。 P反映了多重序列比對反映了多重序列比對各個列的特征。各個列的特征。表示方法表示方法2 2：特征統(tǒng)計圖譜：特征統(tǒng)計圖譜Biocomputing technology Multiple sequence alignment 1 2 3 4 5 (位置位置) A 0.8 0.2 0.2 0.6 0.0 T 0.0 0

59、.4 0.6 0.4 1.0 C 0.2 0.2 0.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （堿基）（堿基）Biocomputing technology Multiple sequence alignment A T T A T A A C T T C T T A T A C T T T A G A A T 利用保守序列或者特征統(tǒng)計圖可以判斷一個序列是否滿足利用保守序列或者特征統(tǒng)計圖可以判斷一個序列是否滿足一定的特征一定的特征 給定一個序列給定一個序列s=a1a2ams=a1a2am，定義字符，定義字符a a在第在第j j位的代價為位的代價為 其中，其中，|A|A|

60、代表字母表代表字母表A A的長度，的長度， AkAk代表代表A A的第的第k k個字符，個字符， A0A0代表空缺字符代表空缺字符“-”-”。整個序列。整個序列s s的代價為的代價為|0),(),( AkjkkPAawjawjjawsw),( ),(*一條序列與特征統(tǒng)計圖相對照，如果代價值小，說明該序一條序列與特征統(tǒng)計圖相對照，如果代價值小，說明該序列具有相應(yīng)的特征，否則該序列不具備相應(yīng)的特征。列具有相應(yīng)的特征，否則該序列不具備相應(yīng)的特征。 Biocomputing technology Multiple sequence alignment4.2.7 隱馬爾可夫模型隱馬爾可夫模型 HMMBi