广义隐Markov模型在基因识别中的应用

Application of Generalized Hidden Markov Model in Gene Finding

广义隐Markov模型(GHMM)是基因识别的一种重要模型,但是其计算量比传统的隐Markov模型大得多,以至于不能直 接在基因识别中使用。根据原核生物基因的结构特点,提出了一种高效的简化算法,其计算量是序列长度的线性函数。在此 基础上,构建了针对原核生物基因的识别程序GeneMiner,对实际数据的测试表明,此算法是有效的。

Generalized Hidden Markov Model (CHMM) is an important model for gene finding. Differ to traditionary hidden Markov model, the length of consecutive runs of CHMM' s state is variable, and abbey a special length distribution. But the computation of CHMM algorithm is too large to be used without being simplified. According to the characteristic of gene' s structure, a new approach is proved to reduce the computational complexity of the algorithm. Then, a gene finding program called CeneMiner for prokaryote gene is realized.The application to real data shows that the algorithm is effective.