Week4_Bioinformatics

MOOC Bioinformatics

Markov Chain

Introduction to Markov chain

序列比对时的状态变化

在序列分析时，需要对gap open 和gap extending分别进行空位罚分，因此需要记住前一个位子的状态，即是否已经是一个空位。

对具体一个空位来说，有具体一下三种可能的状态：
- M: 残基相对（不一定相同）
- X: X链上残基与空位相对
- Y: y链上残基与空位相对

我们可以讲序列对比叙述成在不同状态之间的转换：
- M(i,j): Xi比对到Yj时，序列的最佳比对途径分数
- X(i,j): X(i,j)与空位相对时，序列的最佳比对途径分数
- Y(i,j): Y(i,j)与空位相对时，序列的最佳比对途径分数

Markov Chain

n阶马尔科夫链

Markov Chain describe a discrete stochastic(ramdon) process at successive times. The transitions from one state to all other states, including itself, are governed by a probability distribution.

用于描述一组离散的状态之间的转移关系（不需唯一缺点，能用概率分布描述即可）

唯一的要求：
t时刻的状态分布，由且只由之前有限的n个时刻状态的概率分布确定 ==> n阶马尔科夫链

$P(X_t|X_1...X_{t-1}) = P(X_i|X_{t-n}...X_{t-1})$
$X_t = P(X_{t-1},X_{t-2}...X_{t-n})$

1阶马尔科夫链

$P(X_{t})$ 与且只与$P(X_{t-1})$ 相关

转移概率

$a_{(kl)}$ t时刻从k状态到l状态的概率

$a_{(kl)} = P(X_t=S_l|X_{t-1}=S_k)$
$a_{(lk)} = P(X_t=S_k|X_{t-1}=S_l)$
上述两者不一定相等

转移矩阵（沿对角线不对称）

假定转移的概率与t无关==>齐次马尔科夫链

假定：
gap openning的概率为$\delta$
gap extending的概率是$\epsilon$
根据全概率公式可以推出：
gap结束（从X或Y到M）概率为$1-\epsilon$
非空位延续的概率是$1-2\delta$

所以转移矩阵是：

根据乘法概率：

所以上面的状态是X-->M-->M-->Y，则：
$P(XMMY) = (1-\epsilon)(1-2\delta)\epsilon$

隐形马尔科夫链(Hidden Markov Chain)

The observable symbols ("Token",y(t)) are generated according to their corresponding states(x(t))

即我们无法观测到具体的state path，但是可以观测其每一步的对应符号("Token path")，所以每一步的概率应该是：
Transition Probability + Emission Probability

根据Token path:
$a_{kl} = P(X_t = S_l|X_{t-1} = Sk)$
$e_k(b) = P(y_i = b| X_i = S_k)$ 从状态$S_k$产生b的概率
从状态路径x产生观测符号Y的概率：
$P(X,Y) = \Pi_{(L,i=1)}(e_{xi}(y_i) \times a_{xi,xi+1})$

假定：
Match，所有可能的残基取代，概率为$P_{ab}$
$X_{insertion}$，空位对所有可能的残基，概率为$q_a$
$Y_{insertion}$，空位对所有可能的残基，概率为$q_a$

$P_{M(i,j)}$两残基相对，在x链上从第一位到$X_i$，在y链上从第一位到$Y_j$最大的概率
$P_{X(i,j)}$，x链上的残基对空位，在x链上从第一位到$X_i$，在y链上从第一位到$Y_j$最大的概率

根据状态转换率，定义迭代函数：
$P(X,Y,ali) = max(P_{M(n,m)},P_{X(n,m)},P_{Y(n,m)})$

Probability Interpretation

$\epsilon$，在生物演化过程中发生序列插入或替换的概率

Hidden Markov Chain --> A Pridictor

Predictor of Hidden Markov Chain

Most simple Gene Prediction

给定的DNA序列推测不可观察的 Hidden state: Coding / Non-Coding