C++Guns – RoboBlog

29.03.2017

Biologie++ - RNA Folding with Four-Russians Speedup

Filed under: Allgemein — Tags: — Thomas @ 12:03

Der normale dynamic programing Zuker Algorithmus von Faltungen von Sequenzen hat eine Laufzeit von O(n^4), mit zuätzlichen Cache noch O(n^3). Mit der allgemeinen Four-Russians Speedup Methode für dynamic programing Algorithmen ist eine Laufzeit von O(n^3/log n) möglich. Für kleines n also absolut irrelevant. Für großes n halbiert, oder drittelt sogar die Laufzeit. Was dann aber immer noch unheimlich zu lange ist.
Aber was ist die Idee dahinter?
Als erstes wird festgestellt, dass es nicht möglich ist, die Four-Russians Technik auf die klassische Implementation des Zuker anzuwenden. Da die Auswertungsreihenfolge der Matrizen nicht passt. Also wird die Reihenfolge erst mal umgestellt. Erst kommt eine Schleife die nicht von der derzeitigen Spalte j in der Matrix abhängt. Und dann kommt eine 3fach Schleife die abhängt.
In der innersten Schleife findet nun die Optimierung statt. Die Schleife sieht so aus:

S(i,j)=max( S(i,j), S(i,k-1)+S(k,j) )

Für fixes i,j iteriert nur k von i+1 zu j-1. Die Idee ist nun, Indizes zu Gruppe der Größe q zusammen zu fassen. So dass die innerste Schleife nur noch n/q oft läuft.
Nun ja wenn sie meinen. Um das Maximum zu ermitteln, muss man so oder so jeden Wert in der Matrix in diesem Bereich anfassen. Wie die das verhindern wollen, das lese ich aus dem Paper nicht raus.
Zeitverschwendung.

[1] A Simple, Practical and Complete Time Algorithm for RNA Folding Using the Four-Russians Speedup - Yelena Frid and Dan Gusfield

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress