Online Lectures on Bioinformatics

Variants of the dynamic programming algorithm
Parametric AlignmentsThe score function of an alignment is linear e.g. in the gap penalty or the value of a mismatch. In a graph 'alignmentscore' versus 'gap penalty' each alignment defines a line:figure: Parametric Alignments (schematic) An optimal alignemnt for the gappenalty Zero gets worse assuming increasing gappenalties. For a certain gappenalty another alignment has to be preferred. For expensive gappenalties, there are no more gaps in the optimal alignment and the alignment score depends no more on the gappenalty. When regarding two variable parameters, each alignment defines a plane. The tesselation of the parameterplane may be computed and the cells of the tesselation are convex polygons. Comments are very welcome. luz@molgen.mpg.de 