Computational Biology
@ Comenius University in Bratislava

Rastislav Šrámek. The On-line Viterbi Algorithm. Master thesis, Comenius University in Bratislava, 2007. Supervised by Tomáš Vinař and Broňa Brejová.

Download preprint: 07sramekth.pdf, 616Kb

Download from publisher: http://vili.uniba.sk:8880/ddp/dostupne/2007-FM-lfasYR/

Related web page: not available

Bibliography entry: BibTeX

Abstract:

Hidden Markov models (HMMs) are probabilistic models that have been 
extremely successful in addressing problems in bioinformatics, error-
correcting codes, natural language processing, and other important areas. 
In many of these applications, the Viterbi algorithm is used to find the 
most probable state path through the model generating sequences that can 
be extremely long. Known algorithms either use at least Omega(n) memory in 
the best case and always find the most probable state path, or use o(n) 
memory in the worst case, but do not guarantee correct result.

We introduce a modification of the Viterbi algorithm which is guaranteed 
to find the most probable state path and uses anywhere between O(1) and 
O(n) memory, depending on the model and the input sequence. For a simple 
class of models, we show that the expected memory needed to process a 
sequence is O(log(n)). We present results from experiments with more 
complicated models for the problem of gene finding in bioinformatics that 
indicate similar expected memory requirements.