隱馬爾可夫模型

隱馬爾可夫模型

HiddenMarkovModel

HiddenMarkovModel

思考題：對給定的一定長度的DNA序列，識別其上CpG島大致位的方法。兩個問題：（1）給定一段DNA序列片段，判斷它是否是CpG島？對應(yīng)于Markov模型問題（2）給定一段DNA序列，識別其中的CpG島？對應(yīng)于隱Markov模型問題主要內(nèi)容隱馬爾可夫模型的基本概念隱馬爾可夫模型中的三個基本問題隱馬爾可夫模型的生物信息學(xué)應(yīng)用—CpG島識別

一、隱馬爾可夫模型的基本概念

隱馬爾可夫模型（hiddenMarkovmodel,記作：HMM）是馬爾可夫模型的進(jìn)一步發(fā)展。其在生物信息學(xué)分析中得到了廣泛的應(yīng)用。（1）HMM的基本概念

馬爾可夫模型主要是把一個總隨機過程看成一系列狀態(tài)的不斷轉(zhuǎn)移，其特性主要使用“轉(zhuǎn)移概率”來表示。HMM則認(rèn)為模型的狀態(tài)是不可觀測的（這是“隱”的由來）。能觀測到的只是它表現(xiàn)出的一些觀測值（observations）123a12a21a22a11a23a32a13a31a33例：隱馬爾可夫鏈—觀測三個硬幣狀態(tài)

每個硬幣代表一個狀態(tài);每個狀態(tài)有兩個觀測值:正面H和反面T;

每個狀態(tài)產(chǎn)生H的概率：P(H);

每個狀態(tài)產(chǎn)生T的概率為：1-P(H)對比兩個模型可見：馬爾可夫模型的觀測序列本身就是狀態(tài)序列；隱馬爾可夫模型的觀測序列不是狀態(tài)序列；設(shè)有N個籃子，每個都裝了許多彩色小球，小球顏色有M種.現(xiàn)在按下列步驟產(chǎn)生出一個輸出符號(顏色)序列:按某個初始概率分布，隨機的選定一個籃子，從中隨機地取出一個球，記錄球的顏色作為第一個輸出符號，并把球放回原來的籃子.然后按照某個轉(zhuǎn)移概率分布(與當(dāng)前籃子相聯(lián)系)選擇一個新的籃子(也可能仍停留在當(dāng)前籃子)，并從中隨機取出一個球，記下顏色作為第二個輸出符號.引例2

如此重復(fù)地做下去，這樣便得到一個輸出序列.我們能夠觀測到的是這個輸出序列—顏色符號序列，而狀態(tài)(籃子)之間的轉(zhuǎn)移(狀態(tài)序列)被隱藏起來了.每個狀態(tài)(籃子)輸出什么符號(顏色)是由它的輸出概率分布(籃子中彩球數(shù)目分布)來隨機決定的.選擇哪個籃子(狀態(tài))輸出顏色由狀態(tài)轉(zhuǎn)移矩陣來決定.隱馬爾可夫模型的示例—賭場欺詐問題：（本例來自戴培山等生物信息專題課件）某賭場在投骰子，根據(jù)點數(shù)決定勝負(fù)。在多次投擲骰子的時候采取了如下手段進(jìn)行作弊：準(zhǔn)備了兩個骰子A和B，其中A為正常骰子，B為灌鉛骰子，由于怕被發(fā)現(xiàn)，所有連續(xù)投擲的時候偶爾使用一下B，A和B之間轉(zhuǎn)換的概率如下：(2)隱馬爾可夫模型的參數(shù)

①狀態(tài)總數(shù)N；②每個狀態(tài)對應(yīng)的觀測事件數(shù)M；③狀態(tài)轉(zhuǎn)移矩陣:④每個狀態(tài)下取所有觀測事件的概率分布:⑤起始狀態(tài):我們將圖對應(yīng)到賭場作弊問題，以便深入理解隱馬爾可夫模型：

賭場作弊隱馬爾可夫模型中，狀態(tài)空間—觀測空間示意圖：

注：隱馬爾可夫模型中，是馬爾可夫鏈，是隱蔽層，是不可觀測的，也稱為狀態(tài)鏈。是觀測到的序列，是一個隨機序列，也稱為觀測鏈。因此，隱馬爾可夫模型是有兩個隨機過程組成：即由狀態(tài)鏈（馬爾可夫鏈）和觀測鏈組成二、隱馬爾可夫模型中的三個基本問題

（1）評估問題（evaluation）：從骰子的數(shù)列中推斷是否使用了作弊骰子，如果知道使用了作弊骰子，那么在投擲骰子的過程中出現(xiàn)這個序列的概率有多大。（2）解碼問題（decoding）：如果確實使用了作弊骰子，這些序列中哪些點是由B投擲出來的。（3）學(xué)習(xí)問題（Learning）：也稱為參數(shù)訓(xùn)練問題，即僅僅給出大量的數(shù)據(jù)點，如何從中推斷出細(xì)節(jié)問題（如骰子B投出各個點的概率？賭場是何時偷換的骰子的）。

問題一：給定模型參數(shù)和觀測序列，如何快速求出在該模型下，觀測事件序列發(fā)生的概率？問題二：給定模型參數(shù)和觀測序列，如何找出一個最佳狀態(tài)序列？問題三：如何得到模型中的五個參數(shù)？

問題一：前向和后向算法（估計問題）問題二：Viterbi算法（解碼問題）問題三：Baum-Welch算法（學(xué)習(xí)問題）如何解決三個基本問題1.評估問題（evaluation）

評估問題：是已知觀測序列和模型，如何計算給定模型的情況下，產(chǎn)生觀測序列的概率。路徑：隱馬爾可夫模型中從初始狀態(tài)到終止?fàn)顟B(tài)的一個彼此到達(dá)的狀態(tài)序列，稱為一個路徑。也就是馬爾可夫鏈。

前向算法：

后向算法：

前后向算法

2.解碼問題（decoding）

對于骰子作弊問題中，解碼問題是：如果確實使用了作弊骰子，這些序列中哪些點時由B投擲出來的。

Viterbi算法

3.學(xué)習(xí)問題（Learning）

三、HMM在CpG島識別中的應(yīng)用

1)模型的建立：共8個狀態(tài)，“+”標(biāo)記的狀態(tài)表在CpG島內(nèi)部，“-”標(biāo)記的狀態(tài)表CpG島外部。識別CpG區(qū)域：識別CpG區(qū)域相當(dāng)于尋找連續(xù)的C+和G+組合的區(qū)域，相當(dāng)于把生成原始序列隱狀態(tài)鑒別出來，隱狀態(tài)中C+和G+連續(xù)較高的區(qū)域為CpG區(qū)域，這對應(yīng)到隱馬爾可夫模型的第二個問題，譯碼問題。

應(yīng)用HMM3類基本問題中解碼問題(decoding)：給定一個隱馬爾柯夫模型M和一個字符序列X，在M中為X尋找一條最優(yōu)路徑

*，要求使得P(X|

*)最大（Vite