Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

This paper shows simple dynamic programming algorithms for RNA secondary structure pre diction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O(n(4)) time exact algorithm and an O(n(4-delta)) 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 - epsilon of the optimal, where epsilon,delta are any constants satisfying 0<1. Several related results are shown too. (C) 2000 Elsevier Science B.V. All rights reserved.