Enumerieren aller $\Delta$-optimalen Alignments

  

Abbildung: Enumerationsbaum für den Edit-Graph in Abbildung 16

Wenn wir nun alle $\Delta$-optimalen Pfade enumerieren wollen, so können wir dies für steigende $\delta$ tun, d.h. zuerst alle optimalen Pfade ($\delta =0$), dann alle Pfade mit einer Abweichung von 1 usw.

Um alle $\delta$-optimalen Pfade zu enumerieren, konstruieren wir einen Enumerationsbaum,   in dem jeder Pfad von der Wurzel zu einem inneren Knoten x einem (Teil-)Pfad im Edit-Graph entspricht und dessen Knoten mit $d(x)=\sum_{e\in R} \epsilon(e)$ beschriftet sind, d.h. wir fangen in der Wurzel mit dem Knoten (0,0) an, welcher mit 0 beschriftet ist. Die Wurzel hat drei Kinder (0,1), (1,1) und (1,0) welche mit dem ensprechenden d-Wert beschriftet sind.

Nehmen wir an, wir wollen alle $\delta$-optimalen Pfade ausgeben und haben schon alle $\delta '$-optimalen Pfade ausgegeben mit $\delta '\leq \delta$. Wir expandieren nun zuerst immer die Knoten mit minimalem d-Wert, bis wir an ein Blatt mit der Beschriftung (n,m) gelangen. Der minimale d-Wert ist immer $\delta$, da wir alle Knoten mit kleinerem d-Wert in einem früheren Schritt expandiert haben. Falls wir beim Expandieren ein Blatt (n,m) erreichen, so haben wir einen $\delta$-optimalen Pfad gefunden und geben ihn aus. Falls wir beim Expandieren einen d-Wert von mehr als $\delta$ erreichen, so wird dieser Knoten erst in einem späteren Durchlauf expandiert.

Nachdem wir diesen Vorgang für alle $\delta \leq \Delta$ iteriert haben, haben wir alle $\Delta$-optimalen Alignments ausgegeben.

Es ist klar, daß sich dieses Verfahren mit leichten Modifikationen auch auf andere Alignment Variationen anwenden läßt.