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

<h4>Grammars:</h4>

<PRE>
 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  
</PRE>

Note: In contrast to other grammars for RNA folding, these stochastic
grammars admit non-standard base pairing (with low probability).<br>

To start, enter some input sequence, choose a grammar and a scoring
scheme and press the "Go!" - Button.<br><br>

<h4>Description of the scoring schemes:</h4>
<ul>
<li><i>viterbi</i>: runs the Viterbi algorithm for the
grammar. Probabilities for paired and unpaired bases are taken from
<a href="http://www.daimi.au.dk/~compbio/pfold/">Pfold server</a>. 
For grammars G1 to G5, only example rule probabilies are given. G6 is
the Knudsen/Hein grammar of the Pfold package. Here, the rule
probabilities are also taken from Pfold server.</li>
<li><i>inside</i>: runs the Inside algorithm with same probabilities as viterbi. </li>
<li><i>count</i>: calculates the number of derivations for the given
input sequence</li>
<li><i>pairmax</i>: base pair maximization</li>
<li><i>dotbracket</i>: gives the complete list of derivations in
dotbracket-notation</li>
<li><i>trees</i>: gives the complete list of derivations as
derivation trees</li>
<li><i>A *** B</i>: calculates cross product between scoring
schemes A and B. For example, <i>viterbi *** dotbracket</i>
calculates the best viterbi score together with the corresponding
structures in dotbracket-notation.</li>
</ul>

<H4 id="body_header">For usage on your local machine:</H4>
<ul>
   <li>
      Download the ADP sources:
      <BR>
      <a href="/adp/src/###9.lhs">###9.lhs</a><BR>
      <a href="/adp/src/ADPTriCombinators.lhs">ADPTriCombinators.lhs</a>
      <BR>
   </li>
   <li>
      Download the Haskell interpreter hugs from 
      <a href="http://www.haskell.org/hugs">http://www.haskell.org/hugs</A>.
   </li>
</ul>


<H4><a name="generator">Mechanical proof of non-ambiguity:</a></H4>

For the mechanical proof procedure you need an LR(k) parser
generator. We recommend MSTA, which can be downloaded at <a
href="http://cocom.sourceforge.net/">http://cocom.sourceforge.net/</a>.
For our experiments we used version 0.995 (May 2002).<br>
The file <a
href="/adp/ambiguity/rna-grammars.tgz">rna-grammars.tgz</a> contains
MSTA input files of the grammars G1 to G8 from Dowell and Eddy's
paper.