previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


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(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.
luz@molgen.mpg.de