A hidden Markov model can be written in the form of a
weighted DAG, as follows. Suppose 
is the hidden Markov chain, with 
and 
. The corresponding DAG is a graph with vertices
and an edge at 
iff 
. This correspondence
can be easily extended to the case where the state space
differs for different t. The edge weights are
and the vertex weights
Then the product along a path gives its likelihood. The dynamic
programming algorithm in Theorem 1 gives the most likely
path, and is the Viterbi algorithm in disguise. The forward-backward
algorithms to find the likelihood of the observations can be
considered a variant of the dynamic programming algorithm which lets
us calculate 
as the sum of weights of all paths ending in 
and 
the sum of weights of all paths continuing from 
.
Note that it is not true that all dynamic programming algorithms on
DAGs are equivalent to HMMs; the DAG must have the special structure
in (2). In particular the Smith and Waterman algorithm,
where the DAG consists of all allowable alignments, is not quite in
that form. Although we must step down one row or along one column at
each time point, the inclusion of gaps makes ``time'' proceed at
different rates on the two sequences compared. For example, one might
try thinking of 
giving a process 
corresponding to
an alignment. Then 
can be defined as the pair
of residues corresponding to 
, one of which
may take the value 
for a gap. This is almost the standard form
for an HMM except that we only know 
and T conditionally on the
unobserved process X.
