Abstract

Motivation: We consider the problem of RNA secondary structure prediction. In this setting one is interested in predicting a planar graph from a given nucleotide sequence. Even though there exists already a lot of algorithms dealing with this problem one can not consider it to be solved since even the current (2008) best approaches achieve error rates in the number of predicted pairs of about 25%. The prediction problem itself is well-established and the majority of computational approaches that have been proposed so far consists of two components:

• A dynamic programming algorithm for decoding the structure, and
• a parameter inference method.

While the dynamic programming algorithm is quite similar for all of these methods parameters are usually obtained either by using experimentally estimated thermodynamical data or via probabilistic inference. For more than 20 years thermodynamics based models where the most prominent and most successfully applied models to the RNA secondary structure prediction problem. A recently (Do et al) proposed probabilistic approach used a conditional maximum likelihood scheme for parameter inference. This model could outperform existing thermodynamic models significantly. Encouraged by these recent improvements we will use a large margin method related to Support Vector Machines to attack the prediction problem. The central idea is to find a parameter vector that assigns highest score to correct and lower score to incorrect structures.