Michal Nanasi, Tomas Vinar, Brona Brejova. Sequence Annotation with HMMs: New Problems and Their Complexity. Technical Report arXiv:1210.2587, arXiv.org, October 2012.

Download preprint: not available

Download from publisher: http://arxiv.org/abs/1210.2587

Related www page: not available

Bibliography entry: BibTeX

Abstract:

Hidden Markov models (HMMs) and their variants were successfully used for 
several sequence annotation tasks. Traditionally, inference with HMMs is 
done using the Viterbi and posterior decoding algorithms. However, recently 
a variety of different optimization criteria and associated computational 
problems were proposed. In this paper, we consider three HMM decoding 
criteria and prove their NP hardness. These criteria consider the set of 
states used to generate a certain sequence, but abstract from the exact 
locations of regions emitted by individual states. We also illustrate 
experimentally that these criteria are useful for HIV recombination 
detection. 

Last update: 06/02/2013