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 web 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 modified: 10.11.2012
Contact: Tomáš Vinař, KAI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Broňa Brejová, KI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Office: M-163 Phone: +421(2)60295207
E-mail: 