Now we give another illustration of a dynamic programming method, that
is not directly related to sequence alignment. Suppose we have a
single sequence 
and we have a probability model
for the probability of observing residue u in position
i. Also we have a score function 
for residue
u in position i which are summed to get the score for
the sequence. We might be interested in working out the
probability of observing a given total score. An example of this would
be if the score function is designed to detect splice sites on a DNA
sequence, the probabilities correspond to some model which might be a
null model or a splice site model, and we would like to calculate the
likelihood under this model of an observed score.
We suppose the scores are integer values, with 
.
Take G to be the DAG with vertices
and 
is an edge if
for some 
, in which case it has weight
The weight of a path comes from multiplying the edge weights. Adding
up the weights of all paths to a given vertex 
gives the
probability of obtaining a total score 
. This example comes
from unpublished lecture notes by Phil Green.