欢迎回到北京大学生物信息学:导论与方法网上课程。 我是北京大学生物信息中心高歌, 我们来继续课程,Markov Model 在上个单元里,我们介绍了Markov Chain 通过引入状态的概念,我们可以区分gap open和gap extending。 从而正确完成空位的线性组合罚分,并进而对任意比对计算出一个概率值 但很容易可以发现,仅靠这些还不足以真正完成序列比对。因为现有的状态模型只是区分了空位状态X,Y以及Match状态M, 而没有考虑具体的残基 因此,我们需要进一步引入隐马尔科夫模型。 所谓隐马尔科夫模型,是指在状态的基础上,增加了符号(Token)的概念。 每个状态都可以以不同的概率产生(Emit)一组可以观察到的符号 也就是说,除了状态转移概率之外,隐马尔科夫模型进一步引入了“生成概率”(Emission Probability) 的概念, 每个状态都有自己的生成概率分布,可以按照不同的概率产生一组可以被观测到的符号。 与上节介绍的情形不同,在隐马尔科夫模型里,状态路径是无法直接看到的。 这也是Hidden Markov Model中Hidden的含义。 相反,我们需要根据观测到的符号,来推测对应的状态 例如,当我们观测到字符串aabc时,对应的状态路径(state path)可能是1,1,2,3,也可能是1,2,3,3、1,3,3,3甚至1,1,1,1、2,2,2,2、3,3,3,3等, 因为其实每个状态都有可能产生a,b和c。 但问题在于,不同的状态产生a,b,c的概率不同, 进而不同的状态路径产生最终被观测到的字符串aabc的概率也不同。 理论上讲,我们可以所有可能的路径穷尽出来, 对吧? 然后我每个里面,我都可以算出一个路径的概率来。 对吧? 然后我取概率最大的那个, 就是我最可能的路径. 比如,状态路径1,2,3,3产生aabc的概率 是状态1产生a的概率0.8,乘以状态1转移到状态2的概率0.3,再乘以状态2产生a的概率0.2,再乘以状态2转移到状态3的概率0.5。 再乘以状态3产生b的概率0.3,再乘以状态3转移到状态3的概率1,再乘以状态3产生c的概率0.1得到的总乘积0.0072。 事实上,对每个可能的状态路径,我们都可以按照这个办法,来计算其产生aabc字符串的可能性, 而其中概率最大的那个状态路径,也就是最可能产生这个字串的状态路径 为了方便,我们在上节定义的转移概率alpha k,l之外,再定义生成概率e k,b, 表示在状态S k 时,产生符号(token)b的概率 这样,我们就可以按照上节所说,利用乘法原理,把状态路径X产生观测符号串Y的概率简单的写成两者的乘积。 简单介绍完了隐马尔科夫模型,我们再回到之前提到的考虑空位线性罚分模式的序列比对问题来。 之前提到过,上节建立的Markov Chain通过引入空位状态X,Y以及Match状态M, 可以很好的处理gap open和gap extending, 但没有考虑具体的残基。 因此,我们接下来通过引入刚刚介绍的隐马尔科夫模型来补完这一点。 具体来说,我们用生成概率来处理残基,M状态生成的符号是所有可能的残基替代,其生成概率写作p a,b 而X和Y状态生成的符号则是所有可能插入的残基, 其生成概率写作q a 这样,我们就可以很方便的同时考虑状态和具体的残基, 并进而将序列比对问题重新描述为一个针对特定隐马尔科夫模型与符号串寻找最可能状态路径的问题 具体来说,我们可以应用动态规划的思想,来分步求解。 我们定义PM(i,j)表示在Xi比对到Yj,也就是两个残基对在了一起的时候,第一条序列X从第1位到第i位、第二条序列Y从第1位到第j位最大的概率。 而PX(i,j)和PY(i,j)则分别表示在Xi或Yj残基比对到空位时,序列X从第1位到第i位、序列Y从第1位到第j位最大的概率。 这样,我们就可以进一步根据状态转换图来定义每步的迭代函数。 并进一步应用动态规划的back tracking来得到最终的比对 好,简单总结一下。 本节我们通过引入隐马尔科夫模型,来解决序列比对中线性组合空位问题。 这里,之前看过第二周补充视频的同学可能会产生一个疑问: 第二周时,我们简单的通过引入M,X,Y状态,就已经解决了这个问题, 那么我们为什么在这里还要再如此费力的、花了两个单元的时间,来引入隐马尔科夫模型和这么多的新概念呢? 那么这些新东西,又能给我们带来什么新的好处呢? 首先,隐马尔科夫模型的引入,有效地给出了序列比对的概率解释(Probabilistic interpretation)。 例如,这里的delta就可以理解为在生物演化过程中,出现DNA片段插入/删除的概率, 或者说,产生一个空位的概率 再如,M状态的生成概率,就可以直观地对应于演化过程中相应替代发生的频率 同时,概率模型的引入,还可以帮助我们利用概率论的知识做更多分析。 例如,我们可以在不引入具体比对的情况下,计算两条序列之间最大可能的相似性 事实上,在本节开始的时候我们就提到,隐马尔科夫模型中,同一个观察序列可以来自于许多不同的状态路径。 因此,当我们将所有可能状态路径对应的概率求和时, 就得到了相应观察序列对应的全概率(Full probability)。 在序列比对这个问题上,也就是两条序列之间所有可能的比对概率之和, 或者说,两条序列之间最大可能的相似性 而在具体操作上,实际上非常简单,我们只要将之前每一步迭代时的求最大值变为求和, 再将最后的求最大值变换为求和就可以了。 因为这个方法是将所有可能的比对概率求和,不依赖于特定的比对, 对于之前曾提到的存在多个最优比对的情形尤其重要。 那么最后(the last but not the least),我们要说隐马尔科夫模型通过符号观测序列来反推隐状态这个特点,它的应用领域并不局限于序列比对。 事实上,在现代生物信息学的研究中,隐马尔科夫模型更多的被作为预测器(predictor)来使用,这也是我们下个单元要介绍的内容。 好,这是本节的思考题,欢迎有兴趣的同学认真思考,并积极通过论坛与其他同学及助教进行交流讨论 谢谢大家,我们下节见!