隱馬爾可夫模型

HiddenMarkovModel

HiddenMarkovModel

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

2021/10/104一、隱馬爾可夫模型的基本概念

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

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

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

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

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

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

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

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

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

2021/10/1025問題一：前向和后向算法（估計(jì)問題）問題二：Viterbi算法（解碼問題）問題三：Baum-Welch算法（學(xué)習(xí)問題）如何解決三個(gè)基本問題2021/10/10261.評(píng)估問題（evaluation）

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

2021/10/10272021/10/10282021/10/10292021/10/1030前向算法：

2021/10/10312021/10/10322021/10/10332021/10/10342021/10/10352021/10/10362021/10/10372021/10/10382021/10/10392021/10/10402021/10/10412021/10/10422021/10/10432021/10/10442021/10/10452021/10/10462021/10/10472021/10/10482021/10/10492021/10/10502021/10/10512021/10/10522021/10/1053后向算法：

2021/10/10542021/10/10552021/10/10562021/10/1057前后向算法

2021/10/10582.解碼問題（decoding）

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

2021/10/10592021/10/1060Viterbi算法

2021/10/10612021/10/10622021/10/10632021/10/10643.學(xué)習(xí)問題（Learning）

2021/10/10652021/10/10662021/10/10672021/10/10682021/10/10692021/10/10702021/10/10712021/10/10722021/10/10732021/10/1074三、HMM在CpG島識(shí)別中的應(yīng)用

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

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

*，要求使得P(X|

*)最大（Viterbi算法） 如果找到最優(yōu)路徑

*，則這條路徑穿過的“+”狀態(tài)將對(duì)應(yīng)于CpG島。2021/10/10802021/10/1081假定要進(jìn)行識(shí)別的序列為ATGCGAC我們搜索其所有可能路徑，選擇使得達(dá)到最大值的路徑X。我們使用Viterbi算法進(jìn)行識(shí)別，對(duì)于每一步，每一個(gè)狀態(tài)都計(jì)算如下最大值：

2021/10/10822