Michal Nanasi, Tomas Vinar, Brona Brejova. The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection . In Amihood Amir, Laxmi Parida, ed., Combinatorial Pattern Matching, 21st Annual Symposium (CPM 2010), 6129 volume of Lecture Notes in Computer Science, pp. 164-176, New York, NY, June 2010. Springer.

Download preprint: not available

Download from publisher: http://dx.doi.org/10.1007/978-3-642-13509-5_16

Related www page: not available

Bibliography entry: BibTeX

See also: early version


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 (Kall et al., 2005; 
Brejova et al., 2007; Gross et al., 2007; Brown and Truszkowski, 2010). 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. 

Last update: 07/07/2010