An Optimized Parsing Algorithm Well Suited to RNA Folding

Proceedings of the Twentieth International Conference on Machine Learning, 1995

Volume

Proceedings of the Twentieth International Conference on Machine Learning, 1995

Contents

The application of stochastic context-free grammars to the determination of RNA foldings allows a simple description of the sub-class of sought secondary structures, but it needs efficient 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 structures. 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 standard 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.