Diskussion:Needleman-Wunsch-Algorithmus

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Needleman-Wunsch-Algorithmus“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Fehler im Beispiel?

Nach mehrfacher Betrachtung und der Tatsache, dass bei D(i, j) das i für die Zeile und das j für die Spalte steht, müsste im Beispiel bei 2. Schritt: Berechnung von D(1,2): nicht statt des C ein G im 1. und 3. Fall der Maximums-Funktion stehen? --crush 11:04, 11. Jan. 2010 (CET)

Ja, sehe ich auch so. --Gms 23:12, 11. Jan. 2010 (CET)

Beispiel

Vielleicht wäre es an dieser Stelle günstiger eine Gap nicht mit 0 sondern mit einer negativen Zahl zu bewerten, da der Smith-Waterman-Algorithmus (lokales Alignment) sich vom Needleman-Wunsch ja nur dadurch unterscheidet, dass statt negativen Zahlen 0er geschrieben werden. Durch dieses Beispiel wird es schwieriger den Unterschied zwischen lokalem und globalem Alignment herauszuarbeiten.

Ist ein guter Vorschlag. Wenn ich Zeit habe arbeite ich das Beispiel um. Dennis G. 20:19, 26. Apr 2005 (CEST)

Verstädnisfrage zur Bewertungsfunktion ??

Stimmt die folgende Ausage aus Artikel: "Die einfachste Bewertungsfunktion, die man sich vorstellen kann, gibt bei Gleichheit 1 zurück, ansonsten wird 0 zurückgegeben. Dabei werden also Substitutionen, Insertionen oder Deletionen geduldet und nicht bestraft."

Müsste es statt dessen nicht so heisen ... Dabei werden also Substitutionen, Insertionen oder Deletionen nicht geduldet und bestraft.

Um Substitutionen, Insertionen oder Deletionen nicht zu bestrafen müsste die Bewertungsfunktion ja in diesen Fällen auch 1 zurückliefern???

Bei einer Bestrafung müsste meiner Meinung nach die Bewertungsfunktion -1 zurückliefern. Da durch 0 die Bewertung nicht verändert wird, finde ich, dass "dulden" passt.

--87.122.46.149 00:34, 11. Jul 2006 (CEST)

Beispiel komisch

Ich find es komisch das im Beispiel in der Matrix D in der 1. Zeile und der 1. Spalte die Sequenzen stehen davon war in der Beschreibung nie die Rede. Ich gehe mal davon aus das wurde nur gemacht damit man es besser nachvollziehen kann und die gehören da garnicht hin.

Die gehören da wirklich nicht hin das ist nur verwirrend und hilft überhaupt nicht. Ich werde das Beispiel umschreiben.

Nachtrag: Wenn man es mal verstanden hat ist die Beschriftung ja ganz nett. Aber sie muss auf jeden Fall aus der Matrix raus.

Habt schon recht mit den Buchstaben, aber als ich den Artikel konzipert hatte fand ichs noch sinnvoll. Jetzt sind sie weg, bis auf ein Beispiel zur Anschauung.

Andere Frage: Traut ihr euch nicht eure Signatur zu hinterlassen, oder mal nen Namen? Das ist sonst alles so unpersönlich hier.

Dennis G. 00:10, 15. Jul 2006 (CEST)

Speicher-Komplexität

10.000 * 10.000 * 4 B = 400 * 10^6 B oder? Also ca. 381 MB, nicht 95 MB

Jo hatte die 4 Byte vergessen hast recht. Danke an Unbekannt.

Dennis G. 13:14, 29. Sep 2005 (CEST)

Probleme Abschnitt loeschen

"Durch die Konstruktion des Algorithmus in der dargestellten Weise ist es nicht möglich die längste übereinstimmende Teilsequenz beider Sequenzen zu finden. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman einige Modifikationen am Needleman-Wunsch-Algorithmus vorgeschlagen, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt."

Ich wuerde diesen Abschnitt komplett loeschen, da er falsch ist. Denn mit dem SW-Algorithmus sucht man noch dem lokalen Alignment, also nach einem Substring in der einen Sequenz und einem Substring der anderen Sequenz, welcher den groessten Alignmentscore hat. Das muss nicht die laengste uebereinstimmende Teilsequenz beider Sequenzen (=longest common substring) sein. --Gms 21:33, 7. Jan. 2007 (CET)

Überarbeiten-Baustein eingefügt

Der hier unten genannte Algorithmus hat größere Ähnlichkeit mit Waterman-Smith-Beyer als mit Needleman-Wunsch und bedarf daher dringend einer Überarbeitung.

Woran machst du das fest? Hast du Literatur, die deine Aussage belegt? Hast du die in dem Artikel referenzierten Quellen konsuliert?

P.S.: Naechstes mal bitte die Beitraege auf der Diskussionsseite 'unterschreiben'.

--Gms 18:05, 14. Nov. 2007 (CET)

