Online Lectures on Bioinformatics
Variants of the dynamic programming algorithm
Similarity and distance
In 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.
| Similarity | Distance |
| Local alignments | Evolution and phylogeny |
| suited for comparing proteins
( 
allowed) |
triangle inequality |
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 L1 and L2 and
m matches, u mismatches ang g gaps for an alignment
,
then for every alignment the expression
L1 + L2 = 2m + 2u + g
is valid.
Alignment Quiz: 5.
Comments are very welcome.
luz@molgen.mpg.de