Online Lectures on Bioinformatics

Variants of the dynamic programming algorithm
Similarity and distanceIn the similarity approach, the score of an alignment is maximized. The edit distance gives a measure (the cost) of the minimum number of elementary edit operations (insertions, deletions and substitutions of characters) being necessary to transform one sequence into the other one. In this way it's possible to define a metric on a set of sequences and finding the minimum distance alignment of two sequences results in minimizing the cost.
Theorem: For every distance function a similarity function, so that the alignments resulting from minimization and maximization of these functions are the same respectively.
The key for proofing this is the Alignment Invariant (AI):
Given two sequences with the lengths L_{1} and L_{2} and
m matches, u mismatches ang g gaps for an alignment
,
then for every alignment the expression
L_{1} + L_{2} = 2m + 2u + g
is valid.
Alignment Quiz: 5. Comments are very welcome. luz@molgen.mpg.de 