Application of a Hidden Markov Model and Dynamic Programming for Gene Recognition in DNAs of Bacteria and Viruses

摘要

Statistically significant differences in the occurrence frequencies of nucleotides in DNA regions coding and noncoding the protein have been the subject of intensive study [1-3] and are used in gene recognition algorithms [4-7]. The maximum prediction accuracy has been achieved by the algorithms based on hidden Markov models (HMMs) [8-11]. A new architecture of such a model proposed in this paper takes into account the characteristic features of the nucleotide statistics near the start of a gene an separately considers each of six possible "frames" for the translation of a DNA into a protein code. This model is of special interest in the search for the overlapping genes that are frequently encountered in DNAs of bacteria and viruses. The algorithm of dynamic programming, known as the Viterbi algorithm [12] in the theory of hidden Markov models, specifies the most probable partition of a DNA nucleotide sequence into coding and noncoding regions, provided that the models used is valid. For four of five bacterial genomes, the program that implements the algorithm proposed predicts more than 70 of genes in exact agreement with the data provided by experts in the field of biology.