Ausgabe des Alignments

Die Tabelle und der Edit-Graph bieten dann auch die beiden prinzipiellen Möglichkeiten ein Alignment auszugeben:

• Benutze traceback  pointer, welche während der Berechnung des kürzesten Pfades gesetzt werden.
• Führe die Berechung ``rückwärts'' aus. Der optimale Wert D_n,m wurde durch eine der drei Möglichkeiten aus der Rekursion erreicht. Jede der drei Möglichkeiten entspricht einem Ende des Alignments (Substitution, Deletion, Insertion).

Man beachte, daß es durchaus mehrere Alternativen beim Zurückgehen in der Matrix, bzw. im Edit-Graph geben kann, d.h. es kann mehrere optimale Alignments geben. Wir werden später sehen, wie man geschickt alle (sub)optimalen Alignments ausgeben und/oder ihre Zahl bestimmen kann.

Beispiel 4   Betrachte die beiden Sequenzen aus dem Beispiel 3 (A=WRITERS und B=VINTNER). In der Tabelle zur Berechung eines optimalen Alignments ist der traceback markiert.

		W	R	I	T	E	R	S
	0	1	2	3	4	5	6	7
V	1	1	2	3	4	5	6	7
I	2	2	2	2	3	4	5	6
N	3	3	3	3	3	4	5	6
T	4	4	4	4	3	4	5	6
N	5	5	5	5	4	4	5	6
E	6	6	6	6	5	4	5	6
R	7	7	6	7	6	5	4	5

Der Traceback  läuft nun von Position (n,m) bis zu Position (0,0). In dem Beispiel liefert er uns das optimale globale Alignment:

                W R I - T - E R S
                - V I N T N E R -

mit Wert 5.

Wir fassen die obigen Diskussionen in folgendem Satz zusammen:

Satz 2   Die DP-Tabelle D_i,j zum globalen Alignment zweier Strings der Länge n und m kann in Zeit O(nm) gefüllt werden. Somit kann das globales Alignment in Zeit O(nm) berechnet werden. Ein optimales Alignment kann anhand der Tabelle in Zeit O(n+m) ausgegeben werden.

Beweis: Jeder einzelne Schritt beim Auffüllen der Matrix besteht in einer Fallunterscheidung, welche in konstanter Zeit durchgeführt werden kann. Da es nm Matrixeinträge gibt, beträgt die Gesamtlaufzeit dafür O(nm). Da ein optimales Alignment höchstens Länge O(n+m) hat und jeder traceback-Schritt konstante Zeit benötigt, beträgt die Gesamtlaufzeit zur Ausgabe des Alignments O(n+m).