Diskussion:Waterman-Smith-Beyer-Algorithmus

Abgrenzung zum Needleman-Wunsch-Algorithmus

Es gibt Auffassungen, nach denen der Waterman-Smith-Beyer-Algorithmus eine Erweiterung des Needleman-Wunsch-Algorithmus darstellt. Die Algorithmen werden dann wie folgt verstanden:

• Der Needleman-Wunsch-Algorithmus ermöglicht allgemeine Kosten für einzelne Operationen! D.h. die Kosten für Insertion-, Deletion, Replace/Match Operationen können in Abhängigkeit von dem bearbeiteten Zeichen gewählt werden. Deswegen lässt sich eine Laufzeit in O(nm) erreichen.
• Der Waterman-Smith-Beyer-Algorithmus hingegen ermöglicht allgemeine Gap-Kosten! D.h. die Kosten für ein Gap können in Abhängigkeit der Gap-Länge gewählt werden. Damit ist nurnoch eine kubische Laufzeit möglich.

Vorrausgesetzt diese Unterscheidung stimmt, dann wird momentan im Wikipedia-Artikel zum Needleman-Wunsch-Algorithmus der Waterman-Smith-Beyer-Algorithmus beschrieben.

Folgende Bitte: Wenn ihr die o.g. Unterscheidung auch so seht, tut dies hier kurz kund. Ich kann dann einen Artikel Waterman-Smith-Beyer-Algorithus verfassen, ohne dass er gelöscht wird. Den Verfasser des NW-Algorithmus müsste dann dieser Abgrenzung überzeugt werden damit die Seite zum NW-Algorithmus angepasst werden kann. Wenn ihr anderer Meinung seid, erklärt bitte hier kurz was eurer Meinung nach den Waterman-Smith-Beyer-Algorithmus ausmacht.

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

Ich kann die beschriebene Unterscheidung nicht nachvollziehen. Im Needleman-Wunsch-Paper von 1970 wird schon von allgemeinen Gap-Kosten geschrieben. Auf der NW-Diskussionsseite hatte ich schonmal den relevanten Abschnitt zitiert, nämlich:

'[..] 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. [..]'

Desweiteren ist das Vorlesungsskript als einzige Quelle für den sogenannten Waterman-Smith-Beyer-Algorithmus zu wenig (ist anscheinend nicht online verfügbar und ist nicht über eine Uni-Bibliothek beziehbar ...). Gibt es denn kein Paper zu diesem Algorithmus (von Smith und Beyer ...)?

--Gms 21:53, 30. Nov. 2009 (CET)

Zum Waterman-Smith-Beyer Algorithmus kann ich folgende beiden Referenzen beitragen:

- Original Artikel (Rekursion in Theorem 3)

- Lehrbuch (Theorem 3.13 - Seite 95)

Ich glaube hier gibt es einfach das Problem: was genau steht im originalen Needleman-Wunsch Artikel und in welchem Zusammenhang wird der Begriff Needleman-Wunsch-Algorithm heutzutage verwendet.

- Im ersten Fall hast du (Gms) Recht, dass die beiden Autoren versuchen mit ihrem Halbsatz alle möglichen gap-penalties zu erschlagen. Allerdings fehlt die Beschreibung der notwendigen Rekursionen sowie die Komplexitätsanalyse (soweit ich das sehe).

- Im zweiten Fall, also bzgl. des allgemeinen Gebrauchs des Algorithmus in Forschung und Lehre hat sich der NW mit linearen Gapkosten etabliert. D.h. mit der O(nm) Zeit- und Platzkomplexität und einer festen Bestrafung mit Wert $d$ für das einfügen einer Gapposition. D.h. die Bestrafung des Gaps der Länge $l$ erfolgt durch $ld$ und zwei gaps der Längen $l_{1}+l_{2}=l$ werden mit dem gleichen Wert bestraft $(ld=(l_{1}+l_{2})d=(l_{1}d+l_{2}d))$. Dies ist die aktuelle Lehrbuchmeinung zu NW: globales paarweises Sequenzalignment mit beliebiger match/mismatch Bewertung aber fixer (linearer) Gapkostenbewertung (vgl. , hier wird auch das Problem der Diskrepanz zwischen dem Originalartikel und dem allgemeinen Gebrauch von NW diskutiert (Kapitel 11.7.3)).

Aufgrund dessen ist die Frage wie man den NW in Wikipedia darstellt: festgeschnürt am Originalartikel oder entsprechend des allgemeinen Gebrauchs. Denn schliesslich dient Wikipedia ja als Nachschlagewerk (u.a. für Hilfe suchende Studenten). Wenn dann die allgemeine Lehrmeinung sehr vom Inhalt in Wikipedia abweicht, ist das nicht sehr hilfreich. Allerdings wird die Waterman-Smith-Beyer Rekursion oft in Büchern und Lehre einfach als NW für allgemeine Gapkostenfunktionen beschrieben.

Somit fänd ich beides sinnvoll: eine Seite welche auf die Existenz des WSB-Artikels hinweist und dann aber direkt zur NW-Seite verlinkt. Dann könnte man auf der NW-Seite das ganze Problem lösen/klären. D.h. dort erst die allgemein gebräuchliche Form mit linearen Gapkosten darstellen (wie in den meisten Lehrbüchern als NW bezeichnet) und danach die allgemeinere Form für beliebige Gapkosten skizzieren und dort vermerken, dass diese Rekursion halt von WSB in deren Artikel vorgestellt wurde. Zudem könnte man dann noch (dem Gusfield folgend) das Dilemma zwischen Originalansatz und Gebrauch dikutieren/klären.

Das würde die Sache meiner Meinung nach rund machen...

--Martin Mann 17:25, 02. Dez. 2009 (CET) (ohne Benutzername signierter Beitrag von Qyu (Diskussion | Beiträge) )

Im NW-Paper von 1970 wird klar über beliebige Gap-Kosten und über die Berechnung der Edit-Matrix geschrieben. Aber eben nicht formal spezifizierend als Matrix-Rekurrenzen, sondern in 'Prosa'. Deswegen steht ja auch schon im wp NW-Algorithmus-Artikel im Abschnitt Abgrenzung:

'In dem Needleman-Wunsch Paper von 1970 sind keine Matrix-Rekurrenzen enthalten, der Algorithmus wird dort informell beschrieben; die Matrix-Rekurrenzen ergeben sich aus dieser Beschreibung.'

Welche Quellen nun als Grundlage für den Hauptteil des WP-Artikels Needleman-Wunsch-Algorithmus dienen sollen - da ist doch der Fall ganz klar. Es gibt den wissenschaftlichen Grundsatz, Primärquellen zu verwenden, soweit möglich. Und in diesem Fall ist dies ohne Umstände möglich. Um es anders zu schreiben: Der WP-Artikel kann ja nichts dafür, wenn in ein paar Lehrbüchern bzw. Scripten etwas unsauber der Sonderfall mit linearen Gap-Kosten, welcher in $O(n^{2})$ ist, als Needleman-Wunsch-Algorithmus bezeichnet wird. Kann ja mal vorkommen, dass man beim Verfassen des Skriptes nur in ein Lehrbuch schaut, wo es schon unsauber drin steht, und nicht in die Primärquelle.

Abgesehen davon ist es natürlich kein Problem im Needleman-Wunsch-Algorithmus-Artikel-Abschnitt Abgrenzung oder in einem neuen Abschnitt WSB oder ähnliches darauf einzugehen, dass manche Autoren den NW-Algorithmus mit allgemeinen Gap-Kosten als Waterman-Smith-Beyer-Algorithmus bezeichnen. Und dann natürlich Weiterleitung von der Waterman-Smith-Beyer-Algorithmus-Seite auf Needleman-Wunsch-Algorithmus bzw. den Unterabschnitt.

Auch kann man unter einem weiteren Abschnitt auch noch genauer auf den Spezialfall mit linearen Gap-Kosten eingehen (also z.B. das entsprechende Set von Rekurrenzen aufschreiben) evtl. inkl. Verweis auf Seller 1974.

Zur 'allgemeinen Lehrmeinung': Kommt drauf an! Es gibt auch andere Lehrmeinungen.

Zu Gusfield 11.7.3: Gut, er versucht etwas drumherumzureden in dem er auf den die zwei Betrachtungsweisen 'Problem-Statement' vs. 'Solution-Method' eingeht. Es wird aber nicht darauf eingegangen, warum 'Needleman-Wunsch' einen Vorteil als Problem-Statement gegenüber dem Problem-Statement 'compute global alignment' haben sollte ... Ausserdem heißt der Wikipedia Artikel ja gerade Needleman-Wunsch-Algorithmus und eben nicht 'Needleman-Wunsch' oder 'Needleman-Wunsch-Problem (statement)'. Unabhängig davon bezeichnet auch er den NW-Algorithmus als $O(n^{3})$ Algorithmus.

--Gms 14:59, 3. Dez. 2009 (CET)

Hallo Martin, danke für den aufschlussreichen Kommentar und die Referenzen! Deiner sowie GMS Kommentar machen deutlich, dass es sich in der Tat um eine berechtigte Diskussion handelt. Von daher wäre es -wie auch schon von euch vorgeschlagen- sinnvoll diese Diskrepanz auf der Seite des NW-Algorithmus als auch auf einer Seite zum WSB-Algorithmus zu erwähnen. Vielleicht habe ich ja demnächst mal Zeit dafür..

__AlienR 17:59, 3. Dez. 2009 (CET)