Publication details

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 from publisher | Early version | BibTeX

Abstract

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.


Photo

Contact

Mailing address:
Bronislava Brejova
Katedra informatiky
FMFI UK
Mlynska Dolina
842 48 Bratislava
Slovakia

Office: M163

Phone: +421-2-60295217

E-mail: my_surname at dcs.fmph.uniba.sk