当前位置:首页 期刊杂志

基于POA有向无环图及隐马尔科夫模型的优化PHMM算法

时间:2024-05-23

王靖会 孙启明

摘 要:随着基因组计划的实施,大量的基因组数据被测序,如何从海量数据中提取出有用的生物学信息,成为生物信息学研究中的重点。序列比对是生物信息学研究的基本方法和主要手段,目前已经有很多比对算法,但如何提高算法敏感性及准确性,仍旧是一个难题。基于这种情况,本文基于POA有向无环图算法及隐马尔科夫模型,创新性的提出一种新的算法PHMM算法,这种算法打破传统的线性序列比对,采用了一种基于图论的渐进比对算法,对参数选择具有一定先进性。

关键词:生物信息学;序列比对;POA有向无环图;隐马尔科夫模型;PHMM算法

中图分类号:Q811.2 文献标识码:A DOI:10.11974/nyyjs.20160532013

1 引言

随着人类基因组计划的实施和发展,基因组和蛋白质组研究的也不断深化,伴随而来产生大量的基因序列数据。生物信息学[1]在生物数据分析和处理中的应用越来越广泛,这使得序列分析[2]成为计算机在生物学中研究的热点,并使现代生物学研究方法发生了深刻的改变。生物信息学的研究重点主要分2部分:基因组学方面、蛋白质组学方面。简单的说就是通过分析核酸和蛋白质的序列,得到其表达结构,找到功能及进化的信息。从而阐明生物所携带的生物信息及生命意义。

2 多序列比对算法优化

2.1 多序列比对(MSA)问题描述

对于给定的N条序列,S1,S2,…SN,Sk为N条序列中的1条,Sk∈[S1,SN], Sk=sk1sk2…skn , k=1,2,…N,n>0.skn为N条序列中的任意1条上的1个残基,若该序列为DNA分子序列,则skn属于集合{A,T,C,G},若该序列为RNA分子序列,则skn属于集合{A,U,G,C},若该序列为蛋白质序列,则skn为20种氨基酸中的1种,它的集合中包含20种氨基酸。在生物长期进化发展过程中,会出现少数残基缺失,插入或变异的现象,因此在多序列比对过程中可能会出现序列中断(break)现象,既间隙(gap)问题。当出现间隙时,可以用“—”来表示。当用Σ‘表示序列的集合时,Σ=Σ∪{—}。则多序列比对可以按如下定义:

1个多重序列比对A是1个二维字符矩阵,即A={skn‘},k=1,2,…N,n>0。

其中skn=skn或“—”,并满足以下条件:

序列的数目等于矩阵的行数;

如果移去每行中的“—”将得到原来的序列;

每1列中不允许所有元素同时为“—”。

从定义可以看出,多序列的比对[3-5]可以模拟生物序列的进化过程,当序列中的残基经过插入,删除或替代,则产生了变异,再经过多代的遗传与积累,最终产生较大差异。

2.2 POA算法

POA算法是1种使用偏序图(partially ordered graph)的算法,这种算法不同于其他多序列比对算法,摒弃了传统的线性比对,在POA比对算法中,每个字母代表1个节点,在相邻的节点间用有向边表示,1条序列就是1个有向无环的节点序列。对于MSA格式的序列,首先将每条序列都用POA算法画图,然后将相同的字母对齐合并,对于不能合并的节点,称为分离节点,分离节点单独画出;对于有多条入边或多条出边的节点,称为汇合节点;与汇合节点相连的多条边叫做分支。

POA算法计算相似矩阵时首先是用聚合最近邻聚类算法,根据计算得分构建进化树。对于汇合节点,它可以有多个前驱,所以POA算法扩展了动态规划算法,对于2条序列S和S,设其得分为W(u , v),u和v分别是S和S的节点,为了计算W(u , v),需要考虑所有可能到达这2个节点的分支,则有:

其中,p是序列S中u节点的前分支,q是序列S中v节点的前分支。Δ是空格罚分,W(u , v)是u和v的得分。

2.3 隐马尔科夫模型

隐马尔科夫模型(Hidden Markov Model ,HMM)[6-7]是由马尔科夫模型发展而来。马尔科夫模型是马尔科夫链的模型化过程,这是一种状态空间中从一种状态到另一种状态的随机过程。如果一个将来状态仅依赖于现在状态,而不依赖于过去的状态,这个过程具有马尔科夫性,可称为马尔科夫过程。用公式表示,为:

隐马尔科夫模型是由2个随机变量序列组成的,一条是观察不到的隐马尔科夫链,(Yn ,n≥0);另外一条是可以观察到的随机序列(Xn ,n≥0),{ Yn≥0}称为马尔科夫链,{ Xn ≥0}称为其观察链。马尔科夫链与观察链之间通过一组概率相联系。

