previous section previous page next page next section

Online Lectures on Bioinformatics


Variants of the dynamic programming algorithm

Parametric Alignments

The score function of an alignment is linear e.g. in the gap penalty or the value of a mismatch. In a graph 'alignment-score' versus 'gap penalty' each alignment defines a line:

figure: Parametric Alignments (schematic)

An optimal alignemnt for the gap-penalty Zero gets worse assuming increasing gap-penalties. For a certain gap-penalty another alignment has to be preferred. For expensive gap-penalties, there are no more gaps in the optimal alignment and the alignment score depends no more on the gap-penalty.

When regarding two variable parameters, each alignment defines a plane. The tesselation of the parameter-plane may be computed and the cells of the tesselation are convex polygons.

Comments are very welcome.