This section gives a short introduction to dynamic programming. Readers not interested in the algorithm underlying the alignment routines should proceed to the next section.
Dynamic programming is a standard algorithmic technique in computer science and is particularily useful for problems such as sequence alignment. Intuitively, dynamic programming works bottom to top computing solutions to subproblems and storing them in a table. In this way, every subproblem is solved exactly once and when a subproblem is re-encountered the answer need not be recomputed.
There are two qualities a problem must possess for dynamic programming
to be applicable:
(1) Optimal substructure. The optimal solution to the problem must
contain within it optimal solutions to subproblems.
(2) Overlapping subproblems. The number of distinct subproblems is
small.19.1
It is not hard to see that most sequence alignment problems exhibit both of these behaviours. We will proceed by giving a simple example of how dynamic programming works.