Da keine Diskussion bis jetzt statt fand, entferne ich wieder den Überarbeitungsbaustein. Ich beobachte diese Diskussion, so dass Du auch weiterhin hier antworten kannst (ohne direkt wieder einen Überarbeitungsbaustein einfügen zu müssen ...). --Gms 16:21, 12. Dez. 2007 (CET)

Komplexität

1

Wieso ist die Komplexität nicht O(n*m) da doch nur n*m Matrixelemente betrachtet werden müssen und dann jeweils etwas mit konstanter Zeit ausgeführt wird? Für mich würde das mehr Sinn machen; auch der Smith-Waterman-Algorithmus ist mit O(n*m) angegeben... Gruss --hroest 07:16, 7. Mär. 2008 (CET)

Ein Matrixelement kann eben nicht in konstanter Zeit berechnet werden, da im Falle der Deletion bzw. Insertion über k-Zeilen bzw. l-Spalten optimiert wird. Und diese innere Optimierung ist in $O(max(n,m))$. Deshalb 'funktioniert' der NW-Algorithmus ja auch mit beliebigen Gapkosten - im Gegensatz zum Smith-Waterman.

P.S.: Die Siehe auch Verweise von SW zu NW sind nicht notwendig, da schon im Text jeweils NW <-> SW verlinkt wird. Gruß --Gms 10:06, 7. Mär. 2008 (CET)

2

habe gerade die Speicherfunktion von O() auf S() geändert. Quelle wäre (m)ein Skript aus dem Fach Theoretische Informatik. Reicht die Behauptung oder soll ich eine Quelle raussuchen. --Tukaram 12:14, 26. Mai 2010 (CEST)

Das Symbol $O$ soll ein Landau-Symbol sein! Also bitte nicht ändern! Wenn irgendein (!) Script ein S verwendet, ist das nicht wirklich relevant. --Gms 23:19, 8. Jun. 2010 (CEST)

3

Es müssen $m\cdot n$ Elemente der Matrix berechnet werden, und für jedes Element muss über ${\mathcal {O}}(n)+{\mathcal {O}}(m)$

Hier ist O(n)+O(m) IMO unschön. Es müsste lautet

Es müssen $m\cdot n$ Elemente der Matrix berechnet werden, und für jedes Element muss über $n+m$ ...

Begründung: Der Text begründet, warum die O()-Funktion so aussieht wie sie aussieht, stellt selbst aber keine O() Funktion mehr dar.--Tukaram 12:14, 26. Mai 2010 (CEST)

Die $O$-Notation ist in der Informatik absolut üblich. Siehe auch Artikel Landau-Symbole. --Gms 23:19, 8. Jun. 2010 (CEST)

Affine Gap-Kosten

Affine Gap-Kosten werden meiner Meinung nach nicht im grundlegenden Needleman-Wunsch-Algorithmus berechnet.

Das hat zum Glück nichts mit Meinung zu tun. Es geht darum was die Autoren des Algorithmus in ihrem Paper geschrieben haben. --Gms 18:59, 24. Apr. 2008 (CEST)

Man sollte hier die einfache Version (die dann auch O(n*m) hat) auf alle Fälle mit angeben, im übrigen ist die Berechnung der affinen Gap-Kosten nach dem Schema auch nicht sehr relevant, da dann eher der Gotoh-Algorithmus benutzt wird.

Es geht ja nicht nur um affine oder einheitliche Gap-Kosten. Der Punkt ist ja gerade, dass man mit Needlemann-Wunsch-Algorithmus eine beliebige Gap-Kostenfunktion verwenden kann. P.S.: Beim nächsten Mal bitte Beiträge auf der Diskussionsseite unterschreiben! --Gms 18:59, 24. Apr. 2008 (CEST)

Die hier dargestellte Version hat jedenfalls nix mit dem Paper zu tun. Was hier als Needleman-Wunsch-Algorithmus beschrieben wird ist so nicht im Originalartikel beschrieben. Alles was darin in die Richtung geht, ist ein von den Autoren schwammig formulierter Satz. "The penalty factor could be a function of the size and/or direction of the gap." Hingegen ist eindeutig zu lesen: "In the simplest method, MATij is assigned the value, one, if Aj is the same kind of amino acid as Bi; if they are different amino acids, MATij is assigned the value, zero." Dazu ist sogar ein Beispiel mit Matrizen aufgelistet. Somit ist also klar, welche Matrix-Rekurrenzen hier beschrieben werden sollte. Ich stimme natürlich zu, dass jede beliebige gap-Kostenfunktionen möglich ist, aber eine spezielle gap-Kostenfunktionen als Grundlage zu nehmen, um Unwissenden den Algorithmus erklären zu wollen, ist einfach nicht zielführend. --gezeichnet XXX 00:55, 18. May. 2008 (CEST)

