This page contains ADP implementations of grammars G1 to G6 from Dowell and Eddy's recent paper (R.D. Dowell and S.R. Eddy, Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics, 5(71), 2004.):


 G1 :  S ->  aS | aS | Sa | SS | e              G4 :  S ->  aS | T | e
                                                       T ->  Ta | aS | TaS  

 G2 :  S      ->  aP^{a} | aS | Sa | SS | e    G5 :  S ->  aS | aS S | e
       P^{o} ->  aP^{a} | S            

 G3 :  S ->  aS | aL | Ra | LS                  G6 :   S ->  LS | L  
       L ->  aS | aL                                   L ->  aF | a  
       R ->  Ra | e                                     F ->  aF | LS  
Note: In contrast to other grammars for RNA folding, these stochastic grammars admit non-standard base pairing (with low probability).
To start, enter some input sequence, choose a grammar and a scoring scheme and press the "Go!" - Button.

Description of the scoring schemes:

For usage on your local machine:

Mechanical proof of non-ambiguity:

For the mechanical proof procedure you need an LR(k) parser generator. We recommend MSTA, which can be downloaded at For our experiments we used version 0.995 (May 2002).
The file rna-grammars.tgz contains MSTA input files of the grammars G1 to G8 from Dowell and Eddy's paper.