imported>Invisigoth67: typo

2024-09-25T14:01:50Z

typo

Neue Seite

Der '''Hirschberg-Algorithmus''' berechnet das paarweise [[Sequenzalignment]] und hat einen zur Eingabe [[Platzkomplexität|linearen Speicherbedarf]]. Der in den 1970er Jahren von [[Dan Hirschberg]] entwickelte [[Algorithmus]] verwendet die Methode der [[Dynamische Programmierung|Dynamischen Programmierung]] und das [[Teile und herrsche (Informatik)|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-Notation|O]](n) liegt. Zur Berechnung eines Alignments zweier Zeichenketten <math>x</math> und <math>y</math>
mit <math>m=|x|</math> und <math>n=|y|</math> besitzt der Algorithmus eine Laufzeit
von <math>\Theta(m n)</math> und einen Speicherverbrauch von <math>\Theta(\min\{m,n\})</math>. O.B.d.A soll im Folgenden <math>n\leq m</math> gelten, so dass der Platzbedarf in <math>\Theta(n)</math> liegt.

Anwendung findet der Algorithmus zum Beispiel in der [[Bioinformatik]] zum Abgleich verschiedener [[Desoxyribonukleinsäure|DNA]]- oder [[Protein]]sequenzen.

In einer leicht abgewandelten Form wird Hirschbergs Algorithmus auch dazu verwendet, um in einem [[Graph (Graphentheorie)|Graphen]] parallel [[Zusammenhang von Graphen|Zusammenhangskomponenten]] mit Aufwand <math>\Theta(\log^2 n)</math> auf <math>\Theta(n^2)</math> 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 <math>T_0</math> := 0
02 for j in 1..n loop
03 <math>T_j</math> := <math>T_{j-1}</math> + <math>Ins(y_j)</math>
04 end loop
05 for i in 1..m loop
06 s := <math>T_0</math>
07 <math>T_0</math> := <math>T_0</math> + <math>Del(x_i)</math>
08 c := <math>T_0</math>
09 for j in 1..n loop
10 c := <math>\min\begin{cases}s&+Sub(x_i,y_j)\\ T_j&+Del(x_i)\\c&+Ins(y_j)\end{cases}</math>
11 s := <math>T_j</math>
12 <math>T_j</math> := c
13 end loop
14 end loop

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

'''ε <math>y_1</math> <math>y_2</math> <math>y_3</math> <math>y_4</math> ...'''
'''ε''' 0 1 2 3 ...
'''<math>x_1</math>''' 1
'''<math>x_2</math>'''
'''...'''

s = 0
c = <math>T_0</math> = 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 <math>T_n</math> := 0
02 for j in n-1..0 loop
03 <math>T_j</math> := <math>T_{j+1}</math> + <math>Ins(y_{j+1})</math>
04 end loop
05 for i in m-1..0 loop
06 s := <math>T_n</math>
07 <math>T_n</math> := <math>T_n</math> + <math>Del(x_{i+1})</math>
08 c := <math>T_n</math>
09 for j in n-1..0 loop
10 c := <math>\min\begin{cases}s&+Sub(x_{i+1},y_{j+1})\\T_j&+Del(x_{i+1})\\c&+Ins(y_{j+1})\end{cases}</math>
11 s := <math>T_j</math>
12 <math>T_j</math> := c
13 end loop
14 end loop

=== Berechnung des Alignments auf linearem Speicherplatz ===
Der Divide-&-Conquer-Algorithmus von '''Hirschberg''' berechnet ein Alignment der Zeichenketten <math>|x|</math> und <math>|y|</math>, indem er Vorwärts- und Rückwärtsdurchlauf miteinander kombiniert (Zeilenangaben beziehen sich auf den
nachfolgend angegebenen Pseudocode):

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

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

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

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

