DerHirschberg-Algorithmus berechnet das paarweiseSequenzalignment und hat einen zur Eingabelinearen Speicherbedarf. Der in den 1970er Jahren vonDan Hirschberg entwickelteAlgorithmus verwendet die Methode derDynamischen Programmierung und dasDivide-and-conquer Prinzip.

Der Hirschberg-Algorithmus ist ein allgemein einsetzbarer und optimaler Algorithmus zum Auffinden eines Sequenzalignment. Der bekannteBLAST-Algorithmus und derFASTA-Algorithmus sind nur suboptimale Heuristiken. Vergleicht man den Hirschberg-Algorithmus mit demNeedleman-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 zulinearisieren, was auch das Besondere an diesem Algorithmus ist: Die Berechnungen für ein Sequenzalignment benötigen nur linear viel Speicherplatz, womit diePlatzkomplexität des Algorithmus inO(n) liegt. Zur Berechnung eines Alignments zweier Zeichenketten${\displaystyle x}$ und${\displaystyle y}$mit${\displaystyle m=|x|}$ und${\displaystyle n=|y|}$ besitzt der Algorithmus eine Laufzeitvon${\displaystyle \mathrm{\Theta }(mn)}$ und einen Speicherverbrauch von${\displaystyle \mathrm{\Theta }(min\{m,n\})}$. O.B.d.A soll im Folgenden${\displaystyle n\le m}$ gelten, so dass der Platzbedarf in${\displaystyle \mathrm{\Theta }(n)}$ liegt.

Anwendung findet der Algorithmus zum Beispiel in derBioinformatik zum Abgleich verschiedenerDNA- oderProteinsequenzen.

In einer leicht abgewandelten Form wird Hirschbergs Algorithmus auch dazu verwendet, um in einemGraphen parallelZusammenhangskomponenten mit Aufwand${\displaystyle \mathrm{\Theta }({\log }^{2}n)}$ auf${\displaystyle \mathrm{\Theta }(n^2)}$ Prozessoren zu berechnen.

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

01${\displaystyle T_0}$ := 002 for j in 1..n loop03${\displaystyle T_j}$ :=${\displaystyle T_{j-1}}$ +${\displaystyle Ins(y_j)}$04 end loop05 for i in 1..m loop06       s :=${\displaystyle T_0}$07${\displaystyle T_0}$ :=${\displaystyle T_0}$ +${\displaystyle Del(x_i)}$08       c :=${\displaystyle T_0}$09       for j in 1..n loop10             c :=11             s :=${\displaystyle T_j}$12${\displaystyle T_j}$ := c13       end loop14 end loop

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

ε${\displaystyle y_1}$${\displaystyle y_2}$${\displaystyle y_3}$${\displaystyle y_4}$ ...ε0  1  2  3  ...${\displaystyle x_1}$1${\displaystyle x_2}$...

s =0c =${\displaystyle T_0}$ =1

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:

01${\displaystyle T_n}$ := 002 for j in n-1..0 loop03${\displaystyle T_j}$ :=${\displaystyle T_{j+1}}$ +${\displaystyle Ins(y_{j+1})}$04 end loop05 for i in m-1..0 loop06       s :=${\displaystyle T_n}$07${\displaystyle T_n}$ :=${\displaystyle T_n}$ +${\displaystyle Del(x_{i+1})}$08       c :=${\displaystyle T_n}$09       for j in n-1..0 loop10             c :=11             s :=${\displaystyle T_j}$12${\displaystyle T_j}$ := c13       end loop14 end loop

Der Divide-&-Conquer-Algorithmus vonHirschberg berechnet ein Alignment der Zeichenketten${\displaystyle |x|}$ und${\displaystyle |y|}$, indem er Vorwärts- und Rückwärtsdurchlauf miteinander kombiniert (Zeilenangaben beziehen sich auf dennachfolgend angegebenen Pseudocode):

1. Wenn${\displaystyle |x|=1}$ oder${\displaystyle |y|=1}$ liegt eintriviales 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${\displaystyle |x|>1}$ und${\displaystyle |y|>1}$ geht man über zu Schritt 2.

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

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

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

