生物信息学实验市公开课一等奖百校联赛特等奖课件.pptx

生物信息学试验生物信息学试验试验2 隐马尔科夫模型上海交通大学生命科学技术学院生物信息学与生物统计学系10/10/1第1页生物学中惯用统计模型生物学中惯用统计模型l Structured probability modelsMarkov modelsHidden markov modelslArtificial Neural Network(A.N.N)10/10/2第2页IntroductionHidden Markov Models(HMMs)最早是在上个世纪60年代末70年代初提出来。进入80年代以后，逐步被利用在各个领域。10/10/3第3页IntroductionHidden Markov Models 作为一个强有力统计学模型，主要被应用在一些连续行或时间延续性事件建模上语音识别系统。生物学中DNA/protein序列分析机器人控制。文本文件信息提取。10/10/4第4页HMM优点优点1，它数学结构非常丰富，适合用于各个领域研究。2，在很多领域中，已经证实它结果和实际符合相当好。10/10/5第5页Probability Review10/10/6第6页独立事件概率独立事件概率l构想我们做一连串试验，而每次试验所可能发生结果定为 E1,E2,En,。（可能是有限也可能是无限）。每一个结果 Ek，假如给定一个出现可能性 pk（即概率），则某一特定样本之序列 Ej1 Ej2 Ejn出现概率为 p(Ej1 Ej2 Ejn)=pj1 Pjn。10/10/7第7页马尔科夫链马尔科夫链l普通及惯用统计中，彼此相互独立大约是最有用一个观念。用简单术语來说，相互独立就是彼此毫不相干，一点牵涉都沒有。l不过实际生活中很多事件是相互关联l不是相互独立也就是相互关联意思，不过要怎样相关呢？怎样在相关中作一些简单分类呢？马尔科夫链就是要描述在相关这个概念中最简单一个。但即使如此，相关马可夫链理论已经相当丰富了。在概率理论中，它几乎占了绝大部分。10/10/8第8页马尔科夫链马尔科夫链l在马尔科夫链中考虑最简单相关性。在在这种情况下，我们不能给任一个事件 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。10/10/9第9页隐马尔科夫模型隐马尔科夫模型l不过在大多数情况下我们所观察到值并不是序列本身元素。l即观察值不等于状态值。l故我们引入隐马尔科夫模型。10/10/10第10页定义定义一个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)：初始状态分布10/10/11第11页假设假设对于一个随机事件，有一个观察值序列：O1,.,OT该事件隐含着一个状态序列：X1,.,XT假设1：马尔可夫假设（状态组成一阶马尔可夫链）p(Xi|Xi-1X1)=p(Xi|Xi-1)假设2：不动性假设（状态与详细时间无关）p(Xi+1|Xi)=p(Xj+1|Xj)，对任意i,j成立假设3：输出独立性假设（输出仅与当前状态相关）p(O1,.,OT|X1,.,XT)=p(Ot|Xt)10/10/12第12页马尔科夫链马尔科夫链 Vs 隐马尔科夫模型隐马尔科夫模型 lMarkov 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 10/10/13第13页Problems令 =A,B,为给定HMM参数，令 =O1,.,OT 为观察值序列，隐马尔可夫模型（HMM）三个基本问题：1.评定问题：对于给定模型，求某个观察值序列概率p(|)；forward algorithm2.解码问题：对于给定模型和观察值序列，求可能性最大状态序列；viterbi algorithm3.学习问题：对于给定一个观察值序列，调整参数，使得观察值出现概率p(|)最大。Forward-backward algorithm10/10/14第14页SolutionslEvaluation problem：forward algorithm定义向前变量采取动态规划算法，复杂度O(N2T)lDecoding problem：Viterbi algorithm采取动态规划算法，复杂度O(N2T)lLearning problem：forward-backward algorithmEM算法一个特例，带隐变量最大似然预计10/10/15第15页Struct HMMtypedef 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;10/10/16第16页算法：向前算法（算法：向前算法（1）10/10/17第17页算法：向前算法（算法：向前算法（2）定义前向变量为HMM在时间t输出序列O1Ot，而且位于状态Si概率：10/10/18第18页算法：向前算法（算法：向前算法（3）迭代公式为：结果为：10/10/19第19页Forward algorithm10/10/20第20页算法：向后算法（算法：向后算法（1）10/10/21第21页算法：算法：Viterbi算法（算法（1）lThe 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。10/10/22第22页Viterbi algorithm10/10/23第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=T;t+)for(j=1;j 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;10/10/24第24页生物学中数学模型生物学中数学模型10/10/25第25页马氏链马氏链10/10/26第26页马氏链马氏链10/10/27第27页马氏链马氏链10/10/28第28页隐马可夫模型隐马可夫模型10/10/29第29页隐马可夫模型隐马可夫模型10/10/30第30页隐马可夫模型隐马可夫模型 profile10/10/31第31页Related softwarelHMMERhttp:/hmmer.wustl.edu/lSAM(Sequence Alignment and Modeling System)http:/www.soe.ucsc.edu/lHMMproA windows version for HMM The Division of Biomedical Informatics at Cincinnati Childrens Hospital Medical Center lmetaMEME:A motif based Hidden Markov Model10/10/32第32页HMMERlProfile 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.10/10/33第33页HMMER10/10/34第34页How to create a HMM多序列比对多序列比对相关序列选取相关序列选取模型构建模型构建模型训练模型训练参数调整参数调整应用应用确立模型确立模型10/10/35第35页Example:1.Sequence selection选取相关序列选取相关序列10/10/36第36页2.AlignmentSave result as msf format多序列比对多序列比对10/10/37第37页模型建立模型建立l3.Hmmbuildl4.Hmmtl5.Hmmcalibrate模型建立模型建立用相关序列对模型用相关序列对模型进行训练进行训练参数调整参数调整10/10/38第38页模型文件（模型文件（1）HMMER2.0 2.3.2NAME globins50LENG 162ALPH AminoRF noCS noMAP yesCOM ./hmmbuild globins.hmm globins50.msfNSEQ 50DATE Thu Sep 18 00:02:14 CKSUM 4694XT -8455 -4 -1000 -1000 -8455 -4 -8455 -4NULT -4 -8455NULE 595 -1558 85 338 -294 453 -1158 197 249 902 -1085 -142 -21 -313 45 531 201 384 -1998 -64410/10/39第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 *10/10/40第40页6.未知序列搜索查询未知序列搜索查询lHmmsearch:search a sequence against the profile HMMl未知查询序列Artemia.falProfile HMM：Globin.hmmlCommand:hmmsearch globin.hmm Artemia.fa查询程序查询程序查询未知序列文查询未知序列文件件所用模型所用模型查询命令查询命令10/10/41第41页查询结果查询结果l结果分为2个部分l1：说明部分（数听说明、选项、模型说明）l2:结果序列部分10/10/42第42页Result1第一部分：相关信息说明第一部分：相关信息说明软件信息：版本、权限等软件信息：版本、权限等HMM文件名称，查询阈值文件名称，查询阈值等等HMM文件一些描述信息10/10/43第43页Result 2.1HIT序列分值，序列分值，E值，值，domain数目数目HIT domains分值、位置、分值、位置、E值等信息值等信息10/10/44第44页Result 2.2高分匹配序列比对高分匹配序列比对10/10/45第45页Result 2.3全部序列全部序列HIT分值、分值、E值图值图形分布形分布10/10/46第46页Result 2.4结果统计数据结果统计数据10/10/47第47页Application of HMM:pfam10/10/48第48页Application of HMMlTMHMM:Prediction of transmembrane helices in proteinslhttp:/www.cbs.dtu.dk/services/TMHMM/10/10/49第49页PFAMPfam 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 http:/www.sanger.ac.uk/Software/Pfam/,in Sweden at http:/www.cgb.ki.se/Pfam/,in France at http:/pfam.jouy.inra.fr/and in the US at http:/pfam.wustl.edu/.10/10/50第50页Pfam IntroductionlPfam 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.lPfam contains functional annotation,literature references and database links for each family.10/10/51第51页Pfam IntroductionlVersion 14.0,June,7459 families22336 unique Pfam-A domain architectureslTwo big familieslPfam-A:A high-quality manual part of Pfam.lPfam-B:Low-quality automatically generated alignments of sequence clusters in SWISSPROT and TrEMBL that are not modelled in the curated part of Pfam.10/10/52第52页Pfam IntroductionlThere 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 database10/10/53第53页Pfam GoalslOne 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.10/10/54第54页蛋白二级结构分析蛋白二级结构分析lThe PredictProtein serverhttp:/blast.ym.edu.tw/tools/predictprotein/predictprotein.html 10/10/55第55页