大家好,今天我们首先要给大家介绍马尔科夫模型、 隐马尔科夫模型和Profile隐马尔科夫模型的历史特性、算法和应用。
这是我们一个整个的Outline,时间和状态都是离散的马尔科夫过程称为马尔科夫链。- 它状态间的转移仅依赖于
前一个状态过程,这个过程被称为n阶马尔科夫模型。其中 n是影响下一个状态选择的前(n)个状态。最简单的马尔科夫模型是一阶
模型,它的状态选择仅与前一个状态有关。马尔可夫模型有三个参数,不同的状态不随
时间改变的状态转移去任何初始概率。以天气为例,晴天、多云和阴天是三个不同的状态。
状态转移矩阵则表示从一个状态到下一个状态的转移概率。Pi向量则是第一天分别有13种- 天气的可能性。
在某些情况下我们希望找到的模式用马尔可夫模型描述显得不够充分;回顾一下天气的那- 个例子。
现在有一个宅男他足不出户,所以不能够直接获取到天气状态的观察情况;但是他养一些水藻- ,而且水藻
的状态是以天气的状态有一定的概率关系的。湿透的海藻意味着阴雨;而干燥的海藻则意味着- 阳光灿烂。
它这个例子中我们有两组状态,观察到的状态就是水藻的状态和隐藏在黑箱中无法观察到天气- 的状态。而观察得到
的状态的序列与隐藏的状态之间有一定的概率关系。
宅男就希望设计出一种模型算法,能够在不直接观察到天气的
情况下通过水藻和马尔可夫假设来预测天气的变化模型;就是隐马尔可夫模型还有五个参- 数隐藏的
状态就是系统的真实状态。它是用马尔可夫模式进行描述的,观察的状态就是我们可以看到的- 海藻的湿度,然后
又有一个隐藏状态到另一个隐藏状态转移矩阵,和给定一个隐藏状态 生成某一个观察状态的生成矩阵,以及Pi向量也就是初始向量。
以最初应用的蛋白质方面为例,运用HMM方法对某一个家族蛋白质描述出Profile,
换句话说,蛋白家族的Profile及只对所有成员蛋白共同具有的特性,就是全部保守序- 列或者不保守部分。
有变化的可能性及其概率对它们进行统计学描述,至于描述是和位置特意相关的。在寻找
新的成员蛋白质用这个Profile对数据库中的每一个candidate进行打分,以- 此判断是否为家族成员。
在宅男和海藻的例子中,我们可以把Profile Hidden Markov
model理解为世界上是有很多测量天气的宅男,每一个人 每一天观察到不同的海藻状态得到了不同的天气状态。以此为基础,建立了一系列
转移矩阵和生成矩阵的合集,封装成一个能有效预测海藻和天气关系的Profile。
一旦一个系统可以做为HMM被描述,就可用来解决三个基本问题。其中前两是模式识别问题- ,第一个是
评估就是说给定Hidden Markov model求一个观察序列的概率。第二个是解码,就是搜索最有可能生成一个
观察序列的隐藏的状态。第三个是学习,就是给定观察序列生成一个或者一系列的Hidden Markov model。
回到宅男养海藻看天气这个问题上来,Evaluating的目的是在一群Hidden Markov
model中 挑出一个最合适的来,或者评估这些Hidden Markov model是否符合观察与模型相符的概率最大。
上图列出了已经的到的转移矩阵和生成矩阵, 例如,按视频讲过的求和方法我们可以计算第二天cloudy的概率和。
利用高阶贝叶斯和递归最后得了海藻状态序列,再给定Hidden Markov model
情况下对应的最大自然天气序列及可用于评估的概率。
求出海藻对应的天气概率可以使用Viterbi算法,在此列出
公式不做详述。至于概率和Forward的算法最大的区别在于就是某条 最可能的路径概率而不是每一步的概率和。
左侧的公式其实可观察的状态为K7的Di个状态的最大部分概率的计算公式。但是
对于每个时刻的每个状态都有这样一个概率和部分最优路径,所以我们就需要定义
一个后向指针Pi,如右侧所示,记住这个状态以便最后到OT时进行反推,
所以最后可能只有一个路径是有用的,所以可以用下面的两个公式反推回去。
Baum-Welch或者是BW算法其实是最常用的序列算法, 也是通常构建隐马尔可夫模型时,不止转移和混淆指针首先要做的事情。
首先对于因马尔可夫模型参数进行了初始的估计,但这个很可能是一个错误的猜测。然后通过- 对于给定的
数据评估,再用Veterbi算法和后向指针反推,更新隐马尔可夫模型参数,使得和给定- 的序列数据的误差变小。
对于每一个状态,BW算法既可以计算达到此状态的前向概率alpha,用后向
算法,尤其诠释此状态的最终状态的后向概率,用Forward算法这些概率都可以通过递- 归计算。
应用在蛋白序列中,Profile隐马尔可夫模型与海藻例子类似,对应关系是一天的- 海藻湿度
对应一个位置上氨基酸种类,几天测出的一组海藻湿度数据对应一个具体蛋白的安氨基酸序列。
天气状况代表这个位置上的氨基酸处于那种功能区,如果同一段时间内不同地区的
宅男同时进行天气预测工作,则可以假设相似地区的海藻状态是一个蛋白质家族。
如果每人每天得到的转移矩阵和生成矩阵都不同,他们 构成的隐马尔可夫模型合集是一个家族蛋白的Profile。
蛋白profile Hidden Markov model构建首先要对已知的蛋白质序列进行多序列比对,再次为了简便,
用原理相似的核苷酸序列比对解释比对方法。所谓比对,就是要找出多个序列中相似的
核心及图中框框所围出来的区域,而忽略差异交代的外围,及两侧变化交代的区域。
假如我们已经建立一个以现有多序列为基础的Profile隐马尔科夫模型,那么任给一个- 类似的序列我们
就可以通过现有的这个隐马尔科夫模型来确定新给的序列的最可能的隐状态
及哪些是核心区域那些是外围区域,这就完成了多序列的比对过程。
但是,我们刚才讲过,一个隐马尔科夫模型建立必须以比对好的序列
确定了核心与外围的区域的多条序列为基础。这就如同鸡与蛋的关系一样。
那么这个悖论该如何解决呢?一个可能的过程便是先建立一个猜测的模型,再用这个模型进行- 比对,最后
利用结果修正整个猜测,反复迭代这个过程便可以得到一个精确的模型。这里是一个状态处理-
情况下的 流程图,即首先估计参数,然后加入新的序列计算最可能的隐状态,
再用算法修正参数,重复这个过程直到达到稳态,即为所求的比对结果。
首先是确定初始参数,可以利用随机函数, 主要估计的是转移指针或小指针和初始状态的各个参数。
之后加入一个新的序列计算得到最可能生成这个序列的 序列的隐状态的值。如图中的隐状态即为IMMMM。
这个过程利用Veterbi算法,就是一个基于动态规划的算法,
得到了隐状态之后,基于隐状态和显状态便可以利用BWBW算法得到
新的转移、指针和小指针的值。这样就完成了对初始参数的一次修正。
不断的加入新的序列,不断的对参数进行修正,当参数变化幅度很小时就说明参数达到了最优。
这个方法的好处不仅在于它的速度,更在于它有一定的生物学意义。首先这个方法对于目标序- 列是自适应的。
也就是说只取决于目标的序列,与之前的任何经验无关; 这样就避免了在一个全新的序列中之前经验不适用的情况。
其次,这个方法很容易,与其他生物学方法结合。例如,可以利用结构的数据对比对的结果进-
行修正, 获得更符合生物学功能的模型。同时,这个方法非常的灵活,可以
满足多种条件下的不同需求,故这个多序列解决算法是一个非常好的算法。
当然这部算法也有一定的不足,首先这种逐次迭代的方法不能保证获得全球最优解。为了解决- 这一问题
问题可以引入一些随机的扰动,增加跳出局部最优区域的概率,还可以引入模拟iii的算法,
增大的到全球最优解的概率。其次,这个训练模型的过程极为多序列比对的过程,
当比对的序列较少时,意味着序列就比较小,所以很难保证最终结果接近最优解。
解决的方法是引入其他的序列,及利用先前的经验,但这样无疑会降低比对结果的可信度。
最后,状态的选择是任意的。一般选取的是序列的平均长度,但在很多情况下不使用。因此,- 后来有人
在这个算法的训练过程中添加了对于状态数的修正, 能通过训练来使状态做出改变,确定一个最大的概率。
这里是我们的参考文献,谢谢大家。