^August September – 2010 ^October

Some of the fundamental algorithms in RNA secondary structure are dynamic programming algorithms. The goal of improving these algorithms is motivated by the understanding that RNA structure helps to determine function. While these algorithms have been around since the early 1980’s it was only recently that the well known dynamic programming speed up –Four Russians Speed Up– been applied. In this talk presented is the Four Russians Speed Up applied to the Basic RNA folding algorithm and the Sankoff alignment and folding algorithm. The speedup leads to a time reduction from O(n^3) to O(n^3/log(n) ) for RNA secondary structure and from O(n^6) to O(n^6/log(n^2)) time reduction for the Sankoff algorithm of simultaneous alignment and folding.