《生物信息学课件 3.5.4hmm应用实例》由会员分享，可在线阅读，更多相关《生物信息学课件 3.5.4hmm应用实例（48页珍藏版）》请在金锄头文库上搜索。
1、 3.5.4 隐马尔可夫模型方 法在基因识别中的应用1.马尔可夫模型马尔可夫是俄国的数学家(1856-1922)。马尔可夫模型是一个概率统计模型。（1）Markov模型的基本概念（2）Markov 模型的组成 （3）Markov链（1） Markov模型的基本概念马尔可夫过程:一个过程的“将来”仅依赖“现在” 而不依赖“过去”，此过程具有马尔可夫性,或称 此过程为马尔可夫过程。数学表示式：马尔科夫链:时间和状态都离散的马尔科夫过程 。马尔科夫链的状态空间记做：马尔科夫链（马氏链）在时刻m处于状态Si条 件下，在时刻m +n转移到状态Sj的转移概率是条件概率：由于马氏链在时刻m从任何一个状态Si
2、 出发， 到另一时刻m +n，必然转移到Sj，j=1,2,，诸状态中的某一个，所以有：当pij (m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐 次马尔科夫链。 （2）Markov 模型的组成 随机序列变量：状态空间：为方便起见，可用状态下标代表相应的状态 。转移概率矩阵：初始状态向量：(3)Markov链s1s2s311/21/21/3 2/3下雨多云晴天0.30.20.60.40.20.10.3 0.10.8下雨-状态1多云-状态2晴天-状态3例：马尔可夫链观测天气变化晴天晴天晴天下雨下雨tt+1晴天-晴天-晴天-下雨-下雨-晴天-多云-晴天晴天多云晴天t
3、-1马尔可夫链2.马尔可夫链在识别CpG岛中的应用(1) CpG岛(CpG island)定义：一类长度在几百bp的特殊DNA序列，其中CG核苷酸对出现的频率非常高。例：ACGCGCGTACGCGAAT(2)识别问题的表述： 给定一段DNA序列 S =(s1，s2， ,sL)，确定S 是否是一个CpG岛。 (3)识别问题的数学基础 根据马尔可夫链概念，可知整个序列S的发生概率为 ：现添加两个特殊的字符B(begin)和E(end)，使得 x0=B, xL+1=E，则上述公式简化为：(4)如何识别CpG岛令fst+为CpG 岛内的字符转换概率fst-为CpG 岛外的字符转换概率S的对数似然得分为
4、上述计算值越大，则S越可能是CpG岛。(5)实例利用一组人类DNA序列建立两个马尔可夫 链模型，一个是从中提取的共48个已确定 的CpG岛(+),另外一个是剩余的序列(-)。每组中的转换概率公式:最终得到CpG岛内部和外部的转换概率 对于给定的序列S，计算score(S)(6)进一步待解决的问题:给定DNA序列，确定CpG岛的位置。一种直接的方法：对窗口内的子序列计算得分Score(Sk)，具有正值的Sk 就是可能的CpG岛。存在的问题：事先不知道CpG岛的长度，只是假设长 度为 ，如果 比较大，而真实的CpG岛 又比较小，则上述概率计算值不足以证 实CpG岛；如果 取值比较小，则难以找 出整
5、个CpG岛。这是该算法的最大不足 之处，需要考虑其他的算法。 HMM3.隐马尔可夫模型隐马尔可夫模型（hidden Markov model , 记作：HMM）是马尔可夫模型的进一步发展。其在生物信息 学分析中得到了广泛的应用。（1）HMM的基本概念马尔可夫模型的主要是把一个总随 机过程看成一系列状态的不断转移，其 特性主要使用“转移概率”来表示。HMM则认为模型的状态是不可观测 的（这是“隐”的由来）。能观测到的只 是它表现出的一些观测值（observations ）123a12a21a22a11a23a32a13 a31a33例：隐马尔可夫链观测三个硬币状态v 每个硬币代表一个状态;v每个
6、状态有两个观测值: 正面 H 和反面 T;v 每个状态产生H的概率：P(H);v 每个状态产生T的概率为：1-P(H) 对比两个模型可见：v 马尔可夫模型的观测序列本身就是 状态序列；v 隐马尔可夫模型的观测序列不是状 态序列；(2)隐马尔可夫模型的参数状态总数 N ；每个状态对应的观测事件数 M ；状态转移矩阵 :每个状态下取所有观测事件的概率分布 :起始状态 :问题一：给定模型参数 和观测序 列 ，如何快速求出在该模型下，观测 事件序列发生的概率 ？ 问题二：给定模型参数和观测序列，如何找出一个 最佳状态序列？问题三：如何得到模型中的五个参数？ 4.隐马尔可夫模型的三个基本问题问题一：前向
7、和后向算法（估计问题）问题二： Viterbi算法 （解码问题）问题三： Baum-Welch算法（学习问题）如何解决三个基本问题l问题三的特殊情况：假设已知与字符串序列相对 应的状态序列，可以计算从状态i到状态j的转换 数Aij和在状态j下释放字符k的次数Bj(k)。则：l为了避免零概率，当处理数量较少的样本时，需 要对Aij和Bj(k)进行修正：5.隐马尔可夫模型在基因识别中的应用（1）HMM在CpG岛识别中的应用1)模型的建立：共8个状态，“+”标记的状态表在 CpG岛内部，“-”标记的状态表CpG岛外部。2)模型的训练用Baum-Welch方法(或EM)对于给定的序列X ,调整模型的参
8、数，使得概率P(X|M)最大(即三个基本问题中的学 习问题，learning ）(实际操作时可使用刚才讲的特殊情况下)假设字符处于CpG岛内的概率是p处于CpG岛外的概率是q可以得到状态转换概率（如下图）CpG岛HMM模型中的状态转换概率 3)应用HMM3类基本问题中解码问题(decoding )：给定一个隐马尔柯夫模型M 和一个字符序列X， 在M中为X寻找一条最优路径*，要求使得 P(X|*)最大（Viterbi算法）4)如果找到最优路径*，则这条路径穿过的“+” 状态将对应于CpG岛。（2）HMM在编码序列识别中的应用问题的引入exon-intron-exon-intron-intron-
9、exon HMM具有模拟语法的能力，可用于识别基因结构序列不同的功能区域对应不同的模型Combined model Schematic* 信号传感器模型用途:对信号位点建立小的HMM，如剪切位点、起始密码子区域和终止密码子区域。实例：建立剪切接受体位点的HMMA.问题描述：如下图根据对 比排列 ，形成 具有19 状态的 HMM 模型内含子区域外显子区域 保守位点 B.计算状态的条件概率：将4种概率分布扩展为16种，来处理双联核苷酸的问题。 第一状态 第二状态p1(A) p2(A|A) p2(C|A) p2(G|A) p2(T|A) C.计算序列的概率 例：一段序列为ACTGTC，则 P(ACT
10、GTC)=p1(A)p2(CA)p3(TC)p4(GT)p5(TG)p6(CT)补充：供体位点HMM* 编码区模型模型的最后一个状态应该至少为2阶。对于2阶的状态，具有64种概率分布。例如：p(ACA)=c(CAA)/c(CAA)+c(CAC)+c(CAG)+c(CAT)p(CCA)=c(CAC)/c(CAA)+c(CAC)+c(CAG)+c(CAT) p(GCA)=c(CAG)/c(CAA)+c(CAC)+c(CAG)+c(CAT)p(TCA)=c(CAT)/c(CAA)+c(CAC)+c(CAG)+c(CAT) 其中，c(xyz)是密码子xyz的计数。特征之一是不存在终止密码子。因为对应于
11、终止 密码子TAA、TAG和TGA的p(ATA)、p(GTA) 和p(ATG)自动为0。* 组合模型 单外显子基因组合模型说明：x表示未编码的DNA, c表示编码的DNA整个模型由几个小的独立的HMM构成的大的HMM多个外显子基因组合模型(3)基于HMM的基因识别系统常用的系统Veil (http:/www.cs.jhu.edu/labs/compbio/veil.html)Genie (http:/www-hgc.lbl.gov/inf/genie.html)Genemark (http:/genemark.biology.gatech.edu/GeneMark/)HMMgene (http
12、:/www.cbs.dtu.dk/services/HMMgene)GENSCAN (http:/genomic.stanford.edu/GENSCANW.html)GENSCAN（采用GHMM-扩展的隐马尔柯夫模型 ） (generalized hidden markov model)作业题：1.隐马尔可夫模型的参数主要包括那些？ 2.利用HMM如何识别CpG岛？ 3.简述HMM用于基因识别的组合模型中的 单外显子模型及如何利用它识别基因。思考题：1.隐马尔可夫模型的三个基本问题是什么？ 2.解决隐马尔可夫模型的三个基本问题常用 的方法是什么？ 3.举例说明马尔可夫模型与隐马尔可夫模型 的区别与联系。
