A slight [modification] of the [Needleman Wunsch algorithm] yields a [local] [sequence similarity] [algorithm] ([Michael Waterman] is [quote]d as saying that this was more publicity than he dared to think he'd get just for adding a [zero] to published work). The Smith Waterman algorithm uses the same [objective function] as the Needleman Wunsch algorithm (so you should [read that node]!), but searches for the two [substring]s with the highest [similarity] [score].

Since Needleman Wunsch runs in [time] O(m n), when the [sequence]s have [length]s m and n, it would appear that you'd need time O(m³ n³) to do this. However, a minor modification of the [dynamic programming] algorithm used there yields local sequence similarity in time O(m n). In the dynamic programming [matrix] for Needleman Wunsch, element (i,j) contains the highest score for a partial alignment of letters 1, ..., i of the first sequence to letters 1, ..., j of the second. To be able to do the same thing for a local sequence similarity measure, one more rule is added to the update rule for the Needleman Wunsch algorithm: Any (match) cell with a [negative] score is changed to score 0. This represents the fact the a local alignment could always start at that cell, scoring (so far) 0, and would be better than any negative score. Similarly, when the matrix is complete, the [alignment] score is taken to be the [maximum] over the entire matrix (whereas Needleman Wunsch just takes the score at the far [corner] of the matrix).

[Bellman] probably knew all of this, too.