Stochastic Grammar Applications

A short list of papers that push the frontier of stochastic grammars in bioinformatics.

• Stochastic context free grammars
  • Bockhorst J, Qiu Y, Glasner J, Liu M, Blattner F, Craven M.  Predicting bacterial transcription units using sequence and expression data.  Bioinformatics. 2003;19 Suppl 1:i34-43.
  • Knudsen B, Hein J.  RNA secondary structure prediction using stochastic context-free grammars and evolutionary history.  Bioinformatics. 1999 Jun;15(6):446-54.
  • Rivas E, Eddy SR.  Noncoding RNA gene detection using comparative sequence analysis.  BMC Bioinformatics. 2001;2:8. Epub 2001 Oct 10.

• Higher-power grammars (tree-adjoining, etc)
  • Mamitsuka H, Abe N.  Predicting location and structure of beta-sheet regions using stochastic tree grammars.  Proc Int Conf Intell Syst Mol Biol. 1994;2:276-84.
  • Matsui H, Sato K, Sakakibara Y.  Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures.  Bioinformatics. 2005 Jun 1;21(11):2611-7. Epub 2005 Mar 22.
  • Chiang D, Joshi AK, Dill KA.  A grammatical theory for the conformational changes of simple helix bundles.  J Comput Biol. 2006 Jan-Feb;13(1):21-42.

• Discriminative generalizations
  • Do CB, Woods DA, Batzoglou S.  CONTRAfold: RNA secondary structure prediction without physics-based models.  Bioinformatics. 2006 Jul 15;22(14):e90-8.