Variants of the dynamic programming algorithm

Introduction

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(n²), 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.