Wenn du aus der Literatur zitierst, dann zitiere doch bitte im Zusammenhang. Also in diesem Abschnitt des Needleman-Wunsch-Papers von 1970 heißt es: '[..] In the simplest method, MATij is assigned the value, one, if Aj is the same kind of amino acid as Bi; if they are different amino acids, MATij is assigned the value, zero, The sophistication of the comparison is increased if, instead of zero or one, each cell value is made a function of the composition of the proteins, the genetic code triplets representing the amino acids, the neighboring cells in the arrray, or any theory concerned with the significance of a pair of amino acids. A penalty factor, a number substracted for every gap made, may be assessed as a barrier to allowing the gap. The penalty factor could be a function of the size and/or direction of the gap. No gap would be allowed in the operation unless the benefit from allowing that gap would exceed the barrier. The maximum-match pathway then, is that pathway for which the sum of the assigned cell values (less any penalty factors) is largest. [..]'

In diesem Abschnitt wird zum einen klar zwischen der Behandlung von (Mis-)Matches und Gaps differenziert. Der zweite von Dir zitierte und als 'eindeutig' bezeichnete Satz bezieht sich auf die Behandlung von (Mis-)Matches. Der erste von Dir zitierte Satz, den du als 'schwammig' formuliert bezeichnest, ist doch eine eindeutige Beschreibung welche Gapkostenfunktionen bei diesem DP-Algorithmus verwendet werden können.

Unabhängig hiervon - allgemeine Gapkosten sind ja nicht irgendeine sinnfreie Konstruktion um Artikelleser zu ärgern. Ein Beispiel für eine allgemeine Gapkostenfunktion ist eine logarithmische Gapkostenfunktion - sie wird für bestimmte Anwendungen als biologisch sinnvoller betrachtet, als z.B. die Verwendung von affinen oder einheitlichen Gapkosten.

Desweiteren verstehe ich wirklich nicht, wo das Problem ist. Denn die Idee der Berücksichtigung von Gaps beliebiger Länge (und nicht nur eine Erweiterung um eine Einheit) in der Rekursion wird in der textuellen Beschreibung des Verfahren ausreichend erklärt. Wenn ich Needleman-Wunsch implementieren möchte, mich aber nur einheitliche Kosten interessieren, dann macht natürlich die triviale Optimierung bei der Behandlung von Gap-Erweiterungen Sinn. Aber genau darauf wird ja auch explizit in dem Abschnitt 'Abgrenzung' eingegangen.

Abgesehen davon wird durch die Berücksichtigung von beliebigen Gapkosten das Verständnis des Algorithmus nicht erschwert. Im Gegenteil: Einheitliche Gapkosten sind ein Spezialfall, der schwerer zu verstehen ist - denn der Leser muss erstmal verstehen, warum man zum Zeitpunkt der Auswertung einer beliebigen Zelle i,j man nur eine Zelle für einen Gap-fall betrachten muss, obwohl ja Gaps beliebiger Länge in der aktuellen Zelle enden können.

PS: Mit der WP-Unterschrift ist folgendes gemeint: Hilfe:Signatur - denn so eine Pseudo-Unterschrift wie von Dir verwendet könnte ja schon als gefälschte Unterschrift durchgehen.

--Gms 13:06, 18. Mai 2008 (CEST)

Wegen der massiven Änderungen von gestern und heute die aus dem Alice-DSL-Netz kommen: Rückgängig gemacht aus foglenden Gründen:

• Verfahren: komplette Entfernung von Backtracking aus der Highlevel-Vorbesprechung des Algorithmus
• unnötige Vergrößerung des Artikels: weitere Rekurrenzen für einen Spezialfall - für Argumente dagegen, siehe vorherigen 'Thread'
• die Rekurrenzen des Spezialfalls sind nicht verwendbar für lineare Gapkosten
• Komplexitätsbetrachtung: redundant zur Abgrenzung O(n^3) vs. O(n^2)
• bei linearen Gapkosten ist nicht eine Laufzeit von O(n^2) mit diesem Algorithmus möglich, denn es gibt einen Unterschied zwischen linearen und einheitlichen Kosten!
• Backtracking hat keinen linearen Mehraufwand!
• Komplexität: es wird auf eine Hilfsmatrix ohne weitere Erklärung eingangen
• Komplexität: Mischung von asymptotischer und nicht-asymptotischer Speicherbedarfbetrachtung
• Siehe auch: Eintrag ist schon im Artikel verlinkt

Ich gehe jetzt einfach mal davon aus, dass die Diskussionsbeiträgen in dieser Diskussion, die aus dem Alice-DSL Netz und den Artikel-Änderungen aus dem Alice-DSL Netz, von dem gleichen Autor kommen. Also an Mr. anonym bzw. XXX: Was ist das bitte für ein Diskussionsstil, wenn einem die Argumente ausgehen, einfach Diskussion abbrechen und dann trotzdem einfach massiv in der diskutierten Art und Weise den Artikel ändern? --Gms 08:31, 20. Mai 2008 (CEST)

Offensichtlich hast du dir nicht einmal durchgelesen, was du gelöscht hast....traurigtraurig Zu deinen Punkten:

