隐马尔可夫模型在生物学和医学研究中的应用*

阿肯色医科大学儿科系生物统计中心 美国阿肯色州小石城 72202

隐马尔可夫模型在生物学和医学研究中的应用*

阿肯色医科大学儿科系生物统计中心 美国阿肯色州小石城 72202

隐马尔可夫模型；评价；解码；模型拟合；生物学应用

马尔可夫过程(Markov process)是具马尔可夫特性即无记忆性(memorylessness)又称无后效性(non-aftereffect)的随机过程，其未来状态的条件概率仅与系统的当前状态(或此前的少数若干个历史状态)有关，而独立于其他历史状态(或该序列其他变量的状态)，由俄国数学家Andrey Andreyevich Markov提出相关的统计理论而得名[1]。其中，随机过程通常是指以时间为参数的随机函数，但也可广义地视为一组随参数而变化的随机变量的有限或无限集合，如以空间为参数的随机函数；若参数为离散时又称随机序列。根据时间参数是否连续、状态空间是否可列等性质，马尔可夫过程有离散时间(discrete time)和连续时间(continuous time)、有限(finite)和不可列(infinite)、一阶(first-order，其条件概率仅依赖于系统的当前状态)和高阶(high-order，其条件概率依赖于此前多个状态)、时间齐次(time-homogeneous，有静态的转换频率函数，转换频率不依赖于当前状态所处的位置)和时间非齐次(time-nonhomogeneous)、一维(uni-dimensional)和高维(multi-dimensional)等之分。自然界和人类社会中，马尔可夫过程的存在相当普遍，例如随机漫步(random walk)、醉汉行走(drunkard's walk)、莱维飞行(Lévy flight)、布朗运动(Brownian motion)、原子核中自由电子在电子层中的跳跃等都是齐次的连续时间马尔可夫过程，传染病受感染的人数、人口增长过程等也可由马尔可夫过程来模拟。其中，参数为离散、状态空间可列的马尔可夫序列称为马尔可夫链(Markov chain)[2]。当马尔可夫链的状态不能被完全观测但可由受状态影响的某些观察变量推断时，称为隐马尔可夫过程，相应地，刻画其统计特征的概率模型称为隐马尔可夫模型(hidden Markov model)。常用的隐马尔可夫模型是一维的，其高维的扩展包括多维的隐马尔可夫模型或马氏网格随机场(Markov mesh random field)及更广义的马尔可夫随机场(Markov random field)，又称马尔可夫网络(Markov network)。隐马尔可夫模型在信号处理、文字识别、通信译码、图像分析、经济学、社会学、生命科学等领域有着广泛的应用[3-6]。现介绍隐马尔可夫模型在生物学和医学研究中的应用。

1 隐马尔可夫模型

隐马尔可夫过程是一个双重随机过程，其中基本的随机过程是马尔可夫过程，描述隐变量间状态转移的关系，另一个是观测过程，描述状态和观测结果间的统计关系[7]。因高阶马尔可夫过程可通过数据扩增还原成一阶马尔可夫过程[2]，下面以一阶马尔可夫过程为例加以介绍，有关的分析方法不难扩展至高阶的情形。常见的隐马尔可夫过程如图1所示。

A：一维隐马尔可夫过程；B：二维隐马尔可夫过程；C：隐马尔可夫场。图1 常见的隐马尔可夫过程

1.2 二维隐马尔可夫过程 二维隐马尔可夫过程的基本过程是一个由随机变量阵列构成的马尔可夫网格，每一随机变量Xi,j有Si,j个可能的状态，其条件概率满足无记忆性(即只依赖于紧邻的晶格点)，Pr(Xi,j│X0:i,0:j{Xi,j})=Pr(Xi,j│Xi-1,j,Xi,j-1)(i=1,2,…,I,j=1,2,…,J)，其中X0:i,0:j={Xu,v∀u=0,1,…,i;v=0,1,…,j}，Pr(Xi,j│Xi-1，j,Xi,j-1)是状态转移概率，记为│Xi-1,j=k,Xi,j-1=l)；

当i=0和j=0，有一组初始状态概率Pr(X0,0)，记为π=(πu)(u=1,2,…,S0,0)，其中πu=Pr(X0,0=u)。

1.3 隐马尔可夫场 隐马尔可夫模型可进一步拓展至更高维的情形[10-13]，包括更一般的隐马尔可夫随机场或马尔可夫网络[14-19]。隐马尔可夫随机场是一个夹杂了(条件)独立噪音的马尔可夫随机场，其基本变量是一组称为马尔可夫随机场或马尔可夫网的变量[20]。如图1C所示，每个节点是一个变量，节点间的边代表两变量间的依赖关系。若一个变量子集中的任何两个变量都有边相连，则称该子集为团(clique)，每个团由一组称为势函数(potential functions)的非负函数定义其概率分布。若在一个团中加入另外任何一个节点都不再形成团，则称该团为“极大团”。马尔可夫随机场变量集的联合分布可表示为基于团分解的多个势函数的乘积：

其中cl(X)表示该随机场的一组团，通常是一组极大团，ψc( )是团c的势函数，xc是团c的状态，标准化因子Z=∑xΠc∈cl(x)ψc(xc)。

