Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots ? ??
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.
dynamic programming rna secondary structure pseudoknot approximation algorithms computational biology