• Verfahren: komplette Entfernung von Backtracking aus der Highlevel-Vorbesprechung des Algorithmus

Ja genau, es ist ja viel schlechter ein neuen Kapitels anzulegen...es ist ja auch gleich viel schöner, wenn einen nur Backtracking interessiert und man erst den ganzen Artikel lesen muss, um die Stelle zu finden...echt prima

• unnötige Vergrößerung des Artikels: weitere Rekurrenzen für einen Spezialfall - für Argumente dagegen, siehe vorherigen 'Thread'

Der Fall, den du hier immer als Spezialfall ansprichst, ist weithin als _der_ Needleman-Wunsch-Algorithmus bekannt, wird so an Universitäten gelehrt und in Büchern beschrieben. wenn du das schon nicht akzeptierst, solltest du ihn wenigstens im artikel mit seinen rekurrenzen akzeptieren.

• die Rekurrenzen des Spezialfalls sind nicht verwendbar für lineare Gapkosten

genau das sind sie, sie sind nicht eben _nicht_für einheitliche...tzzzz

• Komplexitätsbetrachtung: redundant zur Abgrenzung O(n^3) vs. O(n^2)

was ist redundant, wenn man dem geneigten wissensbedürftigen Menschen erklärt, warum doch O(nm) möglich ist, so wie er es gelesen/in der Vorlesung gehört hat

• bei linearen Gapkosten ist nicht eine Laufzeit von O(n^2) mit diesem Algorithmus möglich, denn es gibt einen Unterschied zwischen linearen und einheitlichen Kosten!

den gibt es zwar, aber ich hatte die linearen beschrieben...linear=aufsummieren aller zeichen eines gaps.

als einheitlich verstehst du wohl -eine lücke=kosten egal wie lang, und das habe ich _nicht_ beschrieben.

• Backtracking hat keinen linearen Mehraufwand!

Natürlich, wenn ich den Pfad zurückrechne habe ich linearen Mehraufwand.

• Komplexität: es wird auf eine Hilfsmatrix ohne weitere Erklärung eingangen

haha...die war ja schon erwähnt, ich hab es nur noch etwas genauer beschrieben. Aber schön dass du auch das gelöscht hast, nun versteht man es wieder gar nicht. Im übrigen ist Backtracking, wie man es eigentlich betreibt...also mit LINEAREM MEHRAUFWAND nun gar nicht mehr erwähnt, nur noch die Variante, die man in der Praxis gar nicht benutzt. großes lob!

• Komplexität: Mischung von asymptotischer und nicht-asymptotischer Speicherbedarfbetrachtung

wow...naja, ich versteh zwar, dass die hilfsmatrix im aufwand untergehen *kann*. ich will mich hier auch nicht zu sehr vertiefen, dem leser sollte aber aufgezeigt werden, wieso man sich den Speicherplatz sparen kann, wenn man MIT LINEAREM MEHRAUFWAND zurückrechnet.und ob das nun untergeht oder nicht, man kann speicherplatz sparen, und das zählt in der bioinformatik.

• Siehe auch: Eintrag ist schon im Artikel verlinkt

hier habe ich den Link vom "smith-waterman" durch den link zu "alignments" ersetzt. ich habe siehe-auch nicht erfunden...nun hastes ganz gelöscht, auch toll.

Und was soll das eigentlich mit der java-2gb-begrenzung? was hat java jetzt mit needleman-wunsch zu tun? NICHTS!

zusammengefasst merkt man, dass die derzeitige version nichts mit der praxis zu tun hat. wenn man den needleman-wunsch benutzt, dann nicht so wie hier beschrieben. man benutzt keine affinen gap-kosten und keine hilfsmatrix. den artikel kann man sich also eigentlich auch sparen. --hier fehlt wieder die Unterschrift

Hallo anonymer der-sich-weigert-seine-Beiträge-zu-unterschreiben,

wenn man in einer Diskussion der Gegenüber eine andere Meinung vertritt, dann muss man doch nicht gleich persönlich werden. Und nochmals: Es ist aus Gründen der Übersichtlichkeit üblich bei Wikipedia die Beiträge auf den Diskussionsseiten zu unterschreiben. Warum weigerst du dich so hartnäckig dagegen? Auch wiederhole ich mich wenn ich schreibe, dass es ein sehr schlechter Diskussionsstil ist, einfach massiv die in der Diskussion zur Debatte stehenden Punkte im Artikel zu ändern, wenn offensichtlich die Kritikpunkte noch nicht ausgeräumt sind.

Zu deiner Replik:

