Sequence annotation with HMMs: new problems and their complexity

DOI10.1016/J.IPL.2015.03.002zbMATH Open1328.68096DBLPjournals/ipl/NanasiVB15arXiv1210.2587OpenAlexW1996356785WikidataQ57689798 ScholiaQ57689798MaRDI QIDQ2345874FDOQ2345874

Authors: Michal Nánási, Tomáš Vinař, Broňa Brejová 

Publication date: 21 May 2015

Published in: Information Processing Letters (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1210.2587

Recommendations

• The most probable annotation problem in HMMs and its application to bioinformatics
• The consensus string problem and the complexity of comparing hidden Markov models.
• scientific article; zbMATH DE number 2081009
• Inference with constrained hidden Markov models in PRISM
• Bridging Viterbi and posterior decoding: a generalized risk approach to hidden path inference based on hidden Markov models

zbMATH Keywords

computational complexityhidden Markov modelbioinformaticssequence annotationrecombination detection

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Biological Sequence Analysis
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• The consensus string problem and the complexity of comparing hidden Markov models.
• The most probable annotation problem in HMMs and its application to bioinformatics
• Sequence annotation with HMMs: new problems and their complexity
• The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection

Cited In (4)

• The most probable annotation problem in HMMs and its application to bioinformatics
• Sequence annotation with HMMs: new problems and their complexity
• Title not available (Why is that?)
• The consensus string problem and the complexity of comparing hidden Markov models.

Uses Software

• Pfam

This page was built for publication: Sequence annotation with HMMs: new problems and their complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345874)