基于 HMM 的基因识别并行计算
摘 要 分析 了传统的串行基因分析 方法 的局限性，阐述了基于隐马尔科夫模型的基因
识别方法和原理，最后给出了基于隐马尔科夫模型的并行算法并进行了并行效果分析，指
出了并行 计算 在生物信息学领域的广阔前景及重要意义。 关键词 基因识别； HMM；
并行计算； 生物信息学 1 引言 20 世纪 90 年代以来，伴随着各种基因组测序计划的展
开和分子结构测定技术的突破，数以百计的生物学数据库如雨后春笋般迅速出现和成长。
如何利用这些不断爆炸性增长的有关生物分子的原始数据，有效解决基因识别 问题 显得
越来越迫切。最初的基因分析方法是进行简单的核苷酸统计，而后加上剪切保守位点的检
测。以后采用了人工神经 网络 、隐马尔科夫模型（HMM）[1，2]等先进的信息处理和分
析技术，提高基因识别的准确率。但由于生物信息数据量巨大，传统的串行算法往往无法
处理或难以在满意的时间内得到结果。本文针对基因序列的识别，讨论隐马尔科夫模型分
析算法的并行算法设计和并行效果分析。2 隐马尔科夫模型法 隐马尔科夫模型[3]（
Hidden Markov Models，HMM）是一种概率论模型，这种方法已经成功 应用 于多个领域
，如语音识别、光学字符识别等。HMM 在生物信息学领域中也有着重要的应用，如序列
分析、基因识别等。 目前 ，基因识别的 HMM 方法也大致可以分为两类，一类为按照 内
容 搜索的方法，通过核苷酸和三联密码子等在编码区的分布 规律 来界定蛋白质的编码区
；另一类为按照信号搜索的方法，通过编码区周围的信号界定蛋白质编码区。 马尔科
夫链 考虑只取有限个或可数个状态的随机过程{Xn，n=0，1，2，…}，假设对一切状态
i0，i1，…，in-1，i，j 和一切 n≥0，有 P{Xn+1=j | Xn=i，Xn-1=in-1，…，X1=i1，X0=i0}
= P{Xn+1=j | Xn=i}成立，则称此随机过程为离散状态马尔科夫链。简单的说，就是系统未
来的状态仅依赖于当前状态。一个马尔科夫链的概率分布完全由它的初始分布 P(X0)与转
移矩阵 P=(pij)决定。 HMM 基本原理 隐马尔科夫模型 HMM 是由马尔科夫链 发展 扩
充而来的一种随机模型。HMM 可以被理解为一个双重随机过程，一个是不可观察的（隐
含的）状态变化序列，另一个是由该不可观察的状态产生的可观察符号序列。隐马尔科夫
模型形式描述如下：一个 HMM 模型是一个三元组 M=(A，S，Q)，其中 A 是字母表，S 是
有限状态集合，每个状态可以释放字母表中的字符。Q 为概率集合，包括两个部分：一是
状态转换概率 fkl，k，l∈S，表示从状态 k 转化到状态 l 的概率；二是字符释放概率，记为
ek(b) (k∈S，b∈A)，表示在状态 k 下释放出字符 b 的概率。令路径 Π=(π1，π2，…，πL )
是模型 M 的一个相继状态序列，X=（x1，x2，…，xL）是一个字符序列，按下述方式定
义状态转换概率和字符释放概率：fkl = p(πi = l|πi-1 = k)ek(b) = p(xi=b|πi= k) 对于给定
的路径 Π，可以按下面的公式计算出产生序列 X 的概率： P（X|Π）= fπ0，π1 eπi (xi)fπi
，πi+1 这里，令 π0 为起始状态，πi+1 为终止状态。 在表示或分析 HMM 模型时，用
方框表示各个状态，方框之间的连线表示状态转换。对于每个状态，详细地描述各个字符
的释放概率，而对于状态之间的转换，也给出相应转换动作发生的概率，即状态转换概率
。表示 DNA 序列的 HMM 如图 1 所示。 对生物序列而言，HMM 的字符就是 20 个字母
的氨基酸或 4 个字母的核苷酸。编码蛋白质的原始 DNA 序列，在生物的进化过程中会受
到 自然 环境和各种因素的 影响 ，使翻译出的蛋白质序列[4]经历突变、遗失或引入外援
序列等变化，最后按不同的进化路径分化，形成多种功能相近的蛋白质。因此，可以把这
些蛋白质看作由一个基本蛋白质序列经过插入、删除或替换了某些氨基酸残基而形成。这
个过程可以用 HMM 来表示。一个训练好的模型可以代表有共同特征的蛋白质序列。HMM
用于分析蛋白质序列的原理是分析蛋白质产
图 2 HMM 的联合表
