Hirschberg-Algorithmus
# Hirschberg-Algorithmus

Der Hirschberg-Algorithmus berechnet das paarweise Sequenzalignment und hat einen zur Eingabe linearen Speicherbedarf. Der in den 1970er Jahren von Dan Hirschberg entwickelte Algorithmus verwendet die Methode der Dynamischen Programmierung und das Divide-and-conquer Prinzip.

## Allgemeines

Der Hirschberg-Algorithmus ist ein allgemein einsetzbarer und optimaler Algorithmus zum Auffinden eines Sequenzalignment. Der bekannte BLAST-Algorithmus und der FASTA-Algorithmus sind nur suboptimale Heuristiken. Vergleicht man den Hirschberg-Algorithmus mit dem Needleman-Wunsch-Algorithmus, so handelt es sich beim Hirschberg-Algorithmus weniger um einen komplett neuen Algorithmus, sondern eher um eine clevere Strategie, die den Needleman-Wunsch-Algorithmus geschickt einsetzt, um den Speicherverbrauch zu linearisieren, was auch das Besondere an diesem Algorithmus ist: Die Berechnungen für ein Sequenzalignment benötigen nur linear viel Speicherplatz, womit die Platzkomplexität des Algorithmus in O(n) liegt. Zur Berechnung eines Alignments zweier Zeichenketten $x$ und $y$ mit $m=|x|$ und $n=|y|$ besitzt der Algorithmus eine Laufzeit von $\Theta (mn)$ und einen Speicherverbrauch von $\Theta (\min\{m,n\})$. O.B.d.A soll im Folgenden $n\leq m$ gelten, so dass der Platzbedarf in $\Theta (n)$ liegt.

Anwendung findet der Algorithmus zum Beispiel in der Bioinformatik zum Abgleich verschiedener DNA- oder Proteinsequenzen.

In einer leicht abgewandelten Form wird Hirschbergs Algorithmus auch dazu verwendet um in einem Graphen parallel Zusammenhangskomponenten mit Aufwand $\Theta (\log ^{2}n)$ auf $\Theta (n^{2})$ Prozessoren zu berechnen.

### Berechnung der Levenshtein-Distanz auf linearem Speicherplatz

Zum Verständnis des Hirschberg-Algorithmus ist es zunächst wichtig zu verstehen, dass sich die Levenshtein-Distanz auf linearem Speicherplatz berechnen lässt:

In den Zeilen 1–4 wird das eindimensionale Feld $T$ mit n Plätzen Speicherbedarf initialisiert. In Zeile 6 wird die Initialisierung des ersten Elements $T_{0}$ in $s$ gerettet. Danach wird $T_{0}$ und $c$ mit dem Startwert für die nächste Zeile initialisiert. Die nachfolgende Abbildung zeigt eine Momentaufnahme eines Zeilendurchlaufs. In der inneren Schleife zeigt $c$ immer auf das jeweils zuvor berechnete Ergebnis, während $s$ das noch benötigte Ergebnis der letzten Zeile sichert. Nach Zeile 14 steht die Levenshtein-Distanz als Ergebnis in $T_{n}$.

Es sollte klar sein, dass sich diese Berechnung auch rückwärts durchführen lässt. Dabei wird die gedachte Matrix nicht von links nach rechts und von oben nach unten durchlaufen, sondern von rechts unten nach links oben:

### Berechnung des Alignments auf linearem Speicherplatz

Der Divide-&-Conquer-Algorithmus von Hirschberg berechnet ein Alignment der Zeichenketten $|x|$ und $|y|$, indem er Vorwärts- und Rückwärtsdurchlauf miteinander kombiniert (Zeilenangaben beziehen sich auf den nachfolgend angegebenen Pseudocode):

1. Wenn $|x|=1$ oder $|y|=1$ liegt ein triviales Alignment-Problem vor (Zeilen 14 – 22). Ein String bestehend aus nur einem Zeichen muss auf einen anderen String ausgerichtet werden und ein Alignment wird zurückgegeben. Ist $|x|>1$ und $|y|>1$ geht man über zu Schritt 2.

2. Ein Vorwärtsdurchlauf berechnet ein Alignment von $y$ und der ersten Hälfte von $x$ (Zeilen 27 – 40). Das Ergebnis des Vorwärtsdurchlaufs ist ein Feld $T^{\ell }$, dessen Elemente die Kosten für einen Durchlauf von $(0,0)$ bis $(|x|/2,j)$ (mit $0\leq j\leq n$) angeben.

3. Ein Rückwärtsdurchlauf berechnet ein Alignment von $y$ mit der zweiten Hälfte von $x$ (Zeilen 42 – 55). Das Ergebnis ist ein weiteres Feld $T^{r}$, dessen Elemente die Kosten für einen Durchlauf von $(n,m)$ zurück zu $(|x|/2,j)$ angeben.

4. In den Feldelementen $T^{\ell }(n)$ und $T^{r}(0)$ stehen die beiden Levenshtein-Distanzen für die globalen Alignments von $y$ und den jeweiligen Hälften von $x$. In den restlichen Elementen von $T^{\ell }$ stehen die Distanzen von der ersten $x$-Hälfte zu allen Präfixen von $y$. Entsprechend enthalten die restlichen Elemente von $T^{r}$ die Distanzen von der zweiten $x$-Hälfte zu allen Suffixen von $y$.

5. Die Levenshtein-Distanz von $x$ zu $y$ kann nun errechnet werden, indem man entlang der mittleren Zeile der Alignment-Matrix läuft und nach einer kleinsten Summe von korrespondierenden $T^{\ell }$- und $T^{r}$-Elementen sucht. Ist eine solche minimale Summe gefunden, hat man eine Position in der mittleren Zeile gefunden, in der das optimale Alignment die mittlere Zeile bzw. die Mitte von $x$ schneidet. An dieser Stelle wird $y$ in zwei Teile zerteilt und damit kann auch das Alignment-Problem in zwei kleinere Alignment-Probleme zerteilt werden (Zeilen 59 – 65).

6. Schritt 1 wird rekursiv auf den beiden Teilen von $x$ und $y$ aufgerufen. Die beiden rekursiven Aufrufe geben Teil-Alignments zurück, die zu einem einzigen Alignment verknüpft werden. Das Alignment wird zurückgegeben (Zeilen 68 und 69).