• die Vorsprechung ist nicht der ganze Artikel, sie dient der Übersicht über den Algorithmus, ohne ihn zu detailliert zu Beschreiben - also gehört dort ein Verweis auf das Backtracking
• 'ist weithin als _der_ Needleman-Wunsch-Algorithmus bekannt, wird so an Universitäten gelehrt und in Büchern beschrieben. wenn du das schon nicht akzeptierst, solltest du ihn wenigstens im artikel mit seinen rekurrenzen akzeptieren.' - das Original-Paper ist eindeutig, wenn in manchen Vorlesungen es anders gemacht wird, ist das noch kein Argument. Z.B. in mehreren Vorlesungen, die ich gehört habe, wurde der Needleman-Wunsch-Algorithmus in der Form eingeführt, wie er auch im Paper beschrieben wird.
• 'was ist redundant, wenn man dem geneigten wissensbedürftigen Menschen erklärt, warum doch O(nm) möglich ist, so wie er es gelesen/in der Vorlesung gehört hat'

in der Abgrenzung wird ja schon auf den Spezialfall eingegangen: das ist die Redundanz. Außerdem handelt es sich hier um einen Artikel in einer Enzyklopädie; ab einem Übermaß an Details zu einem Spezialfall sind diese Details nicht mehr enzyklopädisch relevant - im Gegensatz zu einer Vorlesungsmitschrift

• Unterschied linear/einheitlich: 'den gibt es zwar, aber ich hatte die linearen beschrieben...linear=aufsummieren aller zeichen eines gaps. als einheitlich verstehst du wohl -eine lücke=kosten egal wie lang, und das habe ich _nicht_ beschrieben.'

Das ist falsch. Gapkosten sind linear wenn sie durch eine lineare Funktion beschrieben werden können, wobei die Bezeichnung lineare-Gapkosten eher unüblich ist, und man eher lineare-Gapkosten als affin bezeichnet. Von einheitlichen Gapkosten spricht man, wenn ein Indel bzw. Mismatch gleichviel kosten. Und du beschreibst eben nicht die Berechnung der Matrix bei linearen Gapkosten.

• Aufwand beim Backtracing - 'Natürlich, wenn ich den Pfad zurückrechne habe ich linearen Mehraufwand' Der NW-Algorithmus ist in O(n^3), das Backtracing ohne Betrachung von co-optimalen Alignments in O(n^2), also Gesamtlaufzeit in O(n^3) - bei optimierung auf einheitliche Gapkosten ist die Gesamtlaufzeit in O(n^2), wo siehst du da den linearen Mehraufwand?
• 'haha...die war ja schon erwähnt, ich hab es nur noch etwas genauer beschrieben. Aber schön dass du auch das gelöscht hast, nun versteht man es wieder gar nicht. Im übrigen ist Backtracking, wie man es eigentlich betreibt...also mit LINEAREM MEHRAUFWAND nun gar nicht mehr erwähnt, nur noch die Variante, die man in der Praxis gar nicht benutzt. großes lob!'

Kein Grund schnippisch zu werden. Wir sind hier bei Wikipedia und man kann hier auch ruhig und sachlich diskutieren. Punkt ist: Das Backtracking-per-Hilfsmatrix ist deswegen exemplarisch angeführt, damit der Leser eine Idee von dem Backtracking-Prozess bekommt. Denn es einfach per Papier-und-Bleispiel nachvollziehbar (entspricht der Annotierung der Matrix mit Pfeilen). Der Artikel beschreibt ja den grundlegenden Algorithmus. Eine vollständige Abhandlung über alle möglichen Backtracking-Verfahren und Varianten ist nicht WP-relevant.

• Komplexität, Vermischung asymptotische vs. nicht-asymptotische Betrachtung: 'wow...naja, ich versteh zwar, dass die hilfsmatrix im aufwand untergehen *kann*. ich will mich hier auch nicht zu sehr vertiefen, dem leser sollte aber aufgezeigt werden, wieso man sich den Speicherplatz sparen kann, wenn man MIT LINEAREM MEHRAUFWAND zurückrechnet.und ob das nun untergeht oder nicht, man kann speicherplatz sparen, und das zählt in der bioinformatik.' Komplexitätsbetrachtungen sind per Definition asymptotische Betrachtungen, da kann man nicht einfach schwammig 'verdoppeln' in Anführungszeichen setzen. Zu 'LINEAREM MEHRAUFWAND' siehe oben. Wenn die Implementationsdetails WP-relevant währen, dann müsste man sie in einen extra Abschnitt Implementationsdetails unterbringen. Abgesehen davon kommt man ja auch durch eine Optimierung des auf O(n)-Speicher. Soll man darauf in Details auch in diesem Abschnitt eingehen, weil es 'in der bioinformatik zählt'?
• 'zusammengefasst merkt man, dass die derzeitige version nichts mit der praxis zu tun hat.' - selbst wenn das stimmen würde, relevant für diesen WP-Artikel ist der grundlegene NW-Algorithmus. Abgesehen davon, siehe auch in meinen vorherigen Beitrag die Bemerkung zu logarithmischen Kostenfunktionen

Also wegen der gesammelten Fehler und Unstimmigkeiten stelle ich den Status vor dem Beginn der Diskussion wieder her.

Und nochmals, nimm das bitte nicht persönlich, sondern diskutiere mögliche noch bestehende Fragen zu diesem zur Debatte stehenden Komplex vorher hier auf dieser Seite. --Gms 20:54, 21. Mai 2008 (CEST)

