生物信息学实验.ppt

生物信息学实验 实验2 隐马尔科夫模型 生物学中常用的统计模型 Structured probability models Markov models Hidden markov models Artificial Neural Network (A.N.N) Introduction Introduction HMM的优点 Probability Review 独立事件概率 设想我们做一连串的实验，而每次实验所可能发生的结果定为 E1,E2,… En,…。（可能是有限也可能是无限）。每一个结果 Ek，如果给定一个出现的可能性 pk（即概率），则某一特定样本之序列 Ej1 Ej2 … Ejn出现的概率为 p(Ej1 Ej2 … Ejn) =pj1 … Pjn。 马尔科夫链 一般及常用的统计中，彼此相互「独立」大概是最有用的一个观念。用简单的术语來说，互相「独立」就是彼此毫不相干，一点牵涉都沒有。 但是实际生活中很多事件是相互关联的 [不是互相独立」也就是相互关联的意思，但是要怎样相关呢？如何在相关中作一些简单的分类呢？马尔科夫链就是要描述在「相关」这个概念中最简单的一种。但即使如此，有关马可夫链的理论已经相当丰富了。在概率理论中，它几乎占了绝大的部分。 马尔科夫链 在马尔科夫链中考虑最简单的「相关」性。在在这种情况下，我们不能给任一个事件 Ej 一個概率 pj 但我们给一对事件 (Ej,Ek) 一個概率 pjk，这个时候 pjk 的解释是一种条件概率，就是假设在某次实验中 Ej 已经出现，而在下一次实验中 Ek 出现的概率。除了 pjk 之外，还需要知道第一次实验中 Ej 出現的機率 aj。有了这些资料后，一個样本序列 Ej0 Ej1 … Ejn（也就是说第零次实验结果是Ej0，第一次一次是 Ej1……第 n 次实验是 Ejn）的概率就很清楚的是 P(Ej0,Ej1,Ejn) =aj pj0j1 pj1j2 … pjn-1jn。 隐马尔科夫模型 但是在大多数情况下我们所观察到的值并不是序列本身的元素。 即观察值不等于状态值。 故我们引入隐马尔科夫模型。 定义 一个HMM 是一个五元组： (ΩX , ΩO, A, B, π ) 其中： ΩX = {q1,...qN}：状态的有限集合 ΩO = {v1,...,vM}：观察值的有限集合 A = {aij}，aij = p(Xt+1 = qj |Xt = qi)：转移概率 B = {bik}，bik = p(Ot = vk | Xt = qi)：输出概率 π = {πi}， πi = p(X1 = qi)：初始状态分布 假设 对于一个随机事件，有一个观察值序列：O1,...,OT 该事件隐含着一个状态序列：X1,...,XT 假设1：马尔可夫假设（状态构成一阶马尔可夫链）  p(Xi|Xi-1…X1) = p(Xi|Xi-1) 假设2：不动性假设（状态与具体时间无关） p(Xi+1|Xi) = p(Xj+1|Xj)，对任意i,j成立 假设3：输出独立性假设（输出仅与当前状态有关） p(O1,...,OT | X1,...,XT) = Π p(Ot | Xt) 马尔科夫链 Vs 隐马尔科夫模型 Markov chains have entirely observable states. However a “Hidden Markov Model” is a model of a Markov Source which admits an element each time slot depending upon the state. The states are not directly observed Problems 令 λ = {A,B,π} 为给定HMM的参数， 令 σ = O1,...,OT 为观察值序列， 隐马尔可夫模型（HMM）的三个基本问题： 评估问题：对于给定模型，求某个观察值序列的概率p(σ|λ) ；forward algorithm 解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；viterbi algorithm 学习问题：对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率p(σ|λ)最大。Forward-backward algorithm Solutions Evaluation problem：forward algorithm 定义向前变量 采用动态规划算法，复杂度O(N2T) Decoding problem：Viterbi algorithm 采用动态规划算法，复杂度O(N2T