Faster algorithms for RNA-folding using the Four-Russians method
Implementation of the two vectors / four russians for accelerating Nussinov RNA folding prediction algorithm. The speedup makes the algorithm go from a O(n^3) to a O(n^3/log(n)) time complexity.
The algorithm used is discribed in Venkatachalam et al. paper.
The algorithm was implemented in c++. We’ve also implemented Nussinov algorithm in order to test the speed-up. Note that after crossvalidating we found that the best size of q si log in base 2 of n, this is thus the default size of q chosen.
Here you can find an intuitive explanation of the two-vectors acceleration, as well as our results.
The code can be found here simply compile and run. Note that you can specify the files containing the sequences in the main().
Here are the 2 plots we generated:
