Multithreaded parsing for predicting RNA secondary structures.

Many computational approaches have been developed for modelling and analysing the RNA secondary structure. These approaches are based on diverse methods such as grammars, dynamic programming, matching and evolutionary algorithms. This paper proposes a new parsing algorithm for the prediction of RNA secondary structures. The proposed algorithm is based on the shift-reduce LR parsing algorithm for programming languages. It has two main contributions: it extends the LR parsing algorithm by using a Stochastic Context-Free Grammar (SCFG) instead of Context-Free Grammar (CFG) for parsing RNA secondary structures; it extends the LR parsing algorithm by using a multithreaded approach to handle the LR parsing conflicts resulting from the use of ambiguous grammars.