previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


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.

Proof

Alignment Quiz: 5.
Alignment Quiz: 5.


Comments are very welcome.
luz@molgen.mpg.de