隐马尔可夫随机场的基本变量不能被完全观测，但每个变量有可测的输出信号相联，给定一隐变量的状态，其对应的观测变量独立于其他变量。

2 隐马尔可夫模型的统计分析

一维隐马尔可夫模型主要运用网格算法，如图2所示，不同变量的各状态可依变量序列的位置排列成一个交织网格，网格的节点对应于某位置的某状态，网格图中的每个节点与前一变量的至少一个节点和(或)与后一变量的至少一个节点相接。应用条件独立性，每个节点可贮存与之有关的所有状态序列(即网格图中经该节点的路径)计算信息。在网格图基础上建立的前向-后向算法(the forward-backward algorithm)[21-22]、维特比算法(the Viterbi algorithm)[23-25]、鲍姆-韦尔奇(the Baum-Welch algorithm)或EM算法(expectation-maximization algorithm)[26-27]分别用于评估、识别、训练问题，现简述如下。

上：前向网格；下：维特比网格。图2 网格算法

2.1 前向-后向算法 一组观察序列(y0，y1，…，yI)的概率，记为Pr(y0，y1，…，yI│Ω)=∑x0，x1，…，xIPr(y0，y1，…，yI│x0，x1，…，xI；Ω),可由前向递推法或后向递推法计算，包括初始化、递推和终止等3个步骤。网格图中的每个节点分别有2个辅助变量贮存前向概率和后向概率，分别记为αi(u)和βi(u)(u=1,2,…,Si，i=0,1,…,I)，αi(u)表示从最始位置到达此状态的所有路径的概率之和，βi(u)表示从此状态出发到最终位置的所有路径的概率之和。

2.3 EM算法 给定一组或若干组观察序列，模型拟合可由EM算法实现。EM算法利用如下原理求解[28]：根据Kullback-Leibler散度理论[29]，完全数据(由隐变量数据与观测数据共同构成)似然函数对数的期望将是观测数据(即不完全数据)似然函数对数的下界(即完全数据似然函数在任意一组隐状态变量频率下的期望将小于或等于观测数据的似然函数)，因此可用完全数据似然函数对数的期望代替不完全数据似然函数对数作为目标函数，通过交替执行期望步和最大化步逐步逼近观测数据的似然函数，进而求得参数的最大似然估计子(maximum likelihood estimator, MLE)。其中期望步是指在给定观测数据下估算隐变量的后验概率分布并对完全数据似然函数对数求期望，最大化步是指根据完全数据似然函数对数的期望，求解最大化似然函数的模型参数，每一期望步和最大化步均将增加(或不减少)完全数据似然函数对数的期望值，从而收敛于一个局部最优解。当完全数据参数的MLE有简单易求的分析解时，EM算法将十分有效。EM算法包括初始化分布参数、一系列由期望步和最大化步构成的迭代及终止等步骤。

①初始化：设定一组初始参数值Ω(0)={π(0),A(0),B(0)}，启动迭代。

②迭代：每一迭代包括期望步和最大化步，两者交替进行，完成一次迭代。

期望步中，计算当前参数值Ω(t)={π(t),A(t),B(t)}和观测数据下的各组序列隐变量状态或状态组合的后验概率分布和完全数据似然函数对数的条件期望。具体地，如前向-后向算法中所述，计算每组序列(y0,y1，…，yI)的前向概率和后向概率，然后隐变量状态或状态组合的概率可由前向概率和后向概率求得：

执行期望步确保在当前参数估计值Ω(t)下完全数据似然函数对数的条件期望值最大化。接着，利用估计的隐变量数据条件期望，求含未知参数的完全数据似然函数对数的期望。

③终止：重复迭代至收敛条件满足，如目标函数不再增加或参数估计不再变化。

原理上，上述一维隐马尔可夫模型统计方法可推广至多维及马尔可夫场的情形，但实际上实现起来难度却非常大。最直接的解决方案是通过把多维空间的节点沿一定方向拓展成一个向量，以向量为新节点把多维模型转化为一维马尔可夫模型。例如，二维马尔可夫网格可沿着行、列、对角或反对角方向拓展成一个向量，得到以向量为“超节点”(supernode)的马尔科夫链[30-34]，三维网格也有类似的推广[35-37]。从而前述的前向-后向算法、维特比算法和EM算法等可用于新的一维模型的统计分析。这类方法的不足是算法的复杂度随向量维数的增加而呈指数增加。另一类方法是应用限制性统计模型减少节点间的连通性，从而降低模型复杂性，这类方法包括伪多维隐马尔可夫模型(pseudomulti-dimensionalHMMs)[38-39]、镶嵌隐马尔可夫模型(embeddedHMMs)[40-41]、依赖树隐马尔可夫模型(dependence-treeHMMs)[42]等，其主要缺点是改变了原有的依赖关系。另外，还有各种探试式(heuristic)近似算法通过简化求解假定减低算法复杂度[30, 32, 43-48]，其局限是理论上不能保证近似性。在隐马尔可夫场方面也有类似前向-后向算法的变量消去法(variableelimination)和信念传播法(beliefpropagation)[对应于前向-后向算法与维特比算法，又可进一步分为和积讯息传送(sum-productmessagepassing)与最大积讯息传送(max-productmessagepassing)]等[49]，用于精确推断。然而，对于多维隐马尔可夫模型和隐马尔可夫场，精确计算是非确定性多项式时间难题(nondeterministic,polynomialtime-hard，简记NP-hard)，迄今不相信存在针对一般情形的快速计算方法。多数情况下因运算量巨大，精确计算基本不可行。近似推理算法及数值计算技术如马尔可夫链蒙特卡洛(MarkovchainMonteCarlo)抽样方法[50]、变分推断法(variationalinference)[51]、循环信念传播法(loopybeliefpropagation)[52-53]等通常更可行。我们在美国国家基金的资助下，开发了伸缩型算法(telescopicalgorithm)，有望将呈指数增加的复杂度降低为线性增加的迭代算法，大大降低计算资源(包括内存和时间)的开销，适用于多维隐马尔可夫模型的精确计算。

