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 und mit und besitzt der Algorithmus eine Laufzeit von und einen Speicherverbrauch von . O.B.d.A soll im Folgenden gelten, so dass der Platzbedarf in 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 auf 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:

01  := 0
02 for j in 1..n loop
03        :=  + 
04 end loop
05 for i in 1..m loop
06       s := 
07        :=  + 
08       c := 
09       for j in 1..n loop
10             c := 
11             s := 
12              := c
13       end loop
14 end loop

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

  ε     ...
ε    0  1  2  3  ...
   1

...
s = 0
c =  = 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  := 0
02 for j in n-1..0 loop
03        :=  + 
04 end loop
05 for i in m-1..0 loop
06       s := 
07        :=  + 
08       c := 
09       for j in n-1..0 loop
10             c := 
11             s := 
12              := c
13       end loop
14 end loop

Berechnung des Alignments auf linearem Speicherplatz

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

1. Wenn oder 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 und geht man über zu Schritt 2.

2. Ein Vorwärtsdurchlauf berechnet ein Alignment von und der ersten Hälfte von (Zeilen 27 – 40). Das Ergebnis des Vorwärtsdurchlaufs ist ein Feld , dessen Elemente die Kosten für einen Durchlauf von bis (mit ) angeben.

3. Ein Rückwärtsdurchlauf berechnet ein Alignment von mit der zweiten Hälfte von (Zeilen 42 – 55). Das Ergebnis ist ein weiteres Feld , dessen Elemente die Kosten für einen Durchlauf von zurück zu angeben.

4. In den Feldelementen und stehen die beiden Levenshtein-Distanzen für die globalen Alignments von und den jeweiligen Hälften von . In den restlichen Elementen von stehen die Distanzen von der ersten -Hälfte zu allen Präfixen von . Entsprechend enthalten die restlichen Elemente von die Distanzen von der zweiten -Hälfte zu allen Suffixen von .

5. Die Levenshtein-Distanz von zu kann nun errechnet werden, indem man entlang der mittleren Zeile der Alignment-Matrix läuft und nach einer kleinsten Summe von korrespondierenden - und -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 schneidet. An dieser Stelle wird 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 und 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 -- Der Divide-&-Conquer-Algorithmus von Hirschberg zur
03 -- Berechnung des globalen Alignments auf linearem Speicher.
04 --
05 -- Bei  besitzt der Algorithmus eine Laufzeit von 
06 -- und einen Speicherverbrauch von .
07 --
08 function HirschbergAlignment(x,y : string) return A is
09        function SubAlignment(,,, : integer) return A is
10                mitte,cut : integer
11                s,c : real
12                 : array(..) of real
13        begin
14                if  or  then
15                        -- Konstruiere Matrix T für die Teil-Strings
16                        -- x(..) und y(..)
17                        -- Achtung: Nur linearer Speicherplatz erforderlich!
18                        T := ...
19                        -- Berechne triviales Alignment auf Matrix T
20                        -- in linearer Laufzeit
21                        return Alignment(T,x(..),y(..))
22                end if
23
24                mitte := 
25                -- finde ausgehend von  den minimalen Pfad
26                -- mit dem Vorwärtsalgorithmus:
27                 := 0
28                for j in .. loop
29                         := 
30                end loop
31                for i in ..mitte loop
32                        s := 
33                        c := 
34                         := c
35                        for j in .. loop
36                                c := 
37                                s := 
38                                 := c
39                        end loop
40                end loop
41                -- finde minimalen score-pfad nach 
42                 := 0
43                for j in .. loop
44                         := 
45                end loop
46                for i in ..mitte loop
47                        s := 
48                        c := 
49                         := c;
50                        for j in .. loop
51                                c := 
52                                s := 
53                                 := c
54                        end loop
55                end loop
56                -- finde den Punkt aus .. in dem der Minimale Pfad die
57                -- mittlere Zeile schneidet:
58                -- 
59                for j in .. loop
60                        if j= then
61                                cut := 
62                        elsif  then
63                                cut := j
64                        end if
65                end loop
66                -- Alignment entsteht durch Konkatenation von linkem und
67                -- rechtem Teil-Alignment:
68                return SubAlignment(,,mitte,cut)
69                                 SubAlignment(mitte,cut,,)
70        end SubAlignment
71        m,n : integer
72 begin
73        m := ; n := 
74        -- Sonderbehandlung:  ist der leere String und lässt keine Zerteilung zu:
75        if m=0 then
76                return 
77        else
78                return SubAlignment(0,0,m,n)
79        end if
80 end HirschbergAlignment

Literatur

  • 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]).
  • 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]).