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