3 隐马尔可夫模型在生物学和医学上的应用

隐马尔可夫模型是预测和特征识别的有效工具。自Churchill将其引入计算生物学[54]，该模型在生物学领域呈现出十分重要的研究价值和广阔的应用前景[55-56]，现概述其在如下几个方面的应用。

3.1 遗传作图 遗传作图(genetic mapping)包括连锁图谱构建(linkage map construction)和基因定位(gene mapping)，是指根据重组信息确定基因以及其他特征序列(如遗传标记)在基因组上相对位置的过程，是图位克隆(map-based cloning)、标记辅助选择(marker-assisted selection)和正向遗传学(forward genetics)等研究的基础。基因在世代间的传递是一个二维马尔可夫过程，从世代的方向上，给定亲本基因型，其子裔将独立于其他祖先，因此是个一阶马尔可夫链；从染色体方向上，若线性排列的各位点间没有重组干扰，则给定某位点的遗传状态(inheritance state)，即该位点的基因来自于祖父或祖母的信息，一边位点的遗传状态将独立于另一边位点的状态，因而也是个一阶马尔可夫链(若存在重组干扰，则是高阶马尔可夫过程)，因此，某个体在某位点(遗传标记或基因等)的遗传状态代表了二维马尔可夫网格上的一个节点。通常性状基因型、标记等位基因序位和遗传状态不能被直接观测，因此遗传因子的传递是个二维的隐马尔可夫过程。迄今的遗传作图主要应用Elston-Stewart算法[57-58]和Lander-Green算法[59]两大基本算法，以前者为基础开发的方法及软件有FASTLINK[60-62]和VITESSE[63]等，以后者为内核的有GENEHUNTER[64]、MERLIN[65]和ALLEGRO[66-67]等。但这两类方法都采用了把二维模型转化为一维模型的计算策略：Elston-Stewart算法把个体或婚姻联结视为一个超节点，利用世代方向的马尔可夫特性简化计算；Lander-Green算法把各位点视为超节点，利用染色体方向上的马尔可夫特性简化计算。两类算法都有局限。随考虑位点数的增加，Elston-Stewart算法中超节点的状态数呈指数式增加，计算机内存和计算时间开销随之也急剧增加，因而只能处理少数位点。随家系内非奠基者(non-founder)数目的增加，Lander-Green算法中超节点的状态数将指数增加，因而只能分析小家系。我们正在开发基于伸缩型算法作图方法，可望克服上述两类方法的不足。

3.2 生物序列数据分析 蛋白质和核酸分别是由氨基酸和核苷酸等单元组成的序列。各单元的线性排列(即一级结构)是高级结构和功能的基础，蕴含了其行使生物功能所需的丰富信息，通过序列分析可挖潜生物分子的结构、功能和进化信息。在生物进化过程中祖代序列受自然环境和其他因素的影响会发生突变、重组交换、插入/缺失等变化，在选择或遗传漂移等进化力作用下，按不同的途径演变成现存的序列。因某些生物学机制如三联体密码、二联核苷酸及功能序列的保守性，序列单元间会存在内在关联性，研究[68]也证实生物序列并非完全随机排列。Krogh等[69]发现蛋白质和DNA等序列数据可用隐马尔可夫模型表述，其中发生在各位置的替换、插入和删除等是不可观测的隐状态，各位置间状态变换具有马尔可夫特性，由一组转换频率决定状态变化的可能性，而测序数据是观测数据，受相应位置状态的一组生成概率控制。因此，隐马尔可夫模型是生物序列数据分析的有效工具，被广泛应用于单一序列的模式识别(pattern recognition)、序列比对、序列分类、相似性查询或同源性检测等[70-73]。

序列比对是指将两个或多个序列按照一定的规律排列，并标注其相似之处，用于检测序列之间的相似性或同源性。在比对中，错配与突变对应，而空位与插入或缺失对应，分别赋以不同的罚值，最终输出一个位置特异性计分表，称为轮廓或特征谱。序列比对是序列特征提取和模式分类的基础。序列比对有全局和局部比对、双序列和多序列比对之分。全局比对考虑整个序列的所有错配和空位，用于比较序列间整体关系上的密切程度，推测同源性；局部比对则识别匹配的子串序列，而忽略配对区域外的错配和空位，考察的是特定区段匹配程度，用于推断那些与功能域有关、进化上更保守的序列片段。多序列比对是双序列比对的推广，用于发现序列的共同特征和序列模式、定量估计序列间的关系、推断进化中的关系，原理上多序列比对与双序列比对相同，但算法复杂度随比对序列数增加而快速增加，通常由启发式、渐进式算法实现。常用的比对方法有以下几种。Needleman-Wunsch算法[74]是成对全局比对方法，Smith-Waterman算法[75]是成对局部比对方法，Feng-Doolittle算法[76]是渐进式多序列比对方法，特征谱分析法[77]是多序列特征谱构建和比较的工具。然而这些常规方法效果相当程度地依赖于取代矩阵(如蛋白质序列中的Dayhoff mutational distance matrix)和空位罚分的选择，带有一定的主观随意性。

