Sequence annotation with HMMs: new problems and their complexity

DOI10.1016/J.IPL.2015.03.002MaRDI QIDQ2345874zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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

zbMATH Keywords

bioinformaticscomputational complexityhidden Markov modelrecombination detectionsequence annotation

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• The consensus string problem and the complexity of comparing hidden Markov models.
• Sequence annotation with HMMs: new problems and their complexity
• The most probable annotation problem in HMMs and its application to bioinformatics
• scientific article; zbMATH DE number 2081009 (Why is no real title available?)

Describes a project that uses

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)