Ähnlichkeits- und Distanzmaße

Wir haben den Begriff des Alignments anhand des Distanz-Begriffes erläutert und motiviert. In diesem Modell versucht man, die Anzahl der erfolgten Mutationen zu minimieren. Eine zweite, meist häufiger benutzte Möglichkeit ist es, ein Ähnlichkeitsmaß  s(A,B) zu definieren. In einem Alignment ordnet man jeder Spalte einen Wert zu, i.a. gilt:

• s(a_i,b_j) > 0, falls a_i = b_j (Match)
• s(a_i,b_j) < 0, falls $a_i \neq b_j$ (Mismatch)
• s(-,b_j), s(a_i,-) < 0. (Insertion oder Deletion (Indel))

Man versucht nun, den Ähnlichkeitswert zu maximieren.

$$s(A,B)=\max\sum_{i=1}^k s(a'_i,b'_j)$$

Man kann zeigen, daß im Falle von globalem Alignment die beiden Probleme äquivalent sind (Übung). Im Falle von lokalem Alignment gibt es jedoch Unterschiede, die bei einigen Problemen verschiedene algorithmische Ansätze erzwingen. Da Ähnlichkeitsalignment in der Praxis häufiger vorkommt, werden wir es in den folgenden Abschnitten statt des Distanzalignments verwenden. Alternativ zu Kostenmatrizen gibt es auch Ähnlichkeitsmatrizen, welche für einzelne Aminosäuren die Werte s(a,b) angeben. Als Beispiel gebe ich hier die gebräuchliche Blosum-Kostenmatrix   an. Eine ausführliche Erklärung der verschiedenen Matrizen kann in [Zie97] gefunden werden.

	A	R	N	D	C	Q	E	G	H	I	L	K	M	F	P	S	T	W	Y	V
A	4
R	-1	5
N	-2	0	6
D	-2	-2	1	6
C	0	-3	-3	-3	9
Q	-1	1	0	0	-3	5
E	-1	0	0	2	-4	2	5
G	0	-2	0	-1	-3	-2	-2	6
H	-2	0	1	-1	-3	0	0	-2	8
I	-1	-3	-3	-3	-1	-3	-3	-4	-3	4
L	-1	-2	-3	-4	-1	-2	-3	-4	-3	2	4
K	-1	2	0	-1	-3	1	1	-2	-1	-3	-2	5
M	-1	-1	-2	-3	-1	0	-2	-3	-2	1	2	-1	5
F	-2	-3	-3	-3	-2	-3	-3	-3	-1	0	0	-3	0	6
P	-1	-2	-2	-1	-3	-1	-1	-2	-2	-3	-3	-1	-2	-4	7
S	1	-1	1	0	-1	0	0	0	-1	-2	-2	0	-1	-2	-1	4
T	0	-1	0	-1	-1	-1	-1	-2	-2	-1	-1	-1	-1	-2	-1	1	5
W	-3	-3	-4	-4	-2	-2	-3	-2	-2	-3	-2	-3	-1	1	-4	-3	-2	11
Y	-2	-2	-2	-3	-2	-1	-2	-3	2	-1	-1	-2	-1	3	-3	-2	-2	2	7
V	0	-3	-3	-3	-1	-2	-2	-3	-3	3	1	-2	1	-1	-2	-2	0	-3	-1	4