目录
Markov Model
1、概念
- 转移矩阵Transition metrics：A
- 不动点state probablity vector(π)：需要满足π为A的特征向量【πA=π】，且π的数值和为1(概率分布的特点)
2、特点
可达、互通、不可约，常返和周期性
3、不动点计算-迭代求结果直至收敛
- 题目
- 结果
*Markov Model的缘起-Page Rank的算法
*为补充内容
PageRank算法的基本想法是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。PageRank是递归定义的，PageRank的计算可以通过迭代算法进行。
一个网页，如果指向该网页的PageRank值越高，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。PageRank值依赖于网络的拓扑结构，一旦网络的拓扑(连接关系)确定，PageRank值就确定。
Hidden Markov Model
1、与Markov chain区别
- 针对的问题：
- 马尔科夫模型：通常用于描述一个系统的未来状态仅依赖于当前状态的概率模型，适用于状态可以直接观察到的情况。
- 隐马尔科夫模型（HMM）：用于描述一个含有隐含未知参数的马尔可夫过程，其中状态不能直接观察到，但可以通过观测向量序列观察到。
- 模型参数：
- 马尔科夫模型：状态转移概率
- HMM：初始状态概率向量π、状态转移概率矩阵A和观测概率矩阵B。
- 状态是否可观测：
- 马尔科夫模型：状态是可以直接观察到的。
- HMM：存在两种状态，一种是隐含状态（hidden states），这些状态不能直接观察到；另一种是观测状态（observation states），这些状态可以通过观测向量序列观察到。
2、模型
- 隐过程X
- 观测过程Y
- 模型参数：初始分布π，转移矩阵A，隐状态的分布矩阵B
3、研究的数学问题
3.1 识别问题-由观测样本得到其来源
-
已知若干个隐马氏模型及其参数，对一个观测样本，决定它来自哪一个模型。即Bayesian判决
-
e.g.观测序列的概率计算，枚举复杂度高考虑使用前传算法和后传算法
-
前传算法
-
后传算法
3.2 解码问题－由观测样本得到隐状态
- 核心在于找到使得联合概率最大的解
- 单点最优：特定时间点上最可能状态
- 路径最优：最可能的状态序列，动态规划Viterbi算法
3.3 学习问题－由观测样本得到三个参数
- 两种情况：观测链对应的状态链已知/未知【学习原则：极大似然估计MLE】
- 状态已知，MLE
- 最优化问题
- 状态链要有充分长的样本(大数定律，以频率代替概率)。
- 状态未知，EM
- 当状态链未知时，由于似然函数的计算中包含了对所有可能的状态链的求和，计算过大，在实际中是不可能被采用的。使用递推算法做模型参数的粗略估计．
- 其核心思想是：在当前参数下，用期望值当成频数“数数”，并用的“频率”估计概率。这实际上是一种EM迭代算法思想。
- MLE和EM算法都是用于参数估计的方法，MLE适用于完全观测数据的情况，而EM算法适用于存在隐变量或不完全数据的情况，MLE可以看作是EM算法的一个特例。
- 当状态链未知时，由于似然函数的计算中包含了对所有可能的状态链的求和，计算过大，在实际中是不可能被采用的。使用递推算法做模型参数的粗略估计．
- EM算法
- EM【多项式时间复杂度】相较MLE优势
Viterbi算法实例
-
解码问题：Viterbi算法
给定观测序列，求最有可能的对应的状态序列
HMM应用
1、基因序列CpG岛识别
-
CpG岛（CpG island）
- 与经常转录的基因相关。
- 原理是在远离基因的部分，在C-G对中的C往往被甲基化抑制转录，这些CG对倾向于突变为TG；但是在promoter和coding regions附近，甲基化被抑制CGs被保留，则转录更容易。
-
模型框架
- 分类讨论：Island bases and NON-Island bases
- 隐层与显层
- 训练：ML或Forward/Backward algorithm
- 解码：Viterbi Algorithm
- 分类讨论：Island bases and NON-Island bases
2、基因识别
2.1 先验知识（Prior Knowledge）
-
生信中的Signals vs Contents：signal是DNA中的一种很小的pattern，e.g.start codon;content是一段DNA,e.g.exons
-
有些密码子比其他密码子更常见。
-
外显子通常比内含子短。
-
5' 剪接位点（外显子到内含子）通常是 GT； 3'剪接位点（内含子到外显子）通常为 AG。
-
核苷酸和二核苷酸的分布在内含子和外显子中通常不同。
2.2 真核和原核的基因识别面临不同问题
2.3 算法举例
- Genscan 最早– Weight Matrix, Weight Array and decision trees as signal sensors, HMMs for content sensors, overall HMM
- GeneMark – HMMs enhanced with ribosomal binding site recognition
- Genie – neural networks for splicing, HMMs for coding sensors, overall structure modeled by HMM
- HMMgene – HMM trained using conditional maximum likelihood
- Morgan – decision trees for exon classification, also Markov Models
- VEIL – sub-HMMs each to describe a different bit of the sequence, overall HMM
- The Viterbi Exon-Intron Locator (VEIL) was developed by John Henderson, Steven Salzberg, and Ken Fasman at Johns Hopkins University.
- 原理：使用由子 HMM 组成的 HMM，每个子 HMM描述序列的不同位点：上游非编码 DNA、外显子、内含子等；利用生物学知识“硬连接 ”部HMM，例如起始和终止密码子、剪接位点。
- 假设测试数据以非编码 DNA 开始并结束并包含一个基因。
3、其他
- 蛋白质家族识别：通过从一组已知同源的蛋白质序列中训练HMM模型，可以用来检测其他序列是否属于同一个蛋白质家族。这个应用可以帮助识别蛋白质家族中的保守区域，并搜索其他序列以识别它们是否属于同一个蛋白质家族。
- RNA二级结构预测：HMM可以帮助预测RNA分子的二级结构，尤其是在寻找具有保守二级结构的非编码RNA时。这对于理解RNA的功能和调控机制非常重要。
- 序列比对和模式发现：HMM能够识别序列中的保守模式或基序（motif），这对于功能预测和同源序列比对非常有用。例如，HMM可以用于识别蛋白质序列中的特定结构域或功能位点。
- 非编码RNA识别：HMM可以用于识别结构化的非编码RNA，尤其是在保守的二级结构区域中。这对于理解非编码RNA在基因调控中的作用至关重要。
- 蛋白质结构预测：HMM可以帮助预测蛋白质的二级结构和功能域，特别是在分析保守结构域时。这对于蛋白质工程和药物设计等领域具有重要意义