基于HMM的基因识别并行计算

1、基于HMM的基因识别并行计算摘要分析了传统的串行基因分析方法的局限性，阐述了基于隐马尔科夫模型的基因识别方法和原理，最后给出了基于隐马尔科夫模型的并行算法并进展了并行效果分析，指出了并行计算在生物信息学领域的广阔前景及重要意义。关键词基因识别；H；并行计算；生物信息学20世纪90年代以来，伴随着各种基因组测序方案的展开和分子构造测定技术的打破，数以百计的生物学数据库如雨后春笋般迅速出现和成长。如何利用这些不断爆炸性增长的有关生物分子的原始数据，有效解决基因识别问题显得越来越迫切。最初的基因分析方法是进展简单的核苷酸统计，而后加上剪切保守位点的检测。以后采用了人工神经网络、隐马尔科夫模型H1，2

2、等先进的信息处理和分析技术，进步基因识别的准确率。但由于生物信息数据量宏大，传统的串行算法往往无法处理或难以在满意的时间内得到结果。本文针对基因序列的识别，讨论隐马尔科夫模型分析算法的并行算法设计和并行效果分析。隐马尔科夫模型3Hiddenarkvdels，H是一种概率论模型，这种方法已经成功应用于多个领域，如语音识别、光学字符识别等。H在生物信息学领域中也有着重要的应用，如序列分析、基因识别等。目前，基因识别的H方法也大致可以分为两类，一类为按照内容搜索的方法，通过核苷酸和三联密码子等在编码区的分布规律来界定蛋白质的编码区；另一类为按照信号搜索的方法，通过编码区周围的信号界定蛋白质编码区。2

3、.1马尔科夫链考虑只取有限个或可数个状态的随机过程Xn，n=0，1，2，假设对一切状态i0，i1，in-1，i，j和一切n0，有PXn+1=j|Xn=i，Xn-1=in-1，X1=i1，X0=i0=PXn+1=j|Xn=i成立，那么称此随机过程为离散状态马尔科夫链。简单的说，就是系统将来的状态仅依赖于当前状态。一个马尔科夫链的概率分布完全由它的初始分布P(X0)与转移矩阵P=(pij)决定。2.2H根本原理隐马尔科夫模型H是由马尔科夫链开展扩大而来的一种随机模型。H可以被理解为一个双重随机过程，一个是不可观察的隐含的状态变化序列，另一个是由该不可观察的状态产生的可观察符号序列。隐马尔科夫模型形

4、式描绘如下：一个H模型是一个三元组=(A，S，Q)，其中A是字母表，S是有限状态集合，每个状态可以释放字母表中的字符。Q为概率集合，包括两个局部：一是状态转换概率fkl，k，lS，表示从状态k转化到状态l的概率；二是字符释放概率，记为ek(b)(kS，bA)，表示在状态k下释放出字符b的概率。令途径=(1，2，L)是模型的一个相继状态序列，X=x1，x2，xL是一个字符序列，按下述方式定义状态转换概率和字符释放概率：fkl=p(i=l|i-1=k)ek(b)=p(xi=b|i=k)对于给定的途径，可以按下面的公式计算出产生序列X的概率：PX|=f0，1ei(xi)fi，i+1这里，令0为起始状

5、态，i+1为终止状态。在表示或分析H模型时，用方框表示各个状态，方框之间的连线表示状态转换。对于每个状态，详细地描绘各个字符的释放概率，而对于状态之间的转换，也给出相应转换动作发生的概率，即状态转换概率。表示DNA序列的H如图1所示。对生物序列而言，H的字符就是20个字母的氨基酸或4个字母的核苷酸。编码蛋白质的原始DNA序列，在生物的进化过程中会受到自然环境和各种因素的影响，使翻译出的蛋白质序列4经历突变、遗失或引入外援序列等变化，最后按不同的进化途径分化，形成多种功能相近的蛋白质。因此，可以把这些蛋白质看作由一个根本蛋白质序列经过插入、删除或交换了某些氨基酸残基而形成。这个过程可以用H来表示

6、。一个训练好的模型可以代表有共同特征的蛋白质序列。H用于分析蛋白质序列的原理是分析蛋白质产生不同序列的概率，对于与模型相符合的序列，能以较大的概率产生。图1隐马尔科夫模型对于给定一个隐马尔科夫模型=(A，S，Q)和一个字符序列X即基因序列，在中寻找产生该序列的最优途径*，该途径从起始状态出发，完毕于终止状态，在途径中的每一个状态都选择释放一个字符，使P(X|*)最大。这是基因识别中常用的一个方法，这里我们设计采用并行算法来求解H的最优途径问题。给定一个字符序列X=x1，x2，xL，以vk(i)代表序列前缀x1，x2，xL终止于kkS，1iL的最可能途径的概率。求解过程如下：1初始化vbegin

7、0=1kbeginvk(0)=02对于每个i=0，1，L-1及每个lS，按下式进展递归计算vl(i+1)=el(xi+1)axvk(i)fklkS3最后，计算序列X终止于状态“end最可能的途径概率，即P(X|*)的值P(X|*)=axvk(L)fk，endkS在实现中我们将隐马尔科夫模型使用一颗状态空间树及一个字符释放概率矩阵结合表示。如图2所示。图2H的结合表示采用并行深度优先搜索技术，在每一个前向分支处启动一个新的进程，并行的计算多计算分支。在单PU的情况下，算法的时间复杂度为(L|S|2)，在具有N个计算节点的情况下，算法的时间复杂度为(L|S|2/N)。在理想的情况下，并行算法在理论

8、上的加速比与计算节点数成正比。在大型基因构造识别的问题域中，为实现并行计算而产生额外的启动、通信等时间与有效计算时间相比根本可以忽略，可近似到达理想加速比。中国科学院院士张春霆指出生物信息学是生物学的核心和灵魂，数学与计算机技术那么是它的根本工具。只有将并行计算研究和基因识别的理论研究有效联络起来，在研究蛋白质构造预测与分析的方法根底上，结合并行计算技术的特点，设计一系列的高效并行实现技术，实现高效、快速的基因识别，生物信息计算才能得到更快的开展。1EddySRPrfilehiddenarkvdelsBiinfratis，1998，14(9)：755-7632RihardD，EddySR，AndersKBilgialSequeneAnalysisBEijing：TsinghuaUniversi