为了弥补上述方法的不足，近年来隐马尔可夫原理被应用于序列比对。根据输入数据，应用学习算法训练模型参数如配对、插入、缺失间的转换频率及各状态的输出概率；基于拟合的模型，应用解码算法，找出单条序列的最优状态组合，完成比对。与常规的序列比对相比，隐马尔可夫模型有正规的概率作基础，对序列空位和插入状态评分、状态输出概率等有可靠的统计理论依据[78]。一组由共同祖先进化而来的序列通过比对构建特征谱后，隐马尔可夫模型可用于提取共同区段、建立搜索数据库、查找序列家族、查询新序列，也可根据相似性对未知序列进行分类，推断进化关系，构建进化树。

3.3 基因发现和序列模式鉴别 基因识别就是从测序得到的DNA序列中识别其中的编码区或基因，这项工作也称为基因组注释(genomic annotation)[79-82]。有两类方法可用于基因识别。一类是完全依赖序列数据的全始方法(ab initio method)，即通过探索DNA序列中特异的区域寻找基因。一个基因包括启动子、起始密码子、外显子、内含子、终止密码子及两端的不翻译区域等结构，其中存在某些特征序列如内含子的供体(GT二联核苷酸)和接受器(AG二联核苷酸)等。如果将给定的一段基因组DNA视为观察序列，而将基因结构看作不能直接观测的隐状态，那么基因预测与自然语言识别十分相似，是一个隐马尔可夫过程，基因识别就是根据观测序列预测隐状态最佳序列，属隐马尔可夫模型的解码问题。隐马尔科夫模型用来预测基因的具体步骤如下。首先，用一组已注释过的DNA序列集训练模型，然后根据拟合的模型，对一个未知的基因组序列反推出最可能的状态路径。类似的思路也适用于序列模式、功能位点和特征信号的鉴别如CpG岛、开放读码框、转录因子结合位点、顺式调控模块、非编码RNA等的预测[83]。另一类基因识别方法是基于同源性方法或称比较基因组学法发现新基因，根据与已知的蛋白质或基因序列比对的结果进行基因预测、推断基因功能，该法也可用于鉴定调控基因、检测开放读码框、探索垃圾基因等。

3.4 分子结构预测 序列单元的排列次序是生物分子的一级结构，其更高级结构与其功能密切相关，如双链DNA的双螺旋和超螺旋立体形状、蛋白质的螺旋与折叠及转角、二级结构元素在三维空间的排列及不同亚基间的复合等。隐马尔可夫模型也可用于分子结构预测，即由一级结构推断其高级结构等[84-86]。本质上这是一个模式识别问题，隐马尔可夫模型能提供有效的解决方案。其思路是把高级结构分成若干个隐状态如蛋白质螺旋、折叠、转角等，通过对已知高级结构数据进行统计分析，建立序列与高级结构之间关系的最佳模型，进而来预测目标序列的高级结构。

3.5 生物图像分析 现代成像技术包括计算机断层扫描成像、磁共振成像、超声成像等，所产生的生物图像是一类重要的生物学数据，计算机图像分析是近年来生物学研究一个非常活跃的热点领域[87-88]。图像的像素间常存在时空依赖性[89]，同一张图像像素间会有空间相关，不同时间点的图像像素间会有时间相关。多维隐马尔可夫模型或隐马尔可夫随机场能可靠地描绘这些内在相关结构和随机噪声过程，作为改进的方法被广泛地应用于图像分割、图像去噪、图像检索、图像分类、图形识别等分析中[20,52,90-91]。其原理是将各个图像像素特征，通常是矢量量化(由若干个标量整体量化像素的特征如色彩、亮度、纹理、形状等)的像素，视作服从一定概率分布的随机变量，用马尔可夫网格模型描述像素的空间结构关系和条件独立性，从而有效地描述图像的性质，进而对图像数据进行拟合。其步骤包括收集训练数据(即大量的图像系列)，提取像素特征(如灰度值、几何形状、纹理单元排列等信息)作为观测序列，定义隐马尔可夫网格模型结构，通过学习算法来优化模型参数，用优化模型对未知图像序列进行图像分割提取、分类识别或者抽象化并找出其本质的内容，进行图像数据库检索、查找。

3.6 流行病学预测 传染病蔓延、慢性病发病等是多状态、多阶段的进程。病源菌在个体间传播和体内的扩散有时序相关性，将来的疫情或病情与现在有关，不依赖于过去。许多情况下，如疾病的状态等不能确诊或没有调查。病源菌传播也具有空间相关性，疾病地理分布也呈一定的空间结构。因此可用隐马尔可夫模型来模拟传染病动力学和慢性病发展过程及地理分布，进行流行病学分析、预报和监控[92-95]。主要步骤是：收集病情、疫情和流行病学资料，划分若干个状态如流行与非流行、健康与疾病分级状态，或动态分派状态数目，建立隐马尔可夫模型，优化模型参数，然后对特定的病情、疫情进行预测或绘制灾情区域分布图。并且，可进一步地把流行病学因素导入马尔可夫模型，如建立对转换状态频率影响模型等，改进预测准确性和评估风险因子。