5. Die [[Levenshtein-Distanz]] von <math>x</math> zu <math>y</math> kann nun errechnet werden, indem man entlang der mittleren Zeile der Alignment-Matrix läuft und nach einer kleinsten Summe von korrespondierenden <math>T^\ell</math>- und <math>T^r</math>-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 <math>x</math> schneidet. An dieser Stelle wird <math>y</math> 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 <math>x</math> und <math>y</math> 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 <math>m=|x|,n=|y|,n \leq m</math> besitzt der Algorithmus eine Laufzeit von <math>\Theta(nm)</math>
06 -- und einen Speicherverbrauch von <math>\Theta(n)</math>.
07 --
08 function HirschbergAlignment(x,y : string) return A is
09 function SubAlignment(<math>i_1</math>,<math>j_1</math>,<math>i_2</math>,<math>j_2</math> : integer) return A is
10 mitte,cut : integer
11 s,c : real
12 <math>T^\ell,T^r</math> : array(<math>j_1</math>..<math>j_2</math>) of real
13 begin
14 if <math>i_1+1=i_2</math> or <math>j_1=j_2</math> then
15 -- Konstruiere Matrix T für die Teil-Strings
16 -- x(<math>i_1+1</math>..<math>i_2</math>) und y(<math>j_1+1</math>..<math>j_2</math>)
17 -- Achtung: Nur linearer Speicherplatz erforderlich!
18 T := ...
19 -- Berechne ''triviales'' Alignment auf Matrix T
20 -- in linearer Laufzeit
21 return Alignment(T,x(<math>i_1+1</math>..<math>i_2</math>),y(<math>j_1+1</math>..<math>j_2</math>))
22 end if
23
24 mitte := <math>(i_1+i_2)/2</math>
25 -- finde ausgehend '''von''' <math>(i_1,j_1)</math> den minimalen Pfad
26 -- mit dem Vorwärtsalgorithmus:
27 <math>T^\ell(j_1)</math> := 0
28 for j in <math>j_1+1</math>..<math>j_2</math> loop
29 <math>T^\ell(j)</math> := <math>T^\ell(j-1) + Ins(y_j)</math>
30 end loop
31 for i in <math>i_1+1</math>..mitte loop
32 s := <math>T^\ell(j_1)</math>
33 c := <math>T^\ell(j_1) + Del(x_i)</math>
34 <math>T^\ell(j_1)</math> := c
35 for j in <math>j_1+1</math>..<math>j_2</math> loop
36 c := <math>\min\begin{cases}T^\ell(j)&+Del(x_i)\\s&+Sub(x_i,y_j)\\c&+Ins(y_j)\end{cases}</math>
37 s := <math>T^\ell(j)</math>
38 <math>T^\ell(j)</math> := c
39 end loop
40 end loop
41 -- finde minimalen score-pfad '''nach''' <math>(i_2,j_2)</math>
42 <math>T^r(j_2)</math> := 0
43 for j in <math>j_2-1</math>..<math>j_1</math> loop
44 <math>T^r(j)</math> := <math>T^r(j+1) + Ins(y_{j+1})</math>
45 end loop
46 for i in <math>i_2-1</math>..mitte loop
47 s := <math>T^r(j_2)</math>
48 c := <math>T^r(j_2) + Del(x_{i+1})</math>
49 <math>T^r(j_2)</math> := c;
50 for j in <math>j_2-1</math>..<math>j_1</math> loop
51 c := <math>\min\begin{cases}T^r(j)&+Del(x_{i+1})\\s&+Sub(x_{i+1},y_{j+1})\\c&+Ins(y_{j+1})\end{cases}</math>
52 s := <math>T^r(j)</math>
53 <math>T^r(j)</math> := c
54 end loop
55 end loop
56 -- finde den Punkt aus <math>j_1</math>..<math>j_2</math> in dem der Minimale Pfad die
57 -- mittlere Zeile schneidet:
58 -- <math>cut :=_{def} \mbox{argmin}_{j_1\leq j\leq j_2}(T^\ell(j)+T^r(j))</math>
59 for j in <math>j_1</math>..<math>j_2</math> loop
60 if j=<math>j_1</math> then
61 cut := <math>j_1</math>
62 elsif <math>T^\ell(j)+T^r(j)<T^\ell(cut)+T^r(cut)</math> 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(<math>i_1</math>,<math>j_1</math>,mitte,cut)
69 <math>\star</math> SubAlignment(mitte,cut,<math>i_2</math>,<math>j_2</math>)
70 end SubAlignment
71 m,n : integer
72 begin
73 m := <math>|x|</math>; n := <math>|y|</math>
74 -- Sonderbehandlung: <math>x</math> ist der leere String und lässt keine Zerteilung zu:
75 if m=0 then
76 return <math>\begin{pmatrix}-\\ y_1\end{pmatrix}\star\begin{pmatrix}-\\ y_2\end{pmatrix}\star\cdots\star\begin{pmatrix}-\\y_n\end{pmatrix}</math>
77 else
78 return SubAlignment(0,0,m,n)
79 end if
80 end HirschbergAlignment

== Literatur ==
* {{Literatur
|Autor=D. S. Hirschberg
|Titel=A linear space algorithm for computing maximal common subsequences
|Sammelwerk=Communications of the ACM
|Band=18
|Nummer=6
|Datum=1975
|Seiten=341-343
|Sprache=en
|Online=https://www.ics.uci.edu/~dan/pubs/p341-hirschberg.pdf
|Format=PDF
|KBytes=}}
* {{Literatur
|Autor=Chao, K.M., Hardison, R.C. and Miller, W.
|Titel=Recent developments in linear-space alignment methods: a survey
|Sammelwerk=Journal of Computational Biology
|Nummer=4
|Datum=1994
|Seiten=271–291
|Sprache=en
|Online=https://www.csie.ntu.edu.tw/~kmchao/papers/1994_JCB.pdf
|Format=PDF
|KBytes=}}

[[Kategorie:Algorithmus]]
[[Kategorie:Bioinformatik]]
[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Parallelverarbeitung|Parallele Programmierung]]

Hirschberg-Algorithmus - Versionsgeschichte

imported>Invisigoth67: typo