Hach das wird aber langsam mühsam.

• Zum Backtracking. ich hab ja nix dagegen, dass es da oben (kurz) erwähnt ist.

aber man kann doch hier ein eigenes Kapitel (oder wie auch immer das hier genannt wird) aufmachen und es da reinschreiben. und zwar beide Möglichkeiten und ausführlich. was spricht da jetzt dagegen? dann findet man es auch sofort, wenn man nur nach backtracking sucht und den rest schon verstanden hat. ohne backtracking ist der algorithmus sinnlos für den leser, da dann die hälfte fehlt.es sei denn er sucht nur den score/distanz.

• lineare gapkosten sind genau das, was ich beschrieben habe.

sonst werden sie als "affine lineare Gap-Kostenfunktion" bezeichnet zum Verständnis: gap der Länge l, distanzfunktion ist:

linear: d(l) = c * l

affin linear: d(l) = c*l + d

einheitlich: wahrscheinlich das, was du beschrieben hast. bei mir hatten aber mismatch und gap eindeutig unterschiedliche bewertungen (match/mismatch werte aus w(a,b) und deletion/insertion durch g(i) bewertet) Da es nur 2 backtrackingverfahren gibt, ufert es ja wohl nicht aus, wenn man diese beschreibt.

• linearer mehraufwand

hier habe ich nie O(nm) oder deine O(n^3) bestritten man muss doch aber den Mehraufwand, der nun einmal durch das backtracking entsteht, auch angeben können. wenn es hilft muss man backtracking eben getrennt betrachten. dies soll ja nur zeigen, dass man durch praktisch vernachlässigbaren mehraufwand die hilfsmatrix sparen kann.und dass es mehraufwand gibt, ist ja unbestreitbar. ich verstehe hier deine frage nicht, so wie du argumentierst könnte man fragen, wieso dann hilfsmatrix, wenn es doch gar keinen mehraufwand gibt?

• da wären wir beim nächsten punkt. hilfsmatrix

sie ist erwähnt aber in keinster weise definiert. wer sich über den algorithmus informiert und ihn tatsächlich implementieren will, scheitert hier. siehe oben-für den leser fehlt die hälfte wieso ist es nicht erlaubt zu erwähnen, dass hier nunmal doppelt so viel speicher verbraucht wird. und das ist in keinster weise unrelevant, auch wenn wir immer noch in O(nm) sind!

• zu dem was viele andere als _den_ Needleman-Wunsch kennen

Wenn du es schon nicht als _den_ Needleman-Wunsch ansiehst, dann könnte man wenigstens damit das Beispiel-Kapitel füllen. dann sieht auch jeder, warum es in O(nm) liegen _kann_ und alle sind glücklich. ich weiß, das jetzige beispiel ist auch O(nm) aber naja...+1 und -1 ist doch ein wenig witzlos

'Hach das wird aber langsam mühsam' - was soll ich da erst sagen? Ich würde meine Zeit auch lieber produktiv in wichtige neue Wikipedia-Artikel oder interessante Änderungen investieren, als ellenlang mit einem anonymous auf der Diskussionseite zu diskutieren, der anscheinend nicht in der Lage ist minimalst seine Behauptungen durch Quellen zu belegen oder sich über grundlegende Abläufe bei Wikipedia zu informieren (z.B. Beiträge unterschreiben, Was ist relevant bei WP, was ist wp nicht, ...).

• 'Zum Backtracking. ich hab ja nix dagegen, dass es da oben (kurz) erwähnt ist.

aber man kann doch hier ein eigenes Kapitel (oder wie auch immer das hier genannt wird) aufmachen und es da reinschreiben. und zwar beide Möglichkeiten und ausführlich. was spricht da jetzt dagegen?'

Dagegen spricht, dass Wikipedia eine Enzyklopädie ist und keine detailierte Implementationsanleitung für Algorithmen.

• 'dann findet man es auch sofort, wenn man nur nach backtracking sucht und den rest schon verstanden hat.

ohne backtracking ist der algorithmus sinnlos für den leser, da dann die hälfte fehlt.es sei denn er sucht nur den score/distanz.'

Der Artikel ist nicht sinnlos ohne die Erwähnung aller Implementationsdetails, da auf das Prinzip des Backtracking high-level-artig eingegangen wird. Irgendwann sind in einem Artikel zu umfangreiche Details nicht mehr relevant für diesen konkreten Artikel und lenken ausserdem Nicht-Experten bei dem Erstverständnis vom Wesentlichen ab.

Sinnvoller scheint es mir, den Backtracking-Artikel um konkrete Beschreibungen verschiedener allgemeingültiger Backtracking-Schemata in DP-Algorithmen zu erweitern. Denn sonst müssten ja in jedem DP-Algorithmus-Artikel redundant alle möglichen Backtracking-Schemata beschrieben werden ...

