生物信息学实验市公开课一等奖百校联赛特等奖课件.pptx
《生物信息学实验市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《生物信息学实验市公开课一等奖百校联赛特等奖课件.pptx(55页珍藏版)》请在咨信网上搜索。
1、生物信息学试验生物信息学试验试验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 Mar
2、kov 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
3、 Ejn出现概率为 p(Ej1 Ej2 Ejn)=pj1 Pjn。10/10/7第7页马尔科夫链马尔科夫链l普通及惯用统计中,彼此相互独立大约是最有用一个观念。用简单术语來说,相互独立就是彼此毫不相干,一点牵涉都沒有。l不过实际生活中很多事件是相互关联l不是相互独立也就是相互关联意思,不过要怎样相关呢?怎样在相关中作一些简单分类呢?马尔科夫链就是要描述在相关这个概念中最简单一个。但即使如此,相关马可夫链理论已经相当丰富了。在概率理论中,它几乎占了绝大部分。10/10/8第8页马尔科夫链马尔科夫链l在马尔科夫链中考虑最简单相关性。在在这种情况下,我们不能给任一个事件 Ej 一個概率 pj 但我们
4、给一对事件(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
5、/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
6、|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 direct
7、ly 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 algori
8、thm定义向前变量采取动态规划算法,复杂度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
9、 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概率:1
10、0/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 s
11、imilar 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=
12、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
13、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
14、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/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生物 信息学 实验 公开 一等奖 联赛 特等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。