【生物信息学】从状态到马尔科夫链 | 学习课

 课程整理链接：

https://mubu.com/doc/kO-X8ggFD0

视频链接：

https://www.bilibili.com/video/av10042290/?p=16

从状态到马尔科夫链

基本概念

一对残基的3种状态：具体请见19.0319课程

M表示两个残基彼此对上，但不一定相等；

X表示序列X的残基对到了一个空位，或者说在序列X上发生了一次插入；

Y则表示序列Y的残基对到了一个空位，或者说在序列Y上发生了一次插入。

线性组合(affine gap)罚分系统：具体请见19.0319课程

将序列比对描述为在三个不同状态之间不断转换的过程

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位最好的比对分数，作为动态规划求解的迭代函数。

马尔科夫链 Markov Chain

定义：由俄国数学家Andrei Andreyevich Markov1906年引入的，一个基于概率的随机过程模型，用来刻画一组之间存在关联的随机事件。

m阶马尔科夫链(m-order Markov Chain)

定义：用来描述一组离散状态之间在不同时刻的转移关系，值得注意的是，这里的状态转换关系不需要是唯一确定的，只需要可以由一个概率分布描述即可。唯一的要求是，t时刻状态的概率分布，有且只有之前有限的m个时刻状态的概率分布确定。

1阶马尔科夫链

定义：最简化的情形，即当前的状态有且只与其前一个状态相关。

齐次Markov Chain(Stationary Markov Chain)

定义：假定转移概率与t无关

转移概率：指用α{k,l}描述在t时刻从k态转移到l态的概率，并进而构成一个转移矩阵。从定义可知，α{k,l}和α{l,k}未必相等，因此这个矩阵是沿对角线不对称的。

回到一对残基的3个状态（区分gap open和gap extending）

定义：1. 从M态可以到产生新的gap，也就是转换到X或Y；2. X、Y也可以转换到自己，表示gap的延伸；3. M也可以转换到自己，表示连续、无gap的延伸；4. X和Y都可以转换回M，表示gap的结束。

分配转移概率：gap open-delta，gap extending-epsilon。

转移概率矩阵：通过全概率公式，导出其它几个转移的概率。由此，我们可以简单的根据乘法定理来计算出任何一个比对的概率值。

以之前的序列为例（LSP-/-TPE）

序列比对的概率解释 Probabilistic interpretation

通过引入马尔科夫链，可以对任意比对计算出概率

往期阅读