[Biojava-l] help about Viterbi in HMM

hz5@njit.edu hz5@njit.edu
Mon, 16 Sep 2002 16:55:34 -0400 (EDT)


ptr should stands for pointer.

argmax should stands for argument maximum.

In short, the viterbi algorithm is saying that the most probable path is the 
path that I am going to predict. So all the recursion is doing is trying to 
find the most probable path. In order to find the path, you have to go forward 
to calculate all possible scores(it sounds too much, but you actually only keep 
the max one in each step, that's why you have argmax, and you also store a 
pointer to the state where you get the max score), and then trace back 
following the pointers start from the max probability you finally got.

A detailed explaination and step by step representation can be found at:
http://www.scs.leeds.ac.uk/scs-only/teaching-
materials/HiddenMarkovModels/html_dev/viterbi_algorithm/s1_pg1.html

I have an excersize-version of implementation in c++ myself, if you need, email 
me.

Hope this help!

Quoting  <huazhongw@263.net>:

> Dear friends,
>    I am now very insterested in bioinformatics and only a newcomer to
> this subject.
>    I have the book "Biological sequence analysis" by Richard Durbin and
> have read it so long a time but understand little,especially about HMM.I
> have studied Probablity and Statistics in chinese but on in English.So
> many terms in equations in the book confused me very much,even some of
> them I can not find them in anywhere.
>    For example,the Algorihtm of Viterbi in HMM in 3th chapter of the
> book(page 56-57).What is "ptr" and how to "argmax" in the recursion of
> Viterbi?And I don't understand the procedure of recursion using Viterbi
> algorithm.
>    So I have a request.Would anyone  please write down to me the
> detailed one-by-one recursion produres using Viterbi algorithm to model
> the dice rolls example in page 57.How to recurse to know what dice(fair
> or leaded)was used?Ten rolls or so of recrusion is enough for me to
> understand,I think.
>    Here I found no person and no English material who and which could
> help me.
>    I need your help.Thanks in advance.
> 
> 
>       Yours,
> 
>   Wang Hua-zhong  Ph.D
>   Cytogenetics Institute,
>   Department of Agronomy ,
>   Nanjing Agricultural University,
>   Nanjing,Jiangsu,P.R.China
>   210095
> 
> _______________________________________________
> Biojava-l mailing list  -  Biojava-l@biojava.org
> http://biojava.org/mailman/listinfo/biojava-l
> 



=========================================================
Haibo Zhang, PhD student
Computational Biology, NJIT & Rutgers University
Center for Applied Genomics, PHRI
http://afs13.njit.edu/~hz5