Computational Biology
@ Comenius University in Bratislava

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

Download preprint: not available

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

Related web page: http://compbio.fmph.uniba.sk/herd/

Bibliography entry: BibTeX

See also: early version

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 (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.