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.
Home