生物信息学实验市公开课获奖课件省名师优质课赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,生物信息学试验,试验2 隐马尔科夫模型,上海交通大学,生命科学技术学院,生物信息学与生物统计学系,1/55,10/6/,1,生物学中惯用统计模型,Structured probability models,Markov models,Hidden markov models,Artificial Neural Network(A.N.N),2/55,10/6/,2,Introduction,Hidden Markov Models(HMMs)最早是在上个世纪60年代末70年代初提出来。,进入80年代以后，逐步被利用在各个领域。,3/55,10/6/,3,Introduction,Hidden Markov Models 作为一个强有力统计学模型，主要被应用在一些连续行或时间延续性事件建模上,语音识别系统。,生物学中DNA/protein序列分析,机器人控制。,文本文件信息提取。,4/55,10/6/,4,HMM优点,1，它数学结构非常丰富，适合用于各个领域研究。,2，在很多领域中，已经证实它结果和实际符合相当好。,5/55,10/6/,5,Probability Review,6/55,10/6/,6,独立事件概率,构想我们做一连串试验，而每次试验所可能发生结果定为,E,1,E,2,E,n,。（可能是有限也可能是无限）。每一个结果,E,k,，假如给定一个出现可能性,p,k,（即概率），则某一特定样本之序列,E,j,1,E,j,2,E,jn,出现概率为,p,(,E,j,1,E,j,2,E,jn,)=,p,j,1,P,jn,。,7/55,10/6/,7,马尔科夫链,普通及惯用统计中，彼此相互独立大约是最有用一个观念。用简单术语來说，相互独立就是彼此毫不相干，一点牵涉都沒有。,不过实际生活中很多事件是相互关联,不是相互独立也就是相互关联意思，不过要怎样相关呢？怎样在相关中作一些简单分类呢？马尔科夫链就是要描述在相关这个概念中最简单一个。但即使如此，相关马可夫链理论已经相当丰富了。在概率理论中，它几乎占了绝大部分。,8/55,10/6/,8,马尔科夫链,在马尔科夫链中考虑最简单相关性。在在这种情况下，我们不能给任一个事件,E,j,一個概率,p,j,但我们给一对事件(,E,j,E,k,)一個概率,p,jk,，这个时候,p,jk,解释是一个条件概率，就是假设在某次试验中,E,j,已经出现，而在下一次试验中,E,k,出现概率。除了,p,jk,之外，还需要知道第一次试验中,E,j,出現機率,a,j,。有了这些资料后，一個样本序列,E,j,0,E,j1,E,jn,（也就是说第零次试验结果是,E,j,0,，第一次一次是,E,j,1,第,n,次试验是,E,jn,）概率就很清楚是,P,(,E,j,0,E,j,1,E,jn,)=,a,j,p,j,0,j,1,p,j,1,j,2,p,jn,-1,jn,。,9/55,10/6/,9,隐马尔科夫模型,不过在大多数情况下我们所观察到值并不是序列本身元素。,即观察值不等于状态值。,故我们引入隐马尔科夫模型。,10/55,10/6/,10,定义,一个HMM 是一个五元组：,(,X,O,A,B,),其中：,X,=q,1,.q,N,：状态有限集合,O,=v,1,.,v,M,：观察值有限集合,A=a,ij,，a,ij,=p(X,t+1,=q,j,|X,t,=q,i,)：转移概率,B=b,ik,，b,ik,=p(O,t,=v,k,|X,t,=q,i,)：输出概率,=,i,，,i,=p(X,1,=q,i,)：初始状态分布,11/55,10/6/,11,假设,对于一个随机事件，有一个观察值序列：O,1,.,O,T,该事件隐含着一个状态序列：X,1,.,X,T,假设1：马尔可夫假设（状态组成一阶马尔可夫链）p(X,i,|X,i-1,X,1,)=p(X,i,|X,i-1,),假设2：不动性假设（状态与详细时间无关）,p(X,i+1,|X,i,)=p(X,j+1,|X,j,)，对任意i,j成立,假设3：输出独立性假设（输出仅与当前状态相关）p(O,1,.,O,T,|X,1,.,X,T,)=p(O,t,|X,t,),12/55,10/6/,12,马尔科夫链 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,13/55,10/6/,13,Problems,令,=A,B,为给定HMM参数，,令 =O,1,.,O,T,为观察值序列，,隐马尔可夫模型（HMM）三个基本问题：,评定问题：对于给定模型，求某个观察值序列概率p(|,)；forward algorithm,解码问题：对于给定模型和观察值序列，求可能性最大状态序列；viterbi algorithm,学习问题：对于给定一个观察值序列，调整参数,，使得观察值出现概率p(|,)最大。Forward-backward algorithm,14/55,10/6/,14,Solutions,Evaluation problem：forward algorithm,定义向前变量,采取动态规划算法，复杂度O(N,2,T),Decoding problem：Viterbi algorithm,采取动态规划算法，复杂度O(N,2,T),Learning problem：forward-backward algorithm,EM算法一个特例，带隐变量最大似然预计,15/55,10/6/,15,Struct HMM,typedef struct,/*number of states;Q=1,2,.,N*/int N;,/*number of observation symbols;V=1,2,.,M*/,int M;,/*A1.N1.N.aij is the transition prob of going from state i,*at time t to state j at time t+1*/double*A;,/*B1.N1.M.bjk is the probability of observing symbol k in state j*/double*B;,/*pi1.N pii is the initial state distribution.*/,double*pi;HMM;,16/55,10/6/,16,算法：向前算法（1）,17/55,10/6/,17,算法：向前算法（2）,定义前向变量为HMM在时间t输出序列O,1,O,t,，而且位于状态S,i,概率：,18/55,10/6/,18,算法：向前算法（3）,迭代公式为：,结果为：,19/55,10/6/,19,Forward algorithm,20/55,10/6/,20,算法：向后算法（1）,21/55,10/6/,21,算法：Viterbi算法（1）,The Viterbi algorithm is a dynamic programming algorithm that computes the most likely state transition path given an observed sequence of symbols.It is actually very similar to the forward algorithm。,22/55,10/6/,22,Viterbi algorithm,23/55,10/6/,23,Viterbi in c,/*1.Initialization*/for(i=1;i N;i+)delta1i=phmm-pii*(phmm-BiO1);psi1i=0;/*2.Recursion*/for(t=2;t N;j+)maxval=0.0;maxvalind=1;for(i=1;i N;i+)val=deltat-1i*(phmm-Aij);if(val maxval)maxval=val;maxvalind=i;deltatj=maxval*(phmm-BjOt);psitj=maxvalind;,24/55,10/6/,24,生物学中数学模型,25/55,10/6/,25,马氏链,26/55,10/6/,26,马氏链,27/55,10/6/,27,马氏链,28/55,10/6/,28,隐马可夫模型,29/55,10/6/,29,隐马可夫模型,30/55,10/6/,30,隐马可夫模型 profile,31/55,10/6/,31,Related software,HMMER,hmmer.wustl.edu/,SAM(Sequence Alignment and Modeling System),www.soe.ucsc.edu/,HMMpro,A windows version for HMM,The Division of Biomedical Informatics at Cincinnati Childrens Hospital Medical Center,metaMEME:A motif based Hidden Markov Model,32/55,10/6/,32,HMMER,Profile hidden Markov models(profile HMMs)can be used to do sensitive database searching using statistical descriptions of a sequence familys consensus.HMMER is a freely distributable implementation of profile HMM software for protein sequence analysis.The current version is HMMER 2.3.2(3 Oct),containing minor bugfixes and updates for the May release of HMMER 2.3.,33/55,10/6/,33,HMMER,34/55,10/6/,34,How to create a HMM,多序列比对,相关序列选取,模型构建,模型训练,参数调整,应用,确立模型,35/55,10/6/,35,Example:1.Sequence selection,选取相关序列,36/55,10/6/,36,2.Alignment,Save result as msf format,多序列比对,37/55,10/6/,37,模型建立,3.Hmmbuild,4.Hmmt,5.Hmmcalibrate,模型建立,用相关序列对模型进行训练,参数调整,38/55,10/6/,38,模型文件（1）,HMMER2.0 2.3.2,NAME globins50,LENG 162,ALPH Amino,RF no,CS no,MAP yes,COM ./hmmbuild globins.hmm globins50.msf,NSEQ 50,DATE Thu Sep 18 00:02:14,CKSUM 4694,XT -8455 -4 -1000 -1000 -8455 -4 -8455 -4,NULT -4 -8455,NULE 595 -1558 85 338 -294 453 -1158 197 249 902 -1085 -142 -21 -313 45 531 201 384 -1998 -644,39/55,10/6/,39,模型文件（2）,模型部分：,HMM A C D E F G H I K L M N P Q R S T V W Y,m-m m-i m-d i-m i-i d-m d-d b-m m-e,-222 *-2807,1 -1412 -1712 -339 -321 -1729 113 -1457 261 -1493 -1591 1181 -1737 -32 -1359 -1788 77 -1353 2620 -2119 -1697 4,-149 -500 233 43 -381 399 106 -626 210 -466 -720 275 394 45 96 359 117 -369 -294 -249,-1909 8804 -451 -894 -1115 -701 -1378 -110 *,2 -1118 -1371 -1805 -1237 -1464 -2231 -889 2528 2067 -899 -510 -1267 -2325 -644 -266 -1422 -1057 -63 -1884 -1486 5,-149 -500 233 43 -381 399 106 -626 210 -466 -720 275 394 45 96 359 117 -369 -294 -249,-18 -6914 -7956 -894 -1115 -3550 -129 *,40/55,10/6/,40,6.未知序列搜索查询,Hmmsearch:search a sequence against the profile HMM,未知查询序列Artemia.fa,Profile HMM：Globin.hmm,Command:hmmsearch globin.hmm Artemia.fa,查询程序,查询未知序列文件,所用模型,查询命令,41/55,10/6/,41,查询结果,结果分为2个部分,1：说明部分（数听说明、选项、模型说明）,2:结果序列部分,42/55,10/6/,42,Result1,第一部分：相关信息说明,软件信息：版本、权限等,HMM文件名称，查询阈值等,HMM文件一些描述信息,43/5510/6/,43,Result 2.1,HIT序列分值，E值，domain数目,HIT domains分值、位置、E值等信息,44/55,10/6/,44,Result 2.2,高分匹配序列比对,45/55,10/6/,45,Result 2.3,全部序列HIT分值、E值图形分布,46/55,10/6/,46,Result 2.4,结果统计数据,47/55,10/6/,47,Application of HMM:pfam,48/55,10/6/,48,Application of HMM,TMHMM:Prediction of transmembrane helices in proteins,www.cbs.dtu.dk/services/TMHMM/,49/55,10/6/,49,PFAM,Pfam is a large collection of protein multiple sequence alignments,and profile hidden Markov models.Pfam is available on the World,Wide Web in the UK at,www.sanger.ac.uk/Software/Pfam/,in Sweden at,www.cgb.ki.se/Pfam/,in France at,pfam.jouy.inra.fr/,and in the US at,pfam.wustl.edu/,.,50/55,10/6/,50,Pfam Introduction,Pfam is a database of protein domain families.Pfam contains,curated multiple sequence alignments for each family,as well,as profile hidden Markov models(profile HMMs)for finding these,domains in new sequences.,Pfam contains functional annotation,literature references and database links for each family.,51/55,10/6/,51,Pfam Introduction,Version 14.0,June,7459 families22336 unique Pfam-A domain architectures,Two big families,Pfam-A:A high-quality manual part of Pfam.,Pfam-B:Low-quality automatically generated alignments of sequence clusters in SWISSPROT and TrEMBL that are not modelled in the curated part of Pfam.,52/55,10/6/,52,Pfam Introduction,There,are two multiple alignments for each Pfam family,the seed alignment,that contains a relatively small number of representative members,of the family and the full alignment that contains all members,in the database that can be detected.All alignments use sequences,taken from pfamseq,which is a non-redundant protein set composed,of SWISS-PROT and SP-TrEMBL.The profile HMM is built from the,seed alignment using the HMMER package,which is then used to search the pfamseq sequence database,53/55,10/6/,53,Pfam Goals,One of the main goals of Pfam was to aid the annotation of,the,Caenorhabditis elegans,genome.Traditional approaches,to large scale sequence annotation use a pairwise sequence comparison,method such as BLAST to find similarity to proteins of known,function.Annotations are then transferred from the protein,of known function to the predicted protein.The pairwise similarity,search does not give a clear indication of the domain structure,of the proteins.Mistakes in annotation can result from not,considering the domain organisation of proteins.For example,a protein may be misannotated as an enzyme when the similarity,is only to a regulatory domain.Since its inception,Pfam has,been developed to provide broad support for automated protein,sequence classification and annotation.During the last year,there have been significant changes and extensions to Pfam,which further this role.,54/55,10/6/,54,蛋白二级结构分析,The PredictProtein server,blast.ym.edu.tw/tools/predictprotein/predictprotein.html,55/55,10/6/,55,