A dynamic programming algorithm for RNA structure prediction including pseudoknots

Elena Rivas, Sean R. Eddy

We describe a dynamic programming algorithm for predicting optimal RNA secondary structure, including pseudoknots. The algorithm has a worst case complexity of $\mathcal{O}(N^6)$ in t…