Nonstationary hidden Markov model estimation

joe at joe at
Tue Mar 23 20:50:26 EST 2004

In article <pgpmoose.200403161800.20071 at>,
John <uebersaxjohn2000 at> wrote:
>Does anyone know if the "Forward Algorithm" to estimate:
>   Pr(o1, o2, ..., oT | theta),
>   o1, o2, ..., OT = observed states at T timepoints or sequence
>                     positions
>   theta           = a vector of parameters that define a hidden 
>                     Markov model
>is correct if transition probability parameters are nonstationary?  
>That is, does the Forward Algorithm give the same value as the full 
>expansion of the likelihood function if the probabilities of moving
>from state i to state j differ from one period/sequence position to 

If I understand correctly, the Forward Algorithm does not compute
Prob(o_1, o_2, ..., o_T | theta)  but computes the  Prob(data | theta, o_T)
recursively, as T increases.  At the end this allows you to put the
probabilities together and compute Prob(data | theta), which sums over all
combinations of the  o_i.   I think it is the
Viterbi algorithm that then can be used to backtrack and compute
Prob(data & o_1, o_2, ..., o_n | theta) / Prob(data | theta).

My understanding is that the method works in the nonstationary case, but
there is one catch.

You have to make use of the equilibrium probabilities of the states at
the end of the sequence.  That may or may not be available to you in the
nonstationary case.  If it isn't available, then you are stuck.  If
the nonstationarity comes from some meta-model, then it might be available
to you.

Joe Felsenstein         joe at
 Department of Genome Sciences and Department of Biology,
 University of Washington, Box 357730, Seattle, WA 98195-7730 USA

More information about the Comp-bio mailing list