Diskussion:Nussinov-Algorithmus

Durbin-Variante

Ist die Rekursion nicht eher: $\gamma (i,j)=\max {\begin{Bmatrix}\gamma (i+1,j)&i{\text{ ungepaart}}&\\\gamma (i,j-1)&j{\text{ ungepaart}}&\\\gamma (i+1,j-1)+\delta (i,j)&i,j{\text{ gepaart}}&\\\max _{i<k<j}(\gamma (i,k)+\gamma (k+1,j))&{\text{Verzweigung}}&\end{Bmatrix}}$ mit $\delta (i,j)={\begin{Bmatrix}1,&{\text{falls}}&(a_{i},a_{j})&{\text{ein kanonisches Basenpaar}}&\\0,&{\text{sonst}}&\end{Bmatrix}}$ ?

Hier die 4 Möglichkeiten beim Erweitern:

• 
  i ungepaart
• 
  j ungepaart
• 
  i und j gepaart
• 
  Verzweigung

--Zhujik

Nein, die Rekursion ist nicht eher das Vorangestellte. Es ist leider so, das der Nussinov falsch im Durbin steht. Und somit anscheinend auch falsch in Vorlesungsskripte landet.

Wenn du dir die Versionshistorie des Artikels anschaust dann hatte ich mich auch zuerst bei den Rekurrenzen beim Durbin orientiert. Denn es war etwas her, dass ich das Nussinov-Paper gelesen hatte und ich hatte es beim Erstellen der ersten Artikelversion nicht parat. Aber dann habe ich nochmal das Paper durchgelesen, gesehen dass die Rekurrenzen im Paper andere sind, und deshalb den Artikel danach entsprechend geändert.

Den Hintergrund hatte ich ja dann auch im Abschnitt 'Abgrenzung' erläutert.

Was im Durbin als Nussinov bezeichnet wird, ist nicht Nussinov - die mehrdeutige 4-fach Fallunterscheidung ist auch nicht 'irgendwie besser'; die Durbin-Variante ist zwar genauso effizient; es kommt der selbe optimale Score raus; aber das Backtracing wird so semantisch mehrdeutig, da mehrere verschiedene Traces die gleiche Struktur repräsentieren. Besonders blöd, wenn man die Anzahl der unterschiedlichen Strukturen ermitteln möchte oder co- bzw. suboptimale Strukturen aufgezählt werden sollen.

Schau dir doch mal das Nussinov-Paper an; da sind die Rekurrenzen klar beschrieben. Diese Rekurrenzen sind auch korrekt; jede wohldefinierte Sekundärstruktur wird durch die 2-fache Nussinov Fallunterscheidung eindeutig beschrieben.

Abgesehen davon ist nach deinen letzten Änderungen, der Artikel etwas inkonsistent geworden. Nach einem flüchtigen Überfliegen ist mir die Bezeichnung der Sequenz mit A aufgefallen, später wird immernoch s[i..j]-Notation verwendet. Der Abschnitt Abgrenzung liest sich jetzt etwas konfus.

Gut, warum die Matrix-Bezeichnung N durch $\gamma$ ersetzt werden muss ... Auch sollte der Vorlesungsskript-Link an letzte Stelle genannt werden, wenn überhaupt - da er ja am wenigsten 'wert' ist - am meisten Wert hat das Original-Paper, Lehrbuch kommt irgendwann später, und ein Vorlesungsskript irgendwann zum Schluss (nicht 'ge-peer-review-t' ...).

Achja, und unterschreib doch beim nächsten Mal deine Beiträge auf der Diskussionsseite mit --~~~~, damit man sie besser zuordnen kann.

Gruß --Gms 23:42, 12. Jul. 2008 (CEST)

Hab die Unterschrift oben vergessen, sry.

Direkt falsch ist er dann ja nicht wie er im Durbin steht, nur ineffizient bzw. für manche Fragestellungen unnütz. Übrigens habe ich nirgends geschrieben dass er "irgendwie besser" ist... Ich finde allerdings die Erklärung besser :) Aber du hast recht, der Originale Nussinov ist es ja dann nicht mehr. Was hälst du davon, wenn man einfach beide Varianten beschreibt, mit entsprechendem Hinweis? --Zhujik 12:00, 13. Jul. 2008 (CEST)

Mit den ' wollte ich nicht zitieren, sondern es nur in Anführungszeichen setzen.

Ich finde es sinnvoller die 4-fach-Fallunterscheidung mit den schematischen Bildern im Artikel Zuker-Algorithmus unterzubringen (dort wird in der ersten Rekurrenz so unterschieden). Dort passt es besser. Denn beim Zuker-Algorithmus wird diese semantisch mehrdeutige Unterscheidung genau so durchgeführt - auch im Original-Paper.

Achja, meinst du nicht, dass man den Algorithmus-Pseudocode in dem Nussinov-Artikel weglassen kann? Denn er ist ja eine sehr direkte Übertragung der Rekurrenz.

--Gms 14:13, 14. Jul. 2008 (CEST)

So - ich habe nun die 4-fach-Fallunterscheidung-Gallery in Zuker-Algorithmus eingebaut. --Gms 19:46, 1. Aug. 2008 (CEST)

Fehler?

Die Formel

$N[i,j]=\max {\begin{Bmatrix}N[i,j-1]&\\\max _{i\leq k<j-1}(N[i,k-1]+1+N[k+1,j-1])\cdot \sigma (k,j)&\end{Bmatrix}},0\leq i<n,0<j<n,i<j$

ergibt für n = 0 und j = 1 im zweiten "max"-Term:

$\max _{0\leq k<0}$

Ich denke nicht, dass das zulässig ist. Was ist hier die Lösung?

... Im Paper von Nussinov et al. tritt ein Zugriff auf das Element N[0,-1] auf. Was soll das bedeuten? --77.80.4.22 14:10, 23. Mär. 2018 (CET)