For a very long time fastest algorithm for minimum free energy (MFE) calculation for single RNA was believed to be $O(n^3)$ time, where n is the size of the RNA sequence. In 2007, Wexler et al. reduced the time complexity for the MFE algorithm for single RNA to $O(n^2 \psi(n))$, where $\psi(n)$ was shown to be almost constant on average. Later in 2010, Backofen et al. used the Wexler et al. approach and reduced the space complexity of the MFE algorithm from $O(n^2)$ to $O(Z)$ and also reduced the time complexity further to $O(n^2+PZ)$, where P is a sparsity parameter satisfying $P < n \le Z \le n(P+1)$. If you are interested to hear about these two papers, please join us for the reading group on May 3rd, 2011, when I will present these two papers and lead discussion about further improvements on this topic.