Michal Nánási, Tomáš Vinař, Broňa Brejová. Sequence annotation with HMMs: New problems and their complexity. Information Processing Letters, 115(6):635-639. 2015.

Download preprint: not available

Download from publisher: http://www.sciencedirect.com/science/article/pii/S002001901500040X

Related web page: not available

Bibliography entry: BibTeX

See also: early version


Hidden Markov models (HMMs) and their variants were successfully used for 
several sequence annotation tasks in bioinformatics. Traditionally, 
inference with HMMs is done using the Viterbi and posterior decoding 
algorithms. However, a variety of different optimization criteria and 
associated computational problems were proposed recently. 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.