Variants of the dynamic programming algorithm In the previous
section the dynamic programming algorithm, by which an optimal
global alignment between two sequences allowing affine linear
gap penalty functions can be found in O(n2), was presented . In
this way, the comparison of two sequences was reduced to finding
the longest (or shortest) path in a directed weighted graph, the
edit graph. Given two sequences, it 's often not a global
alignment but an alignment between substrings of the sequences,
which is of interest. In these cases the dynamic programming
algorithm has to be adapted to the given task and biological
background respectively. Comments are very welcome.