2.4 基于POA算法的HMM模型优化算法PHMM

2.4.1 POA模型的引入

PHMM算法是一种建立于图论比对与隐马尔科夫模型结合的一种比对算法,基于图论比对算法打破传统的线性比对算法,根据图中汇合节点计算序列间的距离,然后构建指导树,按指导树顺序进行渐进比对。

对待比对序列进行POA画图,设A为待比对序列的集合,共有N条序列,则A={A1,A2,,…AN},每条序列长为Li,即含每条序列含有i个残基,每个残疾对应自己的位置i,则有L1,L2,…LI。对于集合A中的序列,要找到调和序列。调和序列是保守区域最多的序列,用调和序列与剩余的其他序列进行相似性计算。对于输入的多个序列,会存在很多重复片段,所以构造POA图的第1步是去环,采用了深度优先搜索算法找到环,然后根据其他信息去掉序列中的环。去环的方法最简单的是切断环中的一条边,根据环上的信息,选取关联信息最少的边进行切断。经过去环过程后,可以得到一个有向无环序列。将待比对序列全部去环处理后,下一步就是找到调和序列。可以通过对节点的重叠次数进行加权计算,这样就可以找到最大权值路径,即要找到的调和序列。

2.4.2 PHMM模型的引入

对于已找到的调和序列AK,作为HMM模型中的初始状态概率π,待比对序列作为固定的状态序列,每条序列与调和序列的相似性作为观察序列的概率,则有:

待比对序列中的任意一条序列Ai与调和序列比对产生的相似概率Q:

accuracu(Ai,Ak )=(2条序列Ai 与AK 中的正确匹配数目)/(AK 序列数目)

在给定的待比对序列(状态序列)A={A1,A2,,…AN}下,产生的2条序列比对的相似概率(观察序列)Q的概率为:

构建进化树有2类方法:使用特征数据(characters)、使用距离数据(distances)。使用数据特征构建进化树一般是针对有限的不同状态的特征,而距离数据一般是用于序列间的差异的衡量。一旦确认了相似性,就可以转换成距离数据。

计算2个序列间的距离D,可以用匹配的残基数目m,比上序列的总数目,通过计算出2个序列间的距离后,建立距离矩阵,距离矩阵是所有待比对序列的总结。根据距离矩阵构建进化树。PHMM算法采用的是类似于UPGMA(Unweighted pair group method using arithmetic averages)的方法构建进化树。PHMM算法对于待比对序列结合A中的序列,每条序列与调和序列都可以进行期望精确度计算E=Ei(Ai,AK),通过对期望精确度的计算,期望精确度越高,则优先加入比对。

3 结论

随着实验方法的增多和检测手段的发展,生物基因序列数据被大量测序,如何解决这些生物数据,从数据中提取有用信息成为生物信息学研究中的重要任务。而多序列比对作为生物信息学研究中的重要手段,如何研究新的比对方法,优化算法也成为生物信息学中的主要内容。

本文针对这一问题,基于POA无环有向图的拓扑结构和统计学算法中的隐马尔科夫模型,研究了一种新的算法PHMM算法。PHMM算法属于渐进比对算法的一种,对于渐进比对算法参数选择问题[8]上有一定先进性,可以提高比对质量的准确性。

参考文献

[1]陈润生.生物信息学[J].生物物理学报,1999(15),1.

[2]唐玉荣.生物信息学中的序列比对算法[J].计算机工程与应用,2003(29):5-7.

[3]霍红卫.序列比较问题的分治法[J].西安电子科技大学学报,1998,25(3):345-348.

[4]郭卫斌,施保昌,王能超.多重生物序列对准及其算法综述[J].高科技通讯,2001(6):96-102.

[5]Yuzhen Ye and Adam Godzik . Multiple flexible structure alignment using partial order graphs[J].Bioinformatics,2005,21(10):2362-2369.

[6] Ocak,H.,Loparo,K.A. new bearing fault detection and diagnosis based on hidden Markov modeling of vibration signals[J].Acoustics,Speech,and Signal Processing.2001.Proceedings.2001 IEEE International Conference on,2001(5):3141-3144.

[7]方绍武,戴蓓倩.一种离散隐Markov模型参数的全局优化算法[J].电路与系统学报,2000,30(6):659-665.

[8]高雨清,陈永彬. 隐Markov模型参数估计的一种新方法[J].自动化学报.1991,17(1):56-62.

免责声明

我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自各大过期杂志,内容仅供学习参考,不准确地方联系删除处理!