Online Lectures on Bioinformatics

Variants of the dynamic programming algorithmIntroductionIn 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^{2}), 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. luz@molgen.mpg.de 