5. DieLevenshtein-Distanz von${\displaystyle x}$ zu${\displaystyle y}$ kann nun errechnet werden, indem man entlang der mittleren Zeile der Alignment-Matrix läuft und nach einer kleinsten Summe von korrespondierenden${\displaystyle T^{\ell }}$- und${\displaystyle 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${\displaystyle x}$ schneidet. An dieser Stelle wird${\displaystyle 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${\displaystyle x}$ und${\displaystyle 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).

01 --02 -- DerDivide-&-Conquer-Algorithmus von Hirschberg zur03 -- Berechnung des globalen Alignments auf linearem Speicher.04 --05 -- Bei${\displaystyle m=|x|,n=|y|,n\le m}$ besitzt der Algorithmus eine Laufzeit von${\displaystyle \mathrm{\Theta }(nm)}$06 -- und einen Speicherverbrauch von${\displaystyle \mathrm{\Theta }(n)}$.07 --08 function HirschbergAlignment(x,y : string) return A is09        function SubAlignment(${\displaystyle i_1}$,${\displaystyle j_1}$,${\displaystyle i_2}$,${\displaystyle j_2}$ : integer) return A is10                mitte,cut : integer11                s,c : real12${\displaystyle T^{\ell },T^r}$ : array(${\displaystyle j_1}$..${\displaystyle j_2}$) of real13        begin14                if${\displaystyle i_1+1=i_2}$ or${\displaystyle j_1=j_2}$ then15                        -- Konstruiere Matrix T für die Teil-Strings16                        -- x(${\displaystyle i_1+1}$..${\displaystyle i_2}$) und y(${\displaystyle j_1+1}$..${\displaystyle j_2}$)17                        -- Achtung: Nur linearer Speicherplatz erforderlich!18                        T := ...19                        -- Berechnetriviales Alignment auf Matrix T20                        -- in linearer Laufzeit21                        return Alignment(T,x(${\displaystyle i_1+1}$..${\displaystyle i_2}$),y(${\displaystyle j_1+1}$..${\displaystyle j_2}$))22                end if2324                mitte :=${\displaystyle (i_1+i_2)/2}$25                -- finde ausgehendvon${\displaystyle (i_1,j_1)}$ den minimalen Pfad26                -- mit dem Vorwärtsalgorithmus:27${\displaystyle T^{\ell }(j_1)}$ := 028                for j in${\displaystyle j_1+1}$..${\displaystyle j_2}$ loop29${\displaystyle T^{\ell }(j)}$ :=${\displaystyle T^{\ell }(j-1)+Ins(y_j)}$30                end loop31                for i in${\displaystyle i_1+1}$..mitte loop32                        s :=${\displaystyle T^{\ell }(j_1)}$33                        c :=${\displaystyle T^{\ell }(j_1)+Del(x_i)}$34${\displaystyle T^{\ell }(j_1)}$ := c35                        for j in${\displaystyle j_1+1}$..${\displaystyle j_2}$ loop36                                c :=37                                s :=${\displaystyle T^{\ell }(j)}$38${\displaystyle T^{\ell }(j)}$ := c39                        end loop40                end loop41                -- finde minimalen score-pfadnach${\displaystyle (i_2,j_2)}$42${\displaystyle T^r(j_2)}$ := 043                for j in${\displaystyle j_2-1}$..${\displaystyle j_1}$ loop44${\displaystyle T^r(j)}$ :=${\displaystyle T^r(j+1)+Ins(y_{j+1})}$45                end loop46                for i in${\displaystyle i_2-1}$..mitte loop47                        s :=${\displaystyle T^r(j_2)}$48                        c :=${\displaystyle T^r(j_2)+Del(x_{i+1})}$49${\displaystyle T^r(j_2)}$ := c;50                        for j in${\displaystyle j_2-1}$..${\displaystyle j_1}$ loop51                                c :=52                                s :=${\displaystyle T^r(j)}$53${\displaystyle T^r(j)}$ := c54                        end loop55                end loop56                -- finde den Punkt aus${\displaystyle j_1}$..${\displaystyle j_2}$ in dem der Minimale Pfad die57                -- mittlere Zeile schneidet:58                --${\displaystyle cut:{=}_{def}{\text{argmin}}_{j_1\le j\le j_2}(T^{\ell }(j)+T^r(j))}$59                for j in${\displaystyle j_1}$..${\displaystyle j_2}$ loop60                        if j=${\displaystyle j_1}$ then61                                cut :=${\displaystyle j_1}$62                        elsif then63                                cut := j64                        end if65                end loop66                -- Alignment entsteht durch Konkatenation von linkem und67                -- rechtem Teil-Alignment:68                return SubAlignment(${\displaystyle i_1}$,${\displaystyle j_1}$,mitte,cut)69${\displaystyle \star }$ SubAlignment(mitte,cut,${\displaystyle i_2}$,${\displaystyle j_2}$)70        end SubAlignment71        m,n : integer72 begin73        m :=${\displaystyle |x|}$; n :=${\displaystyle |y|}$74        -- Sonderbehandlung:${\displaystyle x}$ ist der leere String und lässt keine Zerteilung zu:75        if m=0 then76                return${\displaystyle \left(\begin{array}{c}-\\ y_1\end{array}\right)\star \left(\begin{array}{c}-\\ y_2\end{array}\right)\star \cdots \star \left(\begin{array}{c}-\\ y_n\end{array}\right)}$77        else78                return SubAlignment(0,0,m,n)79        end if80 end HirschbergAlignment

• D. S. Hirschberg:A linear space algorithm for computing maximal common subsequences. In:Communications of the ACM.Band 18,Nr. 6, 1975,S. 341–343 (englisch,uci.edu [PDF]). 
• Chao, K.M., Hardison, R.C. and Miller, W.:Recent developments in linear-space alignment methods: a survey. In:Journal of Computational Biology.Nr. 4, 1994,S. 271–291 (englisch,edu.tw [PDF]). 

• Algorithmus
• Bioinformatik
• Dynamische Programmierung
• Parallelverarbeitung