隐马尔可夫模型

隐马尔可夫模型HiddenMarkovModelHiddenMarkovModel思考题：对给定的一定长度的DNA序列，识别其上CpG岛大致位的方法。两个问题：（1）给定一段DNA序列片段，判断它是否是CpG岛？对应于Markov模型问题（2）给定一段DNA序列，识别其中的CpG岛？对应于隐Markov模型问题主要内容隐马尔可夫模型的基本概念隐马尔可夫模型中的三个基本问题隐马尔可夫模型的生物信息学应用—CpG岛识别一、隐马尔可夫模型的基本概念隐马尔可夫模型（hiddenMarkovmodel,记作：HMM）是马尔可夫模型的进一步发展。其在生物信息学分析中得到了广泛的应用。（1）HMM的基本概念马尔可夫模型主要是把一个总随机过程看成一系列状态的不断转移，其特性主要使用“转移概率”来表示。HMM则认为模型的状态是不可观测的（这是“隐”的由来）。能观测到的只是它表现出的一些观测值（observations）123a12a21a22a11a23a32a13a31a33)...()...(21THHHTHHToooOT例：隐马尔可夫链—观测三个硬币状态每个硬币代表一个状态;每个状态有两个观测值:正面H和反面T;每个状态产生H的概率：P(H);每个状态产生T的概率为：1-P(H))...()...(21THHHTHHToooOT对比两个模型可见：马尔可夫模型的观测序列本身就是状态序列；隐马尔可夫模型的观测序列不是状态序列；设有N个篮子，每个都装了许多彩色小球，小球颜色有M种.现在按下列步骤产生出一个输出符号(颜色)序列:按某个初始概率分布，随机的选定一个篮子，从中随机地取出一个球，记录球的颜色作为第一个输出符号，并把球放回原来的篮子.然后按照某个转移概率分布(与当前篮子相联系)选择一个新的篮子(也可能仍停留在当前篮子)，并从中随机取出一个球，记下颜色作为第二个输出符号.引例2如此重复地做下去，这样便得到一个输出序列.我们能够观测到的是这个输出序列—颜色符号序列，而状态(篮子)之间的转移(状态序列)被隐藏起来了.每个状态(篮子)输出什么符号(颜色)是由它的输出概率分布(篮子中彩球数目分布)来随机决定的.选择哪个篮子(状态)输出颜色由状态转移矩阵来决定.隐马尔可夫模型的示例—赌场欺诈问题：（本例来自戴培山等生物信息专题课件）某赌场在投骰子，根据点数决定胜负。在多次投掷骰子的时候采取了如下手段进行作弊：准备了两个骰子A和B，其中A为正常骰子，B为灌铅骰子，由于怕被发现，所有连续投掷的时候偶尔使用一下B，A和B之间转换的概率如下：A和B之间相互转换的概率写成矩阵如下：正常骰子A灌铅骰子B正常骰子A0.90.1灌铅骰子B0.80.2A和B产生各观测值概率的区别为：观测值123456正常骰子A1/61/61/61/61/61/6灌铅骰子B01/81/83/163/163/8骰子作弊问题模型化：作弊问题由5个部分构成：（1）隐状态空间S(状态空间)：}BA{，灌铅骰子正常骰子S，赌场具体使用哪个骰子，赌徒是不知道的。（2）观测空间O：}6,5,4,3,2,1{O。正常骰子A和灌铅骰子B的所有六个面可能取值。（3）初始状态概率空间：},{率初始选择灌铅骰子的概率初始选择正常骰子的概。（4）隐状态转移概率矩阵22P：正常骰子A灌铅骰子B正常骰子A0.90.1灌铅骰子B0.80.2（5）观测值生成概率矩阵62Q:观测值123456正常骰子A1/61/61/61/61/61/6灌铅骰子B01/81/83/163/163/8隐马尔可夫模型的定义：隐马尔科夫模型由以下五部分构成:（1）隐状态空间S(状态空间)：},,,,{321NSSSSS，其中N为状态的数目。（2）观测空间O：},,,,{321MOOOOO，M为状态对应的观测值的数目。（3）初始状态概率空间：},,,,{321N，其中}{1iiSXP（Ni1）（4）隐状态转移概率矩阵NNP：NNNNNNNNpppppppppP212222111211（5）观测值生成概率矩阵MNQ:NMNNMMMNqqqqqqqqqQ212222111211记HMM为：),,,,(QPOS或简写为),,(QP。(2)隐马尔可夫模型的参数①状态总数N；②每个状态对应的观测事件数M；③状态转移矩阵:④每个状态下取所有观测事件的概率分布:⑤起始状态:}{ijaA)}({kbBji马尔可夫模型的图解：假定观测序列为},,,,,{321ivvvvv（可见）。假定隐马尔可夫链为，},,,,,{321iXXXXX（不可见）。马尔可夫链示意图如下：我们将图对应到赌场作弊问题，以便深入理解隐马尔可夫模型：赌场作弊隐马尔可夫模型中，状态空间—观测空间示意图：注：隐马尔可夫模型中，是马尔可夫链，是隐蔽层，是不可观测的，也称为状态链。是观测到的序列，是一个随机序列，也称为观测链。因此，隐马尔可夫模型是有两个随机过程组成：即由状态链（马尔可夫链）和观测链组成},,,,,{321iXXXXX},,,,,{321ivvvvv二、隐马尔可夫模型中的三个基本问题（1）评估问题（evaluation）：从骰子的数列中推断是否使用了作弊骰子，如果知道使用了作弊骰子，那么在投掷骰子的过程中出现这个序列的概率有多大。（2）解码问题（decoding）：如果确实使用了作弊骰子，这些序列中哪些点是由B投掷出来的。（3）学习问题（Learning）：也称为参数训练问题，即仅仅给出大量的数据点，如何从中推断出细节问题（如骰子B投出各个点的概率？赌场是何时偷换的骰子的）。问题一：给定模型参数和观测序列，如何快速求出在该模型下，观测事件序列发生的概率？问题二：给定模型参数和观测序列，如何找出一个最佳状态序列？问题三：如何得到模型中的五个参数？),,,,(BAMN)...(21ToooO)|(OP问题一：前向和后向算法（估计问题）问题二：Viterbi算法（解码问题）问题三：Baum-Welch算法（学习问题）如何解决三个基本问题1.评估问题（evaluation）评估问题：是已知观测序列和模型，如何计算给定模型的情况下，产生观测序列的概率。路径：隐马尔可夫模型中从初始状态到终止状态的一个彼此到达的状态序列，称为一个路径。也就是马尔可夫链。},,,,,{321ivvvvv),,(QPv)|(vP)|(vP假定序列v有n个观测点},,,,,,{321nivvvvvv，对应状态路径},,,,,,{321niXXXXXX。尽管观测序列},,,,,,{321nivvvvvv已经给定，但生成序列v的状态序列},,,,,,{321niXXXXXX却并不唯一，因为任取一个状态iX都能以一定的概率生成iv。对于某一个观测值，都有N中状态可以产生该观测值，一共n个观测值，因此，产生观测序列的路径共有nN种。对于任意一条路径},,,,,,{321niXXXXXX，生成观测序列},,,,,,{321nivvvvvv的概率为:nnnnvXXXvXXXvXXqpqpq12221111由于产生观测序列的路径共有nN种，因此，观测序列产生的概率为nN个路径各自产生观测序列的和，即nnnnnXXvXXXvXXXvXXqpqpqvP,112221111)|(但是，值得注意的是，这样的计算需要计算2n-1次乘法，nN次加法，总计算量为nNn)12(次，是很难实现的。在实际计算中，可以采用前向算法或后向算法来降低计算量。前向算法：定义前向变量：SSntSXvvPiiittt,1),|,,()(1；表示HMM到t时刻为止，生成部分给定的观测序列为tvv,1，并且t时刻处于状态iS的概率。算法流程：（1）初始化：当t=1时，对某个Ni1，此时前向变量)(1i表示初始时刻，生成一个观测变量1v，状态处于iS的概率，即:1)(1vSSiiqi其中iS表示状态iS的初始概率，1vSiq表示状态iS生成观测值1v的生成概率。（2）递推：当11nt，对某个Ni1，前向变量)(1it表示到t+1时刻为止，生成部分给定的观测序列为11,,ttvvv，并且t+1时刻处于状态iS的概率。根据全概率公式，其等于所有可能的)(jt的基础上进行一步转移，转移到状态iS，并生成观测值1tv，其中Nj1，即:111)()(tiijvSSSNjttqpji（3）结束：当1nt，对某个Ni1，前向变量)(in表示到n时刻为止，生成全部给定的观测序列为nvv,1，并且n时刻处于状态iS的概率。即:niijvSSSNjnnqpji11)()(因此:NjnjvP1)()|(这样，迭代计算可以提高运算速度后向算法：定义后向变量：SSntSXvvPiiitntt,11),|,,()(1表示HMM在t时刻处于状态iS下，从t+1时刻到n时刻，生成部分给定的观测序列为ntvv,1的概率。算法流程：（1）初始化：当t=n时，对某个Ni1，此时后向变量)(in表示时刻n处于状态iS，由于到此为止全部观测序列已经生成完成，不管处于何种状态下一时刻即是结束。因此：1)(in（2）递推：当11nt，对某个Ni1，后向变量)(it表示在t时刻处于状态iS情况下，从t+1时刻开始生成部分给定的观测序列为ntvv,1的概率。根据全概率公式，其等于t时刻处于状态iS进行一步转移，转移到从t+1时刻处于状态jS，然后生成观测值1tv，并从t+2时刻开始生成部分给定的观测序列为ntvv,2，其中Nj1。即:NjtvSSStjqpitjji11)()(1（3）结束：当1t时，对某个Ni1，后向变量)(1i表示在1t处于状态i，从第2t开始生成部分给定的观测序列为nvv,2的概率。即:NjvSSSjqpitjji121)()(1因此:NjvSjjqvPj11)()|(1这样，迭代计算可以提高运算速度前后向算法如果将前向算法和后向算法相结合，便得到前—后向算法，也就是在整个观测序列nvv,1上，tvv,1用前向算法，ntvv,1用后向递推。根据前后向算法的，我们可以看出对于时刻t来说：NittiivP1)()()|(前后向算法可以将计算量降低到nN2次。2.解码问题（decoding）对于骰子作弊问题中，解码问题是：如果确实使用了作弊骰子，这些序列中哪些点时由B投掷出来的。对于一般的隐马尔可夫模型中，解码问题是给定模型),,(QP和一个观测序列},,,,,,{321nivvvvvv，求出模型),,(QP生成},,,,,,{321nivvvvvv的最有可能状态},,,,,,{321niXXXXXX。即推测出隐藏层的状态，也就是解码。数学描述：已知),,(QP，在所能生成的观测序列v的路径},,,,,,{321niXXXXXX中，求使得nnnnvXXXvXXXvXXqpqpqXvP12221111)|,(取得最大值的路径X。Viterbi算法思想：与前面介绍的前向、后向算法类似，定义一个路径最优变量，然后采取递推的方式迭代，进而降低计算量。路径最优变量：)|,,,,,,(max)(21121121tittXXXtvvvSXXXXPit表示在时刻t沿着一条路径ttXXXX,,,121，且在t时刻的状态为itSX产生出观测序列tvvv,,21的最大概率。另外，为了寻找路径，我们定义一个)(it专门记录t时刻状态iS最有可能由哪个状态转移而来。算法步骤：（1）初始化，当t=1时，对某个N