Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots Original Research Article

This paper shows simple dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O(n4) time exact algorithm and an O(n4−δ) time approximation algorithm. The latter one outputs, for most RNA sequences, a secondary structure in which the number of base pairs is at least 1−ε of the optimal, where ε,δ are any constants satisfying 0<ε,δ<1. Several related results are shown too.