For sequences a and b, score
function 
for 
,
and gap penalty function 
for gaps of length k,
define 
to be the maximum similarity score for segments ending
in 
and 
respectively. First set 
for i=0 or j=0,
then for 
and 
there is a recursion
This formula, introduced in Smith and Waterman (1981), gives
recursively the highest score for a local alignment ending at 
.
It is in the form of Theorem 1 with zero vertex weights.
The ``0'' option in the maximization corresponds to having the local
alignment segment starting at 
, and leaving it out gives the
maximum similarity score for global alignments from the first row or
column to 
. Turning the Smith and Waterman algorithm into a
global alignment algorithm is as simple as removing the ``0'' option in
the maximum.