Meno: Michal Nánási Biological sequence annotation with hidden Markov models Mgr. Broòa Brejová PhD. 2010 INF hidden Markov models, sequence annotation, viral recombination Hidden Markov models (HMMs) are an important tool for modeling biological sequences and their annotations. By sequence annotation we mean an assignment of labels to each symbol according to its function. For example, in gene finding we want to distinguish the regions of DNA that encode proteins from surrounding non-coding sequence. A hidden Markov model defines a probability distribution over all annotations of a given sequence $X$. HMMs are traditionally decoded by the Viterbi algorithm. Viterbi algorithm finds the most probable annotation for a subset of HMMs. In general, the sequence annotation is NP-hard and the Viterbi algorithm is used as a heuristic algorithm. Recently it has been shown that other decoding methods give better results than Viterbi in specific applications. We propose a new decoding method that allows uncertainty in region boundaries by considering all annotations with slightly shifted boundaries as the same. Our method (the highest expected reward decoding -- HERD) is an extension of the framework of maximum expected boundary accuracy decoding introduced by Gross \emph{et al.}. We evaluate HERD on the problem of detecting viral recombination in the HIV genome and compare it with an existing tool called jumping HMM which uses the Viterbi algorithm. HERD has better prediction accuracy in terms of the feature sensitivity and specificity, where feature is a single-colored block in an annotation.

Súbory diplomovej práce: