Diskussion:Smith-Waterman-Algorithmus

Achtung: Voraussetzung zum Verständnis dieses Artikels ist der Needleman-Wunsch-Algorithmus.

Trotzdem könnte man eine Einleitung schreiben...

--zeno 18:09, 18. Feb 2005 (CET)

Einleitung ein wenig abgeändert.

Hört sich so schöner an.

Dennis G. 17:14, 16. Sep 2005 (CEST)

Verbesserungsvorschläge

Ich finde, wenn man schon die mathematische Formulierung der Rekursionsgleichung aufzeigt, dann sollte man auch auf die Initialisierung der ersten Zeile/Spalte eingehen. Das steht zwar schon im Artikel über den Needleman-Wunsch Algorithmus, aber an dieser Stelle stört diese Redundanz meiner Meinung nach nicht:

$D(0,0)=0\$

$D(i,0)=max\lbrace D(i-1,0)+w(a_{i-1},-),0\rbrace \ ,wobei\ i=1,\cdots ,n-1$

$D(0,j)=max\lbrace D(0,j-1)+w(-,b_{j-1}),0\rbrace \ ,wobei\ j=1,\cdots ,m-1$

Dann hat man zumindest die gesamte mathematische Formulierung auf einen Blick. Was haltet ihr von diesem Vorschlag ?

Achtung! Die hier genannte Initialisierung ist falsch! siehe Literatur --83.135.210.167 20:53, 3. Jan. 2007 (CET)

Außerdem finde ich, dass im vorherigen Abschnitt der Punkt "Traceback" zu kurz kommt. Beispielsweise wird nicht geklärt nach welchem Muster D durchlaufen wird.

Wird nun wie beim Needleman-Wunsch-Algorithmus immer einer der größten Vorgänger gewählt oder wird einfach diagonal nach oben gegangen, wie es im Beispiel der Fall ist?

Dies ist für den Leser eine wichtige Frage. Wenn ich den Algorithmus richtig verstehe, sucht man hierbei nach exakten Übereinstimmungen von Substrings. Also muß man einfach startend vom größten $D(i,j)\$diagonal zurücklaufen bis man auf die erste Zelle trifft, die den Wert 0 enthält. Dies ist ein Unterschied zum Needleman-Wunsch-Algorithmus und sollte dann auch an dieser Stelle erwähnt werden. Falls ich mich in diesem Punkt irre, so beweist dies trotzdem, dass dieser Artikel noch einen gewissen Feinschliff benötigt :-)

Desweiteren befindet sich im Abschnitt Beispiel ein kleiner Fehler, der eventuell verwirrt. Dort wird definiert, dass Sequenz 1 = ACGA und Sequenz 2 = TCCG . Dazu gibt es zwei Dinge anzumerken:

1. Bei Needleman-Wunsch werden diese Sequenzen als a und b bezeichnet und an diese Notation sollte man sich an dieser Stelle beibehalten.
2. Die Reihenfolge ist falsch. Damit die Sequenzen zu der abgebildeten Matrix passen, müsste man sie vertauschen, d.h. a = TCCG und b = ACGA (vgl. Needleman-Wunsch-Algorithmus).

Ueberarbeitung

Hallo,

ich wollte erst gar nicht soviel ueberarbeiten - aber dann kam doch das eine zum anderen.

Das Beispiel habe ich noch nicht durchgeschaut - aber wahrscheinlich werde ich es auch ueberarbeiten. Also ein Beispiel nehmen, wo man tatsaechlich den Unterschied zwischen globalen und lokalen Alignment sieht (und vielleicht etwas schoener aussieht inkl. Backtracking-Pfeilen).

--83.135.210.167 21:03, 3. Jan. 2007 (CET)

Allgemeinverständlichkeit

Hallo, m.E. ist die Einleitung und der weitere Artikeltext unverständlich und für die Allgemeinheit der Leserschaft (vgl. WP:OMA) unbrauchbar. Erst wer affin mit dem Thema ist, wird überhaupt aus dem Artikel ersehen können, worum es in dem Artikel geht. 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:55, 22. Sep. 2010 (CEST)

Man kann WP:OMA auch als Totschlagargument verwenden. Wenn die Oma noch nicht weiß was ein Sequenzalignment oder ein Substring ist, dann sollte sie dies in den verlinkten Artikeln nachlesen. Dort werden auch detailreich die Varianten von verschiedenen Alignment-Optimierungsproblemen erklärt.

Der Smith-Waterman-Algorithmus ist zudem eine Spezialisierung vom Needleman-Wunsch Algorithmus zur Berechnung des globalen Alignments. D.h. sich direkt mit dem Smith-Waterman-Algorithmus zu beschäftigen und dabei die Grundlagen zu ignorieren ist ein suboptimales Vorgehen.

Ich beschwere mich z.B. auch nicht beim Artikel Demon Core auch nicht: Unverständlich überkritisch! Wenn ich nicht weiß, was eine überkritische Masse ist, dann lese ich mir den verlinkten Artikel durch. Das ist zurecht in dem Artikel nicht nochmal redundant erklärt.

Anderes Beispiel: Hamilton-Funktion - wenn einem die entsprechende höhere Mathematik nicht geläufig ist und keine referenzierten Artikel nachlesen möchte, dann fürchte ich, hat die eine oder 'Oma' damit Verständnisprobleme.

--Gms 13:38, 2. Okt. 2010 (CEST)

Demon Core ist ja wohl ein schlechtes Beispiel, da bekommt man schon im ersten Satz einen Bezug, was hier gänzlich fehlt. Wofür wid der gebraut aus welchem Bereich ist er. Mathe bio Inormatik. Wie wärs denn mit einem ersten Satz ... ist ein Begriff aus ... und dient ... und danach weiter mit dem was da steht.`` --Jörgens.Mi ^Diskussion 08:19, 31. Okt. 2010 (CET)

Ich habe die Einleitung und das lokales Alignment-Problem neugeschrieben. Es wäre toll, wenn jemand darüberliest, um etwaige Fehler zu finden. Dem Begriff Matrix-Rekurrenzen bin ich niemals begegnet; ist das ein geläufiger Begriff? Ich hätte dieses Kapitel mit Rekursiver Algorithmus betitelt. Dieses Kapitel bedarf in meinen Augen ebenso einer Überarbeitung, um den Algorithmus übersichtlicher und verständlicher darzustellen. -- Simon04 19:33, 19. Nov. 2010 (CET)

Ja, Rekurrenz ist der Fachbegriff für diese Art von Funktionen[1]. Es ist ja eine funktionale Spezifikation. --Gms 21:12, 20. Nov. 2010 (CET)

Danke, die Einleutung ist jetzt deutlich besser. nur am Ende Im gegensatz Dazu... Mir als Leser entgeht der Bezug zu diesem andeen Algo.... (Da ich hier die Diskussion und den Artikel gelesen habe natürlich nicht). Jörgens.Mi ^Diskussion 20:29, 19. Nov. 2010 (CET)

So, habe die Einleitung überarbeitet und alles wesentliche reingepackt. Dabei ist es etwas redundant zu dem Artikel Sequenzalignment geworden - aber ich denke das ist ein ganz guter Kompromiss zwischen Redundanz, Knappheit und abgeschlossener Erklärung im Artikel (damit man nicht zuviel springen muss).

' ... ist ein Begriff aus ...' habe ich vermieden, da vieles ein Begriff ist, aber 'Algorithmus' der spezifischere Begriff ist ... ;)

--Gms 21:12, 20. Nov. 2010 (CET)

Die Einleitung gefällt mir gut! Ein paar Fragen bzw. Anmerkungen habe ich noch:

• seine Laufzeit ist quadratisch: eigentlich linar in der Länge beider Sequenzen
• Rekurrenz: Der Link auf eine Begriffserklärung stört mich, besonders, da dort kein passend erscheinender Artikel aufgeführt ist. Eventuell passt Differenzengleichung (engl. recurrence relation)?
• Was ist mit dem A Matrix-Eintrag gemeint?

Übrigens: Ich habe den Abschnitt auf Wikipedia:Unverständliche_Artikel#Smith-Waterman-Algorithmus als erledigt markiert. -- Simon04 18:42, 21. Nov. 2010 (CET)

• Man könnte es auch anders formulieren, z.B.: 'ist quadratisch' in Abhängigkeit von der Eingabelänge - bzw. die Laufzeit wächst quadratisch in Abhängigkeit von der Eingabelänge - d.h. die Eingabelänge ist $m+n=O(max(m,n))=O(m+n)$ und die Laufzeit ist in $O(mn)=O(max(m,n)^{2})$
• Ja, genau, das passt.
• Das ist wahrscheinlich aus einer alten Version übergeblieben oder ein Tippfehler. Sollte vielleicht '$A$-Matrix-Eintrag' heißen, als vielleicht die Matrix mit A bezeichnet wurde. Kann man aber sicherlich geschickter formulieren.
• Super, hatte ich nicht dran gedacht. --Gms 21:39, 21. Nov. 2010 (CET)