The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection

DOI10.1007/978-3-642-13509-5_16MaRDI QIDQ3575245zbMATH OpenOpenAlexWikidataFDO

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

Publication date 26 July 2010

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

zbMATH Keywords

decoding algorithmshidden Markov modelsjumping HMMsrecombination detection

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Protein sequences, DNA sequences (92D20) Information theory (general) (94A15)

Abstract: Hidden Markov models are traditionally decoded by the Viterbi algorithm which finds the highest probability state path in the model. In recent years, several limitations of the Viterbi decoding have been demonstrated, and new algorithms have been developed to address them citep{Kall2005,Brejova2007,Gross2007,Brown2010}. In this paper, we propose a new efficient highest expected reward decoding algorithm (HERD) that allows for uncertainty in boundaries of individual sequence features. We demonstrate usefulness of our approach on jumping HMMs for recombination detection in viral genomes.

Recommendations

• A novel method for decoding any high-order hidden Markov model
• Efficient backward decoding of high-order hidden Markov models
• A novel entropy-based decoding algorithm for a generalized high-order discrete hidden Markov model
• Optimal spaced seeds for hidden Markov models, with application to homologous coding regions
• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• Speeding up HMM decoding and training by exploiting sequence repetitions
• Optimisation of HMM topologies enhances DNA and protein sequence modelling
• The most probable annotation problem in HMMs and its application to bioinformatics

Cited in

(5)

• Sequence annotation with HMMs: new problems and their complexity
• Bridging Viterbi and posterior decoding: a generalized risk approach to hidden path inference based on hidden Markov models
• Improvement of the jpHMM approach to recombination detection in viral genomes and its applications to HIV and HBV.
• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• Speeding up HMM decoding and training by exploiting sequence repetitions

This page was built for publication: The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection

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