从状态到马尔可夫链

A Markov chain describes a discrete stochastic process at successive times. The transitions from one state to any of all states, including itself, are governed by a probability distribution.

马尔可夫链用来描述一组离散状态之间在不同时刻的转移关系。这里的转移关系不需要是唯一确定的，只需要可以由一个概率分布描述即可。
唯一的要求是：t时刻状态的概率分布由且只由之前有限个m时刻状态的概率分布来确定，称为m阶马尔可夫链。
一阶马尔可夫链：当前状态与且只与前一个状态有关。

转移概率：

k态到l态，l态到k态，转移概率矩阵不对称。
通常假设与t无关，齐次马尔可夫链，这也就是线性组合罚分的情形。

有限自动机：

M：匹配上了
X：X对-
Y：-对Y
Gap open：当前匹配，下一个不匹配。（不匹配就是由gap）
Gap extension：当前不匹配，下一个也不匹配。
北京大学生物信息学-第四周-马尔可夫 HMM及其应用

隐马尔可夫模型 Hidden Markov Model HMM

The observable symbols (“tokens”, y(t)) are generated according to their corresponding states (x(t)).
隐马尔科夫模型是指在状态的基础上增加了符号的概念。
每个状态都可以以不同的概率增加一组可以观测到的符号。
北京大学生物信息学-第四周-马尔可夫 HMM及其应用
In addition to State Transition Probability, each state of HMM has a probability distribution over the possible output tokens (Emission Probability 生成概率).

Thus, a HMM is consist of two strings of information.
– The state path 状态路径
– The token path (emitted sequence). 符号路径
But the state path is not directly visible
HMM状态路径与马尔可夫模型是不同的，不能直接看到，这也就是hidden
Instead, we have to infer the underling state path，based on the observable token path.
根据可以看到的符号路径来推测状态路径。

Given a HMM, a sequence of tokens could be generated as
following:
When we “visit” a state, we emit a token from the state’s emission probability distribution.
当我们“访问”一个状态时，从该状态的生成概率分布中发射一个令牌
Then, we choose which state to visit next, according to the state’s transition probability distribution.
然后，根据状态的转移概率分布，选择下一个访问哪个状态。

Each “token” of the HMM is an aligned pair of two residues (M state), or of a residue and a gap (X or Y state).
HMM的每个“令牌”都是比对成功的两个残基(M状态)，或者是一个残基和一个间隙(X或Y状态)。
– Transition and emission probabilities define the probability of each aligned pair of sequences.
转移和生成概率定义了每对比对序列的概率。
Based on the HMM, each alignment of two sequences can be assigned with a probability
在HMM的基础上，两个序列的每一次比对都有一个概率
– Given two input sequences, we look for an alignment with the maximum probability.
-给定两个输入序列，我们寻找最大概率的比对。

Probabilistic interpretation概率解释：

北京大学生物信息学-第四周-马尔可夫 HMM及其应用
δ：在生物演化过程中，出现DNA片段插入与删除的概率，或产生一个空位的概率。
M状态的生成概率，在生物演化过程中，相应替代发生的频率。
利用概率论的知识做更多的分析，计算两序列最大可能的相似性。
Given the nature of HMM, many different state paths can give
rise to the same token sequence.
HMM同一个观察序列可以来自许多不同的状态路径，概率求和的时候，所有序列之和，最大可能相似性。
北京大学生物信息学-第四周-马尔可夫 HMM及其应用
So we can simply sum up them together to get the full probability of a given token sequence.
所以我们可以简单地把它们加在一起来得到给定令牌序列的全部概率。

用隐马尔科夫模型建立预测模型

符号->状态路径

对每个可能的状态路径计算其产生观测符号序列的可能性，其中概率最大的路径，也就是最可能产生这个串的路径。

例子-The Most Simple Gene Predictor (MSGP)最简单的基因预测器：
Given a stretch of genomic sequence, where are the coding regions and where are noncoding regions? 给定一段基因序列，判断哪里是编码区域，哪里是非编码区域？

状态转换图：

北京大学生物信息学-第四周-马尔可夫 HMM及其应用

训练模型：

训练什么?

状态间的转移概率
每个状态的生成概率
从已知的“训练集”估计概率
带注释的基因组区域，带有编码/非编码序列标记

从而填写转移概率矩阵和生成概率矩阵：

对位置的基因组序列，反推出最可能的状态路径（概率最大的状态路径）：
公式：

需要做大量的乘法，不但比较慢，随着连乘次数的增加很容易数值过小，出现下溢的问题，所以引入对树的方法。