previous section previous page next page next section

Online Lectures on Bioinformatics


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.