Diskussion:Hirschberg-Algorithmus

Speicherbedarf

Der Speicherbedarf des Hirschberg Algorithmus zur Berechnung eines global optimalen Alignments liegt bei O(n+m) und nicht O(n). Die im Artikel angesprochene Begrenzung des Speicherbedarfs durch min{n,m} entspricht der des Needle-Wunsch Algorithmus, der die Grundage zum Hirschberg Algorithmus liefert, wenn man nur den Wert des Alignments, nicht aber das Alignment selbst berechnen will. Der Needle-Wunsch Speicherbedarf für die Berechnung eines optimalen Alignments liegt bei O(n*m), da hier die gesamte Tabelle gespeichtert werden muss.

Meiner Ansicht nach ist der Speicherbedarf von O(n) korrekt. n ist dabei die Länge der kürzeren Sequenz. Es müssen ja immer nur die letzte Matrix-Zeile (bzw Spalte) und die neu zu errechnende Zeile (bzw Spalte) im Speicher gehalten werden. Das wären 2n, also O(n). Auf diese Art und Weise wandert man durch die gesamte Matrix. Der Speicherbedarf ist also unabhängig von m. Grüße --Sulai 18:52, 22. Jan. 2008 (CET)

Im Rahmen der O-Notation ist diese Unterscheidung hinfällig, es handelt sich schlicht im lineares Wachstum der Komplexität. Des weiteren benötigt man nur eine einzige Zeile und eine Zelle im Speicher um die Berechnung in place durchzuführen.

Nur das Ergebnis benötigt O(n+m) Speicher, der Algorithmus selbst kommt mit O(n) Speicher aus. Das sind zwei Paar Stiefel. Denn sonst könnte es auch keinen in-place Sortieralgorithmus geben, da das Ergebnis ja immer O(n) Speicher benötigt. --Popelmaus (Diskussion) 17:27, 15. Jul. 2013 (CEST)

Kostenfunktion

Auf die Kostenfunktion Ins(),Del() und Sub() sollte näher eingegangen werden.

Das ist an einem Beispiel schnell erklärt: Ins, Del, Sub kann man je nach Anwendung selbst wichten. Zm Beispiel kann bei der Mutation einer biologischen DNA Sequenz Cytosin leichter durch Thymin als durch Guanin ersetzt werden. Man will ja ein biologisch wahrscheinliches Alignment finden und bestraft daher C->T weniger als C->G. Daher gibt Sub(C,T) einen geringeren Wert als Sub(C,G). --Sulai 18:52, 22. Jan. 2008 (CET)

Kostenfunktion II.

Die Levenshtein-Distanz ist fest definiert und nicht beliebig mit Ins, Del und Sub zu belegen. Sollte man lieber weglassen. Beides zusammen ist definitiv falsch.

Global vs lokal

Der Ansatz von Hirschberg ist nicht auf ein globales Alignment beschränkt, eine lokales ist ebenso möglich.

Beschreibung des Algorithmus' "Berechnung der Levenshtein-Distanz auf linearem Speicherplatz"

Mit der Beschreibung

In den Zeilen 1-4 wird das eindimensionale Feld $T$ 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. 

hab ich ehrlich gesagt kein bisschen mehr verstanden, als durch Betrachten des Algorithmus'. Was evtl hilfreich wäre, wäre eine Beschreibung, was $T$ überhaupt sein soll, und dass $Sub,Ind,Del$ Kostenfunktionen sein sollen.

Naja und der Algorithmus für die umgekehrte Richtung ist soweit ich das sehe komplett identisch, außer dass $x,y$ und $T$ von hinten durchlaufen werden. Insbesondere nach einer "Es sollte klar sein, dass" Einleitung, finde ich, sollte man ihn nicht nochmal hinschreiben ... --188.96.89.255 00:26, 21. Nov. 2009 (CET)

Berechnung des Alignments auf linearem Speicherplatz

Der Algorithmus hat an einer Stelle wenig Sinn:

In Zeile 14 wird geprüft, ob j1 = j2 ist. Wenn ja, dann gebe in Zeile 21 das Alignment mit y(j1 + 1 … j2) zurück!?

Soll die wenn-Bedingung j1 + 1 = j2 heißen?

-- Volneb83 (Diskussion) 19:53, 12. Jun. 2012 (CEST)

Es ist tatsächlich richtig. Man könnte aber auch genauer auf j1=j2 eingehen mit:

return ${\begin{pmatrix}x_{i1+1}\\-\end{pmatrix}}\star \cdots \star {\begin{pmatrix}x_{i2}\\-\end{pmatrix}}$ --Popelmaus (Diskussion) 17:46, 15. Jul. 2013 (CEST)