一种针对基因识别的GHMM简化算法.pdf

《一种针对基因识别的GHMM简化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、国防科技大学学报第26卷第4期JOURNALOFNATIONALUNIVERSITYOFDEFENSETECHNOLOGYVoI.26No.42004文章编号：1001-248（62004）04-0103-04!一种针对基因识别的GHMM简化算法李冬冬，杜耀华，王正志（国防科技大学机电工程与自动化学院，湖南长沙410073）摘要：广义隐Markov模型是计算机基因识别的一种重要模型，它克服了传统隐Markov模型的状态段长成几何分布的缺陷，更加适合于计算机基因识别。其缺点在于计算量大，需要采用有效的简化算法

2、。利用基因的结构特点，在不附加额外限制条件的情况下，提出了一种新的简化算法，其计算复杂度是序列长度的线性函数。对实际生物序列数据的测试结果表明了此简化算法的有效性。关键词：广义隐Markov模型；Viterbi算法；基因识别中图分类号：@61文献标识码：AASimplifiedAlgorithmtoGHMMforGeneFindingLIDong-dong，DUYao-hua，WANGZheng-zhi（CoIIegeofMechatronicsEngineeringandAutomation，Nation

3、aIUniv.ofDefenseTechnoIogy，Changsha410073，China）Abstract：ThegeneraIizedhiddenMarkovmodeI（GHMM）isanimportantmodeIforcomputationaIgenefinding.ComparedwiththetraditionaIhiddenMarkovmodeI（HMM），GHMMneedn’ttheassumptionthattheIengthofeachstateisgeometricaIdistri

4、bution，whiIeitisnecessaryforHMM.ThispropertyisappropriateforcomputationaIgenefinding.ThedemeritofGHMMisitshighcomputationaIcompIexity，whichhindersitfrombeingusedpracticaIIy.Accordingtothecharacteristicofgene’sstructure，anoveIsimpIifiedaIgorithmisproposedwi

5、thoutanyadditionaIassumptions，anditscomputationaIcompIexityisIinearwiththeIengthofseguence.ThetestingresuItforbioIogicaIdatademonstratesthatthesimpIifiedaIgorithmiseffective.Keywords：generaIizedhiddenMarkovmodeI；ViterbiaIgorithm；genefinding隐Markov模型（Hidden

6、MarkovModeI，HMM）最早应用在语音识别中，并获得了极大的成功［1，2］。对生物序列（DNA序列、蛋白质序列）而言，由于它与语音信号具有明显的相似性，因此，近年来，人们也开始把HMM用于生物序列的分析，包括序列比对、蛋白质二级结构预测、基因预测等等，并取得了一定的成功［3］。但是HMM的状态的段长成几何分布，这就限制了它的应用范围。比如对原核生物，其基因编码区的段长分布近似于伽玛分布，而非编码区则是近似于指数分布［4］。为此，人们提出了广义隐Markov模型（GeneraIizedHiddenMa

7、rkovModeI，GHMM），其最大的特点在于状态段长可以是任意分布，从而克服了HMM中状态段长成几何分布的缺陷，使模型能够更好地贴近实际的系统。GHMM的优点使得它被广泛用于基因识别［6，7］，并且获得了较高的准确率。事实上，迄今为止，基因识别准确率最高的几种软件都是采用的这一模型［4~8］。然而，这一推广的代价是计算量的增加，以至于不能直接在实际的基因识别中应用，而必须使用简化算法。本文根据基因的结构特点，提出了一种新的简化算法，在不添加额外条件的情况下，获得了与序列长度成线性关系的计算复杂度，对实际

8、生物序列数据的测试表明，此算法是有效的。1模型描述计算机基因识别的任务是对一个给定的DNA序列，指出其中基因的位置及其完整结构。在HMM模型的框架中，这一问题可以形式化地描述如下［4，5］：!收稿日期：2004-03-15基金项目：军队基础研究项目（JC-02-03-021）作者简介：李冬冬（1974—），男，博士生。104国防科技大学学报2004年第4期对一个长度为L的DNA序列!，定义它的一个状态分解!，它由