隱馬爾可夫模型在生物學和醫學研究中的應用*

阿肯色醫科大學兒科系生物統計中心 美國阿肯色州小石城 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]?，F介紹隱馬爾可夫模型在生物學和醫學研究中的應用。

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)等研究的基礎?；蛟谑来g的傳遞是一個二維馬爾可夫過程，從世代的方向上，給定親本基因型，其子裔將獨立于其他祖先，因此是個一階馬爾可夫鏈；從染色體方向上，若線性排列的各位點間沒有重組干擾，則給定某位點的遺傳狀態(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 生物圖像分析 現代成像技術包括計算機斷層掃描成像、磁共振成像、超聲成像等，所產生的生物圖像是一類重要的生物學數據，計算機圖像分析是近年來生物學研究一個非?；钴S的熱點領域[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