空位状态与马尔可夫模型
在空位罚分里面，我们将一对残基之间可能的比对关系，称为三种不同的状态
如图所示，M表示两个碱基彼此对上，但不一定相等，X表示X残基某碱基对上Y残基的一个空位，Y表示Y残基某碱基对上X残基的一个空位
序列比对可视为在M，X，Y这三个状态之间来回转换的过程，X可视为在Y残基的gap extending，Y也可视为在X残基上的gap extending；X，Y向M转移可视为关闭gap，M向X，Y转移可视为开启gap
根据图上对M，X，Y的定义有：
其中M为：
M
X为：
X
Y为：
Y
引入马尔可夫模型：
其中马尔可夫模型本次状态仅与上次状态有关，与上次再以前的状态都无关，由状态和转移概率组成
我们设X向X转移，Y向Y转移的概率为ε（gap extending），M向X，Y转移的概率为δ（gap open）；那么X，Y向M转移的概率为1-ε，M向M转移的概率为1-2δ（可以通过全概率公式计算）
有了右下角的表，我们可以计算任意状态的概率值
比方说XMMY这个状态
序列比对与HMM
上述模型仅考虑了空位状态的情况，并不代表所有的序列比对情况，也就是说我确定是M状态，其中M状态还包括match和mismatch，这两种情况的打分是不一样的，那么仅靠普通马尔可夫模型是么办法区分的，所以我们采用HMM来做模型
HMM相对于马尔可夫模型引入了符号的概念，即在状态转移链的基础上引入了可观察的符号项
除了有转移概率，还有生成概率
上半部分是状态转移，下半部分是观察概率
简而言之即：
公式
转移概率即状态之间转移到可能性，而观察概率就是具体为A，T，C，G四个碱基的概率
最终的概率值等于转移概率乘观察概率
示例
在M状态中，match为两个碱基S-S（匹配正确的），mismatch为两个碱基S-T（匹配错误的），因此这两个观察概率是不一样的
M状态的观察概率为pab(其中是指A-A，G-G，C-C，T-T这四种情况出现的概率)；X，Y的观察概率为qa(即A，T，C，G四种碱基比对到空位的概率)
以上各种情况的概率可以做成一张表，类似于动态规划的得分表，当然pab，qa组成的表中，其数值需要进行训练
最终乘相应的转移概率和观察概率即可，最后利用动态规划的回溯来求解即可,类比动态规划算法,采用HMM模型也需要事先根据序列的先验信息规定P[M(1,1)],P[X(1,1)]和P[Y(1,1)]的值,然后根据上图的迭代公式进行回溯
这里的PM即pab，Px，Py即为qa
对比下传统的动态规划算法，采用概率计算可能速度更快
当然，这些转移矩阵概率和观察矩阵概率需要通过训练集来训练得到，一般情况下根据序列情况进行参数训练，训练好以后可用于预测测试集的序列比对情况
可参考：//www.greatytc.com/p/866bfb75586a
