Problemdefinition

Definition 1   Sei $\Sigma$ ein endliches Alphabet ohne das Leerzeichen '-' und $\Sigma'=\Sigma\cup \{'-'\}$. Seien weiter $A=a_1 \cdots a_n$ und $B=b_1 \cdots b_m$ mit $a_i,b_j \in \Sigma$ zwei Strings über diesem Alphabet. Ein (globales) Alignment von A und B sind zwei Strings $A'=a'_1 \cdots a'_k$ und $B'=b'_1 \cdots b'_k$, $n,m \leq k \leq n+m$, $a'_i,b'_j \in \Sigma'$ mit der Eigenschaft, daß für ein beliebiges $1\leq j \leq k$, a'_j oder b'_j $\in \Sigma$ ist und A' bzw. B' ohne die Leerzeichen A bzw. B ergeben.

Normalerweise schreibt man die beiden Strings so untereinander, daß der jeweils i-te Buchstabe von A' über dem i-ten Buchstaben von B' steht. In unseren Beispielen wird $\Sigma$ üblicherweise das Alphabet der Aminosäuren (siehe auch 1.1) oder der Nukleinsäuren (siehe auch 1.2) sein.

Beispiel 1    

         A' = - G C T G A T A T A G C T
         B' = G G G T G A T - T A G C T

Unter der exponentiell großen Anzahl möglicher Alignments möchte man das ``beste'' herausfinden. Dazu braucht man ein Maß, um die Güte von Alignments beurteilen zu können. Wenn man den Wert eines Alignments als $c(A',B')=\sum_{i=1}^k d(a_i',b_i')$ definiert, dann ist ein solches Maß ist die Distanz  $d(A,B)=\min_{\{A',B'\}} c(A',B')$ zwischen den beiden Strings A und B. Dabei geht man davon aus, daß sich zwei ähnliche Sequenzen im Laufe der Evolution durch sogenannte ``point mutations'' voneinander entfernt haben. Dabei gibt es in dem allgemein gebräuchlichen Modell drei mögliche Operationen:

1.

Deletion 
Aus Sequenz A wurde an der i-ten Stelle ein Buchstabe gelöscht, d.h. im Alignment steht an dieser Stelle in B' ein '-'.

2.

Insertion 
In Sequenz B wurde an der i-ten Stelle ein Buchstabe eingefügt, d.h. im Alignment steht an dieser Stelle in A' ein '-'.

3.

Substitution 
In Sequenz B wurde an der i-ten Stelle ein Buchstabe aus A ersetzt, d.h. im Alignment steht an dieser Stelle zwei unterschiedliche Buchstaben.

Gibt man nun diesen drei Operationen positive Kosten ( d(a,b), d(a,-), d(-,b) >0, $\forall a,b\in \Sigma, a\neq b$), so sucht man eine Folge dieser Operationen, welche möglichst billig ist und dabei String A in String B überführt. Es ist üblich und auch biologisch sinnvoll anzunehmen, daß ein solches Distanzmaß eine Metrik  bildet.

Beispiel 2   Nehmen wir an, wir haben als Distanzwerte d(C,G)=2 und d(-,G)=d(A,-)=3 gegeben, so können die Sequenzen aus Beispiel 1 durch folgende Operationen ineinander übergeführt werden.

insert G an Position 1
substitute C durch G an Position 3
delete A an Position 8

Die Kosten dieser Operationen sind 3+2+3=8.