3.7 进化树构建 与基因在世代间传递类似，分子进化也是双重马尔可夫过程的组合：一方面，发生在基因组空间维度上不同位点的进化事件如序列单元的取代和重组交换等是马尔可夫过程；另一方面，发生在进化历史时间维度上各进化树分叉点的事件也是马尔可夫过程[96]。相较于传统的忽略位点间相依关系的进化树模型，进化树隐马尔可夫模型可更为精准地表达进化上的真实关系，因而构建的进化树更为精确[97-98]。这类模型也用于抗原决定基的发现等研究中[99]。此外，隐马尔可夫模型也被用于处理进化和比较基因组研究中的不确定性和数据的不完整性[100]和位点进化率的异质性[101]等。

3.8 文本挖掘 飞速增长的医学文献和临床资料为循证医学提供了大量素材，如何有效驾驭和处理海量文本信息也成了重要课题，开发有效的文本挖掘方法可大大提高工作效率[102]。隐马尔可夫模型是进行文本信息提取和分类的强有力工具[103-104]。其基本思路是科研论文和病例档案包含若干语义标签或抽取域(如症状、论文标题域、作者域等)，其内容是要抽取的语义项，信息提取首先需确定抽取域，然后再提取相应的语义项，这一过程与隐马尔可夫模型相吻合，各抽取域对应于模型的隐状态序列，而语义项则对应于各状态的观测。具体实现包括建立隐马尔可夫模型和选择适当的结构，对论文和医学资料的语义项作分解，将大量已知的语义项作为观测序列进行模型学习，利用学习好的模型对未知观测序列执行解码运算，找出最优状态序列，即寻找语义项相关的抽取域，并提取语义项信息，进而完成文本挖掘任务。

4 展望

生物体是由无数代谢网络和调控网络等组成的多层次、模块化错综庞杂的系统，长期进化过程中功能上的关联及随机事件进一步造就了充满复杂性和不确定性的复杂进化关系，解析这些复杂联系、破译生命的奥秘是当今生物学研究面临的艰巨挑战。现代生物技术为生物学研究提供了潜在可靠的实验手段，为剖析不同层次网络模块结构、追踪历史事件等创造了可能，但对这些数据的提炼和知识的综合，有赖于系统生物学、计算生物学、生物信息学等分析工具。隐马尔可夫模型既能反映变量随机性，又能反映变量间潜在结构，对内在联系和随机信号有较强的建模能力，不仅能灵活处理时间、空间关联性，同时又能容忍知识域中存在的不完整性和矛盾性，因此是十分有效的生物建模和生物计算工具。近年来，隐马尔可夫模型在复杂生物学问题求解如基因代谢网络分析和多组学数据的有机整合[105-106]中有深入的应用。相信已经初试身手的隐马尔可夫模型必将在生物学机制的研究中大有用武之地。

[1]SHANNON CE.A mathematical theory of communication[J].Bell Labs Technical Journal,1948,27(3):379

[2]BILLINGSLEY P.Statistical methods in Markov chains[J].Annals of Mathematical Statistics,1961,32(1):12

[3]BHARUCHA-REID AT.Elements of the theory of Markov processes and their applications[M].New York/Toronto/London:McGraw-Hill,1960.

[4]VIDYASAGAR M.Hidden Markov Processes:theory and applications to biology[M].Princeton:Princeton University Press,2014.

[5]DYMARSKI P.Hidden Markov models, theory and applications[M].Rijeka:InTech Press,2011.

[6]CHING WK,MK MG.Markov chains: models, algorithms and applications[M].2nd ed.New York:Springer,2013.

[7]RABINER L,JUANG B.An introduction to hidden Markov models[J].IEEE ASSP Magazine,1986,3(1):4

[8]WOODS J.Two-dimensional discrete Markovian fields[J].IEEE Transactions on Information Theory,1972,18(2):232

[9]FORNASINI E.2D Markov chains[J].Linear Algebra and Its Applications,1990,140(1):101

[10]POLITIS DN.Markov-Chains in many dimensions[J].Adv Appl Probab,1994,26(3):756

[11]DERIN H,KELLY PA.Discrete-index Markov-type random processes[J].Proceedings of the IEEE,1989,77(10):1485

[12]ABEND K,HARLEY T,KANAL L.Classification of binary random patterns[J].IEEE Transactions on Information Theory,1965,11(4):538

