(This section is taken with permission from [17] because
it succinctly describes the process of finding the best parse). Given
the L matrices, a simple dynamic programming algorithm can find the
parse of S with the highest score (called the ``best parse"). The
constraints that apply are that exons and introns alternate and are
adjacent and non-overlapping. Suppose we have already parsed the
prefix of S beginning at position 1 and ending at position j.
Such a parse is called a partial parse. Let the value 
denote the score for the best partial parse that ends with an exon
that terminates at position j, and the value 
denote the
score for the best partial parse that ends with an intron that
terminates at position j. The following recursive definitions of
and 
can be converted into a dynamic programming
algorithm (see Auger and Lawrence [1], Sankoff [12]
and Snyder and Stormo [14]).
The score for the best parse is 
.