Topology and prediction of RNA pseudoknots

\section{Motivation:}
Several dynamic programming algorithms for predicting RNA structures with
pseudoknots have been proposed that differ dramatically from one another
in the classes of structures considered.
\section{Results:}
Here we use the natural topological classification of RNA structures in
terms of irreducible components that are embedable in surfaces of fixed
genus. We add to the conventional secondary structures four building blocks
of genus one in order to construct certain structures of arbitrarily high
genus. A corresponding unambiguous multiple context free grammar provides
an efficient dynamic programming approach for energy minimization,
partition function, and stochastic sampling. It admits a topology-dependent
parametrization of pseudoknot penalties that increases the sensitivity and
positive predictive value of predicted base pairs by 10-20\% compared to
earlier approaches. More general models based on building blocks of higher
genus are also discussed.
\section{Availability:}
The source code of \texttt{gfold} is freely available at
\url{http://www.combinatorics.cn/cbpc/gfold.tar.gz}
\section{Contact:}
\href{[email protected]}{[email protected]}
\section{Supplementary information:}
Supplementary material containing a complete presentation of the
algorithms, full proofs of theorems, and detailed performance data are
available at \emph{Bioinformatics online}.