[13]GRAY AJ,KAY JW,TITTERINGTON DM.An empirical study of the simulation of various models used for images[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,1994,16(5):507

[15]KINDERMANNR，SNELLJL．Markov random fields and their applications[J].American Mathematical Society,1980,1(3):415

[16]SHAKYA S,SANTANA R.Markov networks in evolutionary computation[M].Berlin/Heidelberg:Springer,2012.

[17]SMYTH P.Belief networks,hidden Markov models,and Markov random fields: a unifying view[J].Pattern Recognition Letters,1997,18(11/13):1261

[18]JORDAN MI.Graphical models[J].Statistical Science,2004,19(1):140

[19]KUNSCH H,GEMAN S,KEHAGIAS A.Hidden Markov random fields[J]. Annals of Applied Probability,1995,5(3):577

[20]ZHANG Y,Brady M,SMITH S.Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximization algorithm[J].IEEE Trans Med Imaging,2001,20(1):45

[22]RABINER LR.A tutorial on hidden Markov models and selected applications in speech recognition[J].Proceedings of the IEEE,1989,77(2):257

[23]VITERBI A.Error bounds for convolutional codes and an asymptotically optimum decoding algorithm[J].IEEE Transactions on Information Theory,1967,13(2):260

[24]VITERBI AJ.A personal history of the Viterbi algorithm[J].IEEE Signal Processing Magazine,2006,23(4):120

[25]FORNEY GDJ.Theviterbi algorithm[J].Proceedings of the IEEE,1973,61(5):268

[26]BAUM LE,PETRIE T.Statistical inference for probabilistic functions of finite state Markov chains[J].Annals of Mathematical Statistics,1966,37(6):1554

[27]BAUM LE,PETRIE T,SOULES G,et al.A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains[J].Annals of Mathematical Statistics,1970,41(1):164

[28]DEMPSTER AP,LAIRD NM,RUBIN DB.Maximum likelihood from incomplete data via the EM algorithm[J].Elearn,1977,39(1):1

[29]KULLBACK S,LEIBLER RA.On information and sufficiency[J].Annals of Mathematical Statistics,1951,22(1):79

[30]LI J,NAJMI A,GRAY RM.Image classification by a two-dimensional hidden Markov model[J].IEEE Transactions on Signal Processing,2000,48(2):517

[31]LI YJ.An analytic solution for estimating two-dimensional hidden Markov models[J].Appl Math Comput,2007,185(2):810

[32]KANAL LN,GELSEMA ES.Pattern recognition in practice Ⅱ[M].Amsterdam:Elsevier,1986.

[33]DU S,WANG J,WEI Y.New learning algorithms for third-order 2-D hidden Markov models[J].International Journal of Advancements in Computing Technology,2011,3(2):104

[34]XIANG M,SCHONFEID D,KHOKHAR A.A general two-dimensional hidden Markov model and its application in image classification[J].IEEE International Conference on Image Processing,2007,6(3):Ⅵ

[35]QIAN W,TITTERINGTON DM.Pixel labelling for three-dimensional scenes based on Markov mesh models[J].Signal Processing,1991,22(3):313

[36]JOSHI D,LI J,WANG JZ.A computationally efficient approach to the estimation of two-and three-dimensional hidden Markov models[J].IEEE Transactions on Image Processing,2006,15(7):1871

[37]LI J，JOSHI D，WANG JZ．Stochastic modeling of volume images with a 3-D hidden Markov model:4 volume[C].International Conference on Image Processing,2004．IEEE，2004: 2359

[38]WERNER S,Rigoll G．Pseudo 2-dimensionalhidden Markovmodelsinspeechrecognition[C].IEEE Workshop on Automatic Speech Recognition and Understanding，2001．IEEE, 2001: 441

[39]LIN HC,WANG LL,YANG SN.Color image retrieval based on hidden Markov models[J].IEEE Transactions on Image Processing,1997,6(2):332

[40]KUO SS,AGAZZI OE.Keyword spotting in poorly printed documents using pseudo 2-D hidden Markov models[J].IEEE Transaction Pattern Analysis and Machine Intelligence,1994,16(8):842

[41]NEFIAN AV,HAYES Ⅲ MH.Face recognition using embedded hidden Markov model[C].IEEE Conference on Audio and Video-based Biometric Person Authentication.IEEE,1999:19

[42]MERIALDO BJ,JITEN J,HUET B.Multi-dimensional dependency-tree hidden Markov models[C].International Conference on Acoustics, Speech, and Signal Processing.IEEE,2006:773

[43]BAUMGARTNER J, FLESIA AG, GIMENEZ J，et al．A new approach to image segmentation with two-dimensional hidden Markov models[C].2013 BRICS Congress on Computational Intelligence & 11th Brazilian Congress on Computational Intelligence.IEEE,2013：213

[44]EMENTHON D，DOERMANN D，STUCKELBERG MV，Image distance using hidden Markov models:3 volume[C].The 15th Int．Conf．on Pattern Recognition, 2000．IEEE,2000:143

[45]SARGIN ME, ALTINOK A, ROSE K，et al. Conditional iterative decoding of two dimensional hidden Markov models[C].The 15th IEEE International Conference on Image Processing, 2008．IEEE,2008:2252

[46]MERIALDOB，MARCHAND-MAILLE S，HUETB．Approximate Viterbi decoding for 2-D hidden Markov models: 6 volume[C].IEEE International Conference on Acoustics，Speech，and Signal Processing，2000．IEEE,2000:2147

[47]PERRONNIN F，DUGELAY JL，ROSE K.Deformable face mapping for person identification[C].International Conference on Image Processing ICIP2003．IEEE，2003:661

[48]BAGGENSTOSS PM.Two-dimensional hidden Markov model for classification of continuous-valued noisy vector fields[J].IEEE Transaction Aerospace and Electronic System,2011,47(2):1073

[49]KOLLER D,FRIEDMAN N.Probabilistic graphical models:principles and techniques[M].Cambridge:MIT Press,2009.

[50]BROOKS S.Markov chain Monte Carlo method and its application[J].Journal of the Royal Statistical Society Series D:the statistician,1998,47(1):69

[51]JORDAN MI,GHAHRAMANI Z,JAAKKOLA TS,et al.An introduction to variational methods for graphical models[J].Mach Learn,1999,37(2):183

[52]BLAKE A,KOHLI P,ROTHER C.Markov random fields for vision and image processing[M].Cambridge:MIT Press,2011.

[53]WANG C,PARAGIOS N.Markov random fields in vision perception: a survey[M].Rapport de recherché,2012.

[54]CHURCHILL GA.Stochastic models for heterogeneous DNA sequences[J].Bull Math Biol,1989,51(1):79

[55]CHOO KH,TONG JC,ZHANG L.Recent applications of hidden Markov models in computational biology[J].Genomics Proteomics Bioinformatics,2004,2(2):84

[56]KOSKI T.Hidden Markov models for bioinformatics[M].Dordrecht:Kluwer Academic Publishers,2001.

[57]ELSTON RC,STEWART J.A general model for the genetic analysis of pedigree data[J].Hum Hered,1971,21(6):523

[58]CANNINGS C,THOMPSON EA,SKOLNICK MH.Probability functions on complex pedigrees[J].Advances in Applied Probability,1978,10(1):26

[59]LANDER ES,GREEN P.Construction of multilocus genetic linkage maps in humans[J].Proc Natl Acad Sci USA,1987,84(8):2363

[60]COTTINGHAM RW JR,IDURY RM,SCH-FFER AA.Faster sequential genetic linkage computations[J].Am J Hum Genet,1993,53(1):252

[63]O'CONNELL JR,WEEKS DE.The VITESSE algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance[J].Nat Genet,1995,11(4):402

[64]KRUGLYAK L,DALY MJ,REEVE-DALY MP,et al.Parametric and nonparametric linkage analysis: a unified multipoint approach[J].Am J Hum Genet,1996,58(6):1347

[65]ABECASIS GR,CHERNY SS,COOKSON WO,et al.Merlin:rapid analysis of dense genetic maps using sparse gene flow trees[J].Nat Genet,2002,30(1):97

[66]GUDBJARTSSON DF,THORVALDSSON T,KONG A,et al.Allegro version 2[J].Nat Genet,2005,37(10):1015

[67]GUDBJARTSSON DF,JONASSON K,FRIGGE ML,et al.Allegro, a new computer program for multipoint linkage analysis[J].Nat Genet,2000,25(1):12

[68]GENTLEMAN JF,MULLIN RC.The distribution of the frequency of occurrence of nucleotide subsequences, based on their overlap capability[J].Biometrics,1989,45(1):35

[69]KROGH A,BROWN M,MIAN IS,et al.Hidden Markov models in computational biology:applications to protein modeling[J].J Mol Biol,1994,235(5):1501

[70]KARLIN S,GHANDOUR G,OST F,et al.New approaches for computer analysis of nucleic acid sequences[J].Proc Natl Acad Sci USA,1983,80(18):5660

[71]HUGHEY R,KROGH A.Hidden Markov models for sequence analysis: extension and analysis of the basic method[J].Comput Appl Biosci,1996,12(2):95

[72]YOON BJ.Hidden Markov models and their applications in biological sequence analysis[J].Curr Genomics,2009,10(6):402

[73]EDDY SR.Hidden Markov models[J].Curr Opin Struct Biol,1996,6(3):361

[74]NEEDLEMAN SB,WUNSCH CD.A general method applicable to the search for similarities in the amino acid sequence of two proteins[J].J Mol Biol,1970,48(3):443

[75]SMITH TF,WATERMAN MS.Identification of common molecular subsequences[J].J Mol Biol,1981,147(1):195

[76]FENG DF,DOOLITTLE RF.Progressive sequence alignment as a prerequisite to correct phylogenetic trees[J].J Mol Evol,1987,25(4):351

[77]GRIBSKOV M,MCLACHLAN AD,EISENBERG D.Profile analysis:detection of distantly related proteins[J].Proc Natl Acad Sci USA,1987,84(13):4355

[78]HE M,PETOUKHOV S.Mathematics of bioinformatics:theory,methods and applications[M].[s.l]:Wiley-Interscience,2010:15

[79]KROGH A,MIAN IS,HAUSSLER D.A hidden Markov model that finds genes in E.coli DNA[J].Nucleic Acids Res,1994,22(22):4768

[80]LUKASHIN AV,BORODOVSKY M.Gene.hmm:new solutions for gene finding[J].Nucleic Acids Res,1998,26(4):1107

[81]BURGE C,KARLIN S.Prediction of complete gene structures in human genomic DNA[J].J Mol Biol,1997,268(1):78

[82]PEDERSEN JS,HEIN J.Gene finding with a hidden Markov model of genome structure and evolution[J].Bioinformatics,2003,19(2):219

[83]BANG H,ZHOU XK,VAN EPPS HL,et al.Statistical methods in molecular biology[M].Clifton:Humana Press,2010.

[84]CHURCHILL GA.Hidden Markov chains and the analysis of genome structure[J].Computers and Chemistry,1992,16(2):107

[85]GOLDMAN NTHORNE JL,JONES DT.Using evolutionary trees in protein secondary structure prediction and other comparative sequence analyses[J].J Mol Biol,1996,263(2):196

[86]WON JK,HAMELRYCK T,PR-GELBENNETT A,et al.An evolutionary method for learning HMM structure:prediction of protein secondary structure[J].BMC Bioinformatics,2007,8(1):357

[87]ROEDER AH,CUNHA A,BURL MC,et al.A computational image analysis glossary for biologists[J].Development,2012,139(17):3071

[88]RITTSCHER J.Characterization of biological processes th-rough automated image analysis[J].Annu Rev Biomed Eng,2010,12:315

[89]WANG Y,RESNICK SM,DAVATZIKOS C,et al.Analysis of spatio-temporal brain imaging patterns by Hidden Markov models and serial MRI images[J].Hum Brain Mapp,2014,35(9):4777

[90]LI SZ.Markov randomfield modeling in computer vision[M].Tokyo:Springer,2012.

[91]LI J,GRAY RM.Image segmentation and compression using hidden Markov models[M].New York:Springer,2000.

[92]LE STRAT Y,CARRAT F.Monitoring epidemiologic surveillance data using hidden Markov models[J].Stat Med,1999,18(24):3463

[93]COOPER B,LIPSITCH M.The analysis of hospital infection data using hidden Markov models[J].Biostatistics,2004,5(2):223

[94]WATKINS RE,EAGLESON S,VEENENDAAL B,et al.Disease surveillance using a hidden Markov model[J] BMC Med Inform Decis Mak,2009,9(1):39

[95]GREEN PJ,RICHARDSON S.Hidden Markov models and disease mapping[J].J Am Stat Assoc,2002,97(460):1055

[96]NIELSEN R.Statistical methods in molecular evolution[M].New York:Springer,2010.

[97]SIEPEL A,HAUSSLER D.Combining phylogenetic and hidden Markov models in biosequence analysis[J].J Comput Biol,2004,11(2/3):413

[98]HUSMEIER D.Discriminating between rate heterogeneity and interspecific recombination in DNA sequence alignments with phylogenetic factorial hidden Markov models[J].Bioinformatics,2005,21(suppl 2):ii166

[99]LACERDA M,SCHEFFLER K,SEOIGHE C.Epitope discovery with phylogenetic hidden Markov models[J].Mol Biol Evol,2010,27(5):1212

[100]BYKOVA NA, FAVOROV AV, MIRONOV AA.Hidden Markov models for evolution and comparative genomics analysis[J].PLoS One,2013,8(6):e65012

[101]FELSENSTEIN J,CHURCHILL GA.A Hidden Markov Model approach to variation among sites in rate of evolution[J].Mol Biol Evol,1996,13(1):93

[102]AGGARWAL C,ZHAI CX.Mining text data[M].New York:Springer,2012.

[103]JANG H,SONG SK,MYAENG SH.Text mining for medical documents using a Hidden markov model[C]//NG HT,LEONG MK,KAN MY, et al.Editors Information Retrieval Technology:AIRS 2006.Berlin/Heidelberg:Springer,2006:553

[104]YI K,BEHESHTI J.A hidden Markov model-based text classification of medical documents[J].Journal of Information Science,2009,35(1):67

[105]WEI P,PAN W.Network-based genomic discovery: application and comparison of Markov random field models[J].J R Stat Soc Ser C Appl Stat,2010,59(1):105

[106]RIDER AK,CHAWLA NV,EMRICH SJ.A survey of currentintegrative network algorithms for systems biology[M]//.Systems biology:integrative biology and simulation tools.Dordrecht:Springer,2013:479

(2017-01-23收稿 责任编辑王 曼)

特约述评作者简介

楼向阳(1967-)，男，浙江东阳人，博士，美国阿肯色医科大学副教授。1997年获浙江大学农生学院作物遗传育种专业统计遗传研究方向博士学位。2002年赴美国留学深造，相继在佛罗里达大学(University of Florida)统计系、德克萨斯大学圣安东尼奥医学中心(University of Texas Health Science Center)精神病学系、弗吉尼亚大学(University of Virginia)精神病医学与神经行为科学系任博士后研究员。2006年在美国弗吉尼亚大学(University of Virginia)晋升为助理教授，2009年在美国阿拉巴马大学伯明翰分校(University of Alabama at Birmingham)晋升为副教授，2015年任职杜兰大学(Tulane University)副教授，2016年在阿肯色医科大学(University of Arkansas for Medical Sciences)任职。在《Journal of the American Statistical Association》《American Journal of Human Genetics》《Proceedings of the National Academy of Sciences of the United States of America》《Human Molecular Genetics》《Molecular Psychiatry》《Biological Psychiatry》《Genetics》《Heredity》《Human Genetics》等期刊上发表学术论文70余篇。2006年获浙江省科学技术奖一等奖1项。主持美国国家科学基金(NSF)、美国国立卫生研究院(NIH)R01基金等国际级项目及中国国家自然科学基金项目等多项课题的研究。担任美国国家科学基金评委、美国国立卫生研究院基金评委，多家国际学术杂志的副主编和编委。

10.13705/j.issn.1671-6825.2017.03.001

*美国国家科学基金项目 DMS1462990