隐马尔可夫模型.pptVIP

 隐马尔可夫模型Hidden Markov Model Hidden Markov Model  思考题： 对给定的一定长度的DNA序列，识别其上CpG岛大致位的 方法。 两个问题： （1）给定一段DNA序列片段，判断它是否是 CpG岛？对应于Markov模型问题 （2）给定一段DNA序列，识别其中的CpG岛？ 对应于隐Markov模型问题 主要内容 隐马尔可夫模型的基本概念 隐马尔可夫模型中的三个基本问题 隐马尔可夫模型的生物信息学应用—CpG岛识别 一、隐马尔可夫模型的基本概念 隐马尔可夫模型（hidden Markov model , 记作：HMM）是马尔可夫模型的进一步发展。其在生物信息学分析中得到了广泛的应用。 例：隐马尔可夫链—观测三个硬币状态 如此重复地做下去，这样便得到一个输出序列.我们能够观测到的是这个输出序列—颜色符号序列，而状态(篮子)之间的转移(状态序列)被隐藏起来了.每个状态(篮子)输出什么符号(颜色)是由它的输出概率分布(篮子中彩球数目分布)来随机决定的.选择哪个篮子(状态)输出颜色由状态转移矩阵来决定. 隐马尔可夫模型的示例—赌场欺诈问题：（本例来自戴培山等生物信息 专题课件） 某赌场在投骰子，根据点数决定胜负。在多次投 掷骰子的时候采取了如下手段进行作弊：准备了 两个骰子A和B，其中A为正常骰子，B为灌铅骰 子，由于怕被发现，所有连续投掷的时候偶尔使 用一下B，A和B之间转换的概率如下： 我们将图对应到赌场作弊问题，以便深入理解隐马尔可夫 模型： 赌场作弊隐马尔可夫模型中，状态空间—观测空间示意图： 注： 隐马尔可夫模型中， 是马尔可夫链，是隐蔽层，是不可观测 的，也称为状态链。 是观测到的序列，是一个随机序列，也 称为观测链。 因此，隐马尔可夫模型是有两个随机过程组成：即由状态 链（马尔可夫链）和观测链组成 二、隐马尔可夫模型中的三个基本问题 （1）评估问题（evaluation）：从骰子的数列中推断是 否使用了作弊骰子，如果知道使用了作弊骰子，那么在投 掷骰子的过程中出现这个序列的概率有多大。 （2）解码问题（decoding）：如果确实使用了作弊骰 子，这些序列中哪些点是由B投掷出来的。 （3）学习问题（Learning）：也称为参数训练问题，即 仅仅给出大量的数据点，如何从中推断出细节问题（如骰 子B投出各个点的概率？赌场是何时偷换的骰子的）。 如何解决三个基本问题 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|?*)最大（Viterbi算 法） 如果找到最优路径?*，则这条路径穿过的“+” 状态将对 应于CpG岛。 假定要进行识别的序列为 ATGCGAC 我们有哪些信誉好的足球投注网站其所有可能路径，选择使得达到最大值的路径X。 我们使用Viterbi算法进行识别， 对于每一步，每一个状态都计算如下最大值： * （1）HMM的基本概念 马尔可夫模型主要是把一个总随机过程看成一系列状态的不断转移，其特性主要使用“转移概率”来表示。 HMM则认为模型的状态是不可观测的（这是“隐”的由来）。能观测到的只是它表现出的一些观测值（observations） 1 2 3 a12 a21 a22 a11 a23