隐马尔可夫模型

隐马尔可夫模型

HiddenMarkovModel

HiddenMarkovModel

思考题：对给定的一定长度的DNA序列，识别其上CpG岛大致位的方法。两个问题：（1）给定一段DNA序列片段，判断它是否是CpG岛？对应于Markov模型问题（2）给定一段DNA序列，识别其中的CpG岛？对应于隐Markov模型问题主要内容隐马尔可夫模型的基本概念隐马尔可夫模型中的三个基本问题隐马尔可夫模型的生物信息学应用—CpG岛识别

一、隐马尔可夫模型的基本概念

隐马尔可夫模型（hiddenMarkovmodel,记作：HMM）是马尔可夫模型的进一步发展。其在生物信息学分析中得到了广泛的应用。（1）HMM的基本概念

马尔可夫模型主要是把一个总随机过程看成一系列状态的不断转移，其特性主要使用“转移概率”来表示。HMM则认为模型的状态是不可观测的（这是“隐”的由来）。能观测到的只是它表现出的一些观测值（observations）123a12a21a22a11a23a32a13a31a33例：隐马尔可夫链—观测三个硬币状态

每个硬币代表一个状态;每个状态有两个观测值:正面H和反面T;

每个状态产生H的概率：P(H);

每个状态产生T的概率为：1-P(H)对比两个模型可见：马尔可夫模型的观测序列本身就是状态序列；隐马尔可夫模型的观测序列不是状态序列；设有N个篮子，每个都装了许多彩色小球，小球颜色有M种.现在按下列步骤产生出一个输出符号(颜色)序列:按某个初始概率分布，随机的选定一个篮子，从中随机地取出一个球，记录球的颜色作为第一个输出符号，并把球放回原来的篮子.然后按照某个转移概率分布(与当前篮子相联系)选择一个新的篮子(也可能仍停留在当前篮子)，并从中随机取出一个球，记下颜色作为第二个输出符号.引例2

如此重复地做下去，这样便得到一个输出序列.我们能够观测到的是这个输出序列—颜色符号序列，而状态(篮子)之间的转移(状态序列)被隐藏起来了.每个状态(篮子)输出什么符号(颜色)是由它的输出概率分布(篮子中彩球数目分布)来随机决定的.选择哪个篮子(状态)输出颜色由状态转移矩阵来决定.隐马尔可夫模型的示例—赌场欺诈问题：（本例来自戴培山等生物信息专题课件）某赌场在投骰子，根据点数决定胜负。在多次投掷骰子的时候采取了如下手段进行作弊：准备了两个骰子A和B，其中A为正常骰子，B为灌铅骰子，由于怕被发现，所有连续投掷的时候偶尔使用一下B，A和B之间转换的概率如下：(2)隐马尔可夫模型的参数

①状态总数N；②每个状态对应的观测事件数M；③状态转移矩阵:④每个状态下取所有观测事件的概率分布:⑤起始状态:我们将图对应到赌场作弊问题，以便深入理解隐马尔可夫模型：

赌场作弊隐马尔可夫模型中，状态空间—观测空间示意图：

注：隐马尔可夫模型中，是马尔可夫链，是隐蔽层，是不可观测的，也称为状态链。是观测到的序列，是一个随机序列，也称为观测链。因此，隐马尔可夫模型是有两个随机过程组成：即由状态链（马尔可夫链）和观测链组成二、隐马尔可夫模型中的三个基本问题

（1）评估问题（evaluation）：从骰子的数列中推断是否使用了作弊骰子，如果知道使用了作弊骰子，那么在投掷骰子的过程中出现这个序列的概率有多大。（2）解码问题（decoding）：如果确实使用了作弊骰子，这些序列中哪些点是由B投掷出来的。（3）学习问题（Learning）：也称为参数训练问题，即仅仅给出大量的数据点，如何从中推断出细节问题（如骰子B投出各个点的概率？赌场是何时偷换的骰子的）。

问题一：给定模型参数和观测序列，如何快速求出在该模型下，观测事件序列发生的概率？问题二：给定模型参数和观测序列，如何找出一个最佳状态序列？问题三：如何得到模型中的五个参数？

问题一：前向和后向算法（估计问题）问题二：Viterbi算法（解码问题）问题三：Baum-Welch算法（学习问题）如何解决三个基本问题1.评估问题（evaluation）

评估问题：是已知观测序列和模型，如何计算给定模型的情况下，产生观测序列的概率。路径：隐马尔可夫模型中从初始状态到终止状态的一个彼此到达的状态序列，称为一个路径。也就是马尔可夫链。

前向算法：

后向算法：

前后向算法

2.解码问题（decoding）

对于骰子作弊问题中，解码问题是：如果确实使用了作弊骰子，这些序列中哪些点时由B投掷出来的。

Viterbi算法

3.学习问题（Learning）

三、HMM在CpG岛识别中的应用

1)模型的建立：共8个状态，“+”标记的状态表在CpG岛内部，“-”标记的状态表CpG岛外部。识别CpG区域：识别CpG区域相当于寻找连续的C+和G+组合的区域，相当于把生成原始序列隐状态鉴别出来，隐状态中C+和G+连续较高的区域为CpG区域，这对应到隐马尔可夫模型的第二个问题，译码问题。

应用HMM3类基本问题中解码问题(decoding)：给定一个隐马尔柯夫模型M和一个字符序列X，在M中为X寻找一条最优路径

*，要求使得P(X|

*)最大（Vite