Standard-Bounding

Nimm an, wir haben für jeden Knoten r des Gitters eine untere Schranke l für die Kosten des kürzesten Pfades in $r\to t$. So ist z.B. :

$$L(r\to t) := \sum_{1\leq i< j\leq k} c(A^*(\sigma^r_i,\sigma^r_j))$$

 eine untere Schranke, da die Projektion eines optimalen Alignments A^* auf i und j sicherlich einen höheren Wert als das optimale Alignment von $\sigma_i$ und $\sigma_j$ hat also:

$$\sum_{1\leq i< j\leq k} c(A^*(\sigma^r_i,\sigma^r_j)) \leq c(r\to^* t)$$

Nun braucht man in der Expansion eines Knotens q einen Nachbarn r nicht in Q einzufügen, wenn gilt:

$$c(s\to^* q) + c(q,r) + L(r\to t) > U$$

wobei U eine obere Schranke für den Wert c(A^*) eines optimalen multiplen Alignments ist. Das heißt, wenn die Summe des kürzesten Weges nach q plus die Kosten der Kante von q nach r plus eine untere Schranke eines kürzesten Weges von r nach t schon größer als eine obere Schranke für ein optimales Alignment ist, dann kann es kein optimales Alignment durch q und r geben. Aus diesem Grunde braucht r nicht in Q eingefügt werden.