Fabrice Lefebvre

An optimized parsing algorithm well-suited to RNA folding

The application of stochastic contaxt-free grammars to the determination of RNA foldings allows a simple description of the sub-class of sought secondary structure, but it needs efficients parsing algorithms. The more classic thermodynamic model of folding popularized by Zuker under the framework of dynamic programming algorithms, allows an easy computation of foldings but its use is delicate when constraints have to be introduced on sought secondary structure. We show here that S-attribute grammars unify these two models and we introduce a parsing algorithm whose efficiency enables us to handle problems until then too difficult or too large to deal with. As a matter of fact, our algorithm is as efficient as a standart dynamic programming one when applied to the thermodynamic model (yet it offers a greater flexibility for the expression of constraints) and it is faster and saves more space than other parsing algorithms used so far for stochastic grammars.