• 'hier habe ich nie O(nm) oder deine O(n^3) bestritten

man muss doch aber den Mehraufwand, der nun einmal durch das backtracking entsteht, auch angeben können. wenn es hilft muss man backtracking eben getrennt betrachten. dies soll ja nur zeigen, dass man durch praktisch vernachlässigbaren mehraufwand die hilfsmatrix sparen kann.und dass es mehraufwand gibt, ist ja unbestreitbar. ich verstehe hier deine frage nicht, so wie du argumentierst könnte man fragen, wieso dann hilfsmatrix, wenn es doch gar keinen mehraufwand gibt?'

Du hast die Laufzeiten 'bestritten' in dem du mit den 'falschen' Fachbegriffen in dem unpassenden Abschnitt 'Komplexität' den Mehraufwand falsch beschrieben hast. Also nochmal, wenn das Backtracking in O(n^2) ist und die Berechnung der Matrix in O(n^3), dann ändert sich die konstanten Faktoren der Gesamtlaufzeit von O(n^3). Also ist der Mehraufwand konstant und eben nicht linear. Und dieser konstante Faktor ist natürlich unterschiedlich groß, je nachdem welches Backtracking-Schema verwendet wird, wie die restliche Implementation aussieht, welche Programmiersprache, welcher Compiler, was für ein Rechner verwendet wurde usw. Man könnte natürlich in einem anderen Abschnitt a la 'Implemenationsdetails' erwähnen, dass der konstante Faktor beim Mehraufwand durch Hilfsmatrix 'so und so' ist, bei einem anderen Schema oder ohne Backtracing 'anders' ist. Aber das wäre ja die absolute Binse. Wenn ich eine quadratische Hilfsmatrix habe, dann habe ich natürlich konstant mehr Aufwand, wenn mein Algorithmus schon in O(n^3) oder im Spezialfall in O(n^2) ist.

Das alles sind ja auch keinen zentralen Merkmale des NW-Algorithmus. Und eben nicht relevant für diesen konkreten Artikel.

• 'hilfsmatrix

sie ist erwähnt aber in keinster weise definiert. wer sich über den algorithmus informiert und ihn tatsächlich implementieren will, scheitert hier. siehe oben-für den leser fehlt die hälfte wieso ist es nicht erlaubt zu erwähnen, dass hier nunmal doppelt so viel speicher verbraucht wird. und das ist in keinster weise unrelevant, auch wenn wir immer noch in O(nm) sind!'

Du musst unterscheiden zwischen 'relevant für eine Impelementierung des NW-Alg.' und WP-Relevanz bzw. Relevanz für diesen konkreten Artikel. Wie gesagt, WP ist kein Ersatz für ein Vorlesungsskript oder ein Lehrbuch, welches sich mit Implementationsdetails zu bestimmten Algorithmus umfassend auseinander setzt. Es gibt z.B. nebenan das Schwesterprojekt Wikibooks ...

• 'ich weiß, das jetzige beispiel ist auch O(nm) aber naja...+1 und -1 ist doch ein wenig witzlos' - witzlos ... - ist es mit +23 und -42 witziger? Oder spaßiger mit 32.42 log_10 x ^ 2 + 42.23 log_10 x für die Gapkosten? Das Beispiel soll ja möglichst übersichtlich sein ... so von wegen per Papier und Bleistift nachrechnen ...

• wegen den Gapkosten ... du bist dir so sicher das 'lineare gapkosten sind genau das, was ich beschrieben habe.' Wie kommt das? Ich habe nochmal etwas in der Literatur nachgeschaut, und es gibt wohl kein eindeutiges Paper/Quelle, in der allgemein anerkannt die verschiedenen Fachbegriffe definiert sind.

Z.B. Durbin verwendet 'linear' für Gapkosten, welche durch eine Funktion 'f(x) = x b' beschrieben werden können. f ist eine lineare Funktion, aber 'g(x) = a + x b' ist auch eine lineare Funktion und Gapkosten die durch g beschrieben werden, bezeichnet Durbin allerdings als 'affine'. Gusfield geht darauf ein, dass 'affine' für Gapkosten wie durch g beschrieben weiter verbreitet ist in der Community als die Bezeichnung 'linear'. Aber es gibt auch einen Teil der Community die eben g als 'linear'-Gapkosten-fn bezeichnet. Einheitliche Gapkosten sind wie f definiert, und die Mismatches können anders gewichtet werden, da hatte ich mich oben verschrieben. Damals hatte ich in dem Artikel 'einheitlich' verwendet, um die Konfusion um 'linear wie g' vs. 'linear wie f' zu vermeiden. Also einheitlich in dem Sinne, dass jede Stelle einer Lücke gleichviel zu dem Wert einer Lücke einer gegebenen Länge beiträgt.

Also, ich würde sagen: Die Konfusion und die aufgezählten Aspekte der verschiedenen Gapkosten-Schemata zeigen, dass WP ein eigenen Artikel über Gapkosten braucht. --Gms 23:17, 26. Mai 2008 (CEST)

Abgrenzung zum Waterman-Smith-Beyer-Algorithmus

Es gibt Auffassungen nach denen dieser Wikipedia-Artikel den Waterman-Smith-Beyer-Algorithmus beschreibt. Offensichtlich wurden an dieser Stelle bereits ähnliche Überschneidungen diskutiert. Deswegen möchte ich gerne alle Interessenten die sich mit dem Needleman-Wunsch-Algorithmus auskennen zu der dortigen Diskussion einladen. Ziel ist es, sich auf eine Abgrenzung zu einigen, damit ein neuer Artikel entstehen kann: Diskussion:Waterman-Smith-Beyer-Algorithmus

__AlienR 12:57, 27. Nov. 2009 (CET)

Einleitung unverständlich

Hallo, m.E. ist die Einleitung unverständlich und für die Allgemeinheit der Leserschaft (vgl. WP:OMA) unbrauchbar. Erst wer affin mit dem Thema ist, wird auch den einleitenden Satz verstehen können. Auch aus dem Rest des Artikels erschließt sich einem allgemeinen Leser keinesfalls der Artikelgegenstand. Insofern wünschte ich mir eine Überarbeitung. Grüße -- René Schwarz 18:47, 22. Sep. 2010 (CEST)

Hm, vermutest du, das die Einleitung für den Otto-Normal-Leser unverständlich ist oder schätzt du dich als ein solcher ein, und kannst mit der Einleitung nichts anfangen?

In der Einleitung ist ja schon auf den Alignment-Artikel verlinkt. Hilft deiner Meinung nach die Kenntnisnahme des Alignment-Artikels beim Verständnis der Einleitung? --Gms 21:26, 24. Sep. 2010 (CEST)

Ich habe von der Einleitung nichts verstanden, von daher tauge ich hier wohl als Otto-Normal-Leser. In welches Fachgebiet gehört der Algorithmus denn - Mathematik, Informatik, Wirtschaftswissenschaften? Gibt es ein allgemein zugängliches Beispiel wofür der Algorithmus gut sein kann? (Ich meine, auch für Leute die nicht wissen, wer die Gap-Kosten am Ende bezahlen muss ...)

Vielleicht hilft der Alignment-Artikel ja weiter, aber ich denke, ein Artikel sollte aus sich selbst heraus dem Leser eine grobe Orientierung geben. --J.Ammon 06:18, 3. Feb. 2011 (CET)

Und, hilft der Sequenzalignment-Artikel? Der Needleman-Wunsch-Algorithmus ist nah verwandt mit dem Smith-Waterman-Algorithmus - wie ist die Meinung zu der dortigen Einleitung? Die Einleitung in diesem Artikel könnte man analog aufziehen. --Gms 23:20, 17. Feb. 2011 (CET)

Ich war zwar nicht gefragt, glaube aber auch, dass die Einleitung nicht OMA-tauglich ist. (Die des Smith-Waterman-Algorithmus auch nicht.) M.E. würde es schon helfen, wenn in den ersten Satz "in der (Bio-)Informatik" eingefügt würde -- wobei ich nicht sicher bin, ob das "Bio-" gerechtfertigt ist. -- UKoch 16:59, 23. Feb. 2011 (CET)

So, nun enthält die Einleitung etwas zu den Anwendungen in der Bioinformatik, Optimierungsziel wird genannt, Alignment erklärt usw. (btw, Needleman-Wunsch waren zwar Biologen, aber NW kann man natürlich auch für beliebige Zeichenketten einsetzen - sie auch Leveshtein-Distanz). Deswegen habe ich nun den Baustein entfernt. Beispiel ist im Artikel schon enthalten - hat aber nichts mit der Einleitung zu tun. --Gms 22:51, 20. Jan. 2012 (CET)

Hallo! Ich habe jetzt auch versucht, die Einleitung umzuschreiben, nach dem Motto: Das Wichtigste zuerst, in möglichst simplen Worten. Ausserdem hab ich versucht, die Sprache ein bisschen zu entschnörkeln. Das geht sicher noch besser, aber ich bin kein Experte. --131.130.226.44 17:59, 3. Sep. 2018 (CEST)

Beispiel irreführend

Entspricht das Beispiel dem im Originalpaper beschriebenen Algorithmus? Das sieht nach O(n²) aus. Easelpeasel (Diskussion) 19:31, 6. Dez. 2013 (CET)

Formalismus im Beispiel

Die Bezeichnung "die Matrix D(i,j)" ist falsch. Die Matrix heißt D (in R^n x m) und D(i,j) ist ein Koeffizient der Matrix, hier ein Skalar. Ich bin der Stochastik aber absolut fremd, darum will ich im Artikel nichts ändern.

Ich verstehe noch nicht, warum die Matrix im Beispiel plötzlich D heißt und im Algorithmus M?! (nicht signierter Beitrag von 131.188.6.20 (Diskussion) 17:19, 30. Jan. 2020 (CET))