欢迎回到北京大学生物信息学:导论与方法网上课程。
我是北京大学生物信息中心高歌
下面,让我们开始课程,Markov Model
首先,让我们来回顾一些基本的概念。
在第二周第一节中,我们提到了由于一次插入和删 除往往涉及到多个残基,因此与替换不同,一个空
位的长度常会大于1。
因此,空位罚分往往采取一种线性组合的模式,
也就是说,把gap open和gap extending区分 开来,分别给予不同的罚分。
要正确区分gap open和gap extending,需要引入 状态的概念,
换句话说,需要“记住”之前是否已经open了一个gap
具体来说,我们将一对残基之间可能的三种比对关系,称为三个不同的状态:
M表示两个残基彼此对上,但不一定相等;
X表示序列X的残基对到了一个空位,或者说在序列X上发生了一次插入;
而Y则表示序列Y的残基对到了一个空位,或者说在序列Y上发生了一次插入
基于这个状态的定义,我
们在第二周的补充材料中,利用计算机科学中有限状态机(Finite State Automation, FSA)模型,对于线性组合(affine gap)罚分系统给出了一个解。
具体来说,我们将序列比对描述为在三个不同状态之间不断转换的过程
并定义M(i,j)表示在Xi比对到Yj,也就是两个残基对在了一起的时候,第一条序列X从第1位到第i位、第二条序列Y从第1位到第j位最好的比对分数。
而X(i,j)和Y(i,j)则分别表示在Xi或Yj残基比对到空位时,序列X从第1位到第i位、序列Y从第1位到第j位最好的比对分数,
作为动态规划求解的迭代函数。
同样,与之前的F类似,我们也可以用动态规划矩阵来将三组状态转换关系表示为在三个平面之间的单元格填充,
只是对于每一个平面而言,回溯关系即可能来自于本平面,也可能来自于另外一个平面,或者说,另外一个状态。
换句话说,我们构造了一个Markov链 (Markov Chain)
Markov链是由俄国数学家Andrei Andreyevich Markov1906年引入的,一个基于概率的随机过程模型,用来刻画一组之间存在关联的随机事件
用来刻画一组之间存在关联的随机事件。
具体来说,Markov Chain用来描述一组离散状态之间在不同时刻的转移关系,
值得注意的是,这里的状态转换关系不需要是唯一确定的,只需要可以由一个概率分布描述即可。
唯一的要求是,t时刻状态的概率分布,由且只由之前有限的m个时刻状态的概率分布确定,
称之为m阶马尔科夫链(m-order Markov Chain)
事实上,我们通常可以只考虑其最简化的情形:1阶马尔科夫链,也就是当前的状态与且只与其前一个状态相关。
具体来说,我们可以引入转移概率的概念,
用α{k,l}描述在t时刻从k态转移到l态的概率,
并进而构成一个转移矩阵。
从定义上可以知道,α{k,l}和α{l,k}未必相等,
因此这个矩阵是沿对角线不对称的。
通常,我们会假定这个转移概率与t无关,也就是所谓的齐次Markov Chain(Stationary Markov Chain)
而这也恰好是刚刚提过的线性组合罚分的情形
我们之前提到过,要正确区分gap open和gap extending,其实只需要“记住”前一个状态是什么就可以了:
如果是M,那么可以选择开启一个新gap,从而转进到X或Y状态;
而如果已经在X或Y,那么或者继续延伸gap,要么关掉gap
具体来看,
我们首先有三个状态,M, X, Y,
分别表示两个残基彼此对上、序列X的残基对到了一个空位和序列Y的残基对到了一个空位。
从M态可以到产生新的gap,也就是转换到X或Y
而X、Y也可以转换到自己,表示gap的延伸
当然,M也可以转换到自己,表示连续、无gap的延伸
另一方面,X和Y都可以转换回M,表示gap的结束
进一步,我们可以对每种可能的转移都分配一个概率:
首先考虑M到X,Y,也就是gap open,以及X,Y到自身,也就是gap extending,
那么它们对应的概率分别设置为delta和epsilon
那么,通过全概率公式,我们可以导出其它几个转移的概率,并进而得到完整的转移概率矩阵。
由此,我们可以简单的根据乘法定理来计算出任何一个比对的概率值。
例如对之前给的例子比对,我们可以简单的写出对应的状态XMMY。
并依次将相关的转移概率乘起来,就可以得到其对应的概率值。
事实上,我们可以对任意比对计算出概率,也就是说,我们通过引入Markov Chain,给出了序列比对的概率解释(Probabilistic interpretation) 。
在下一节里,我们将进一步引入隐马尔科夫模型,来在此基础上进一步拓展和深化。
好,这是本节的思考题,欢迎有兴趣的同学认真思考,并积极通过论坛与其他同学及助教进行交流讨论。
下节见!