Stochastic Context Free Grammars

A Stochastic Context Free Grammar is a stochastic generalisation of a context-free grammar. Introduced in natural language parsing, it is useful in working with RNA structure.

Implementations in DART

• Grammar object: DartSrc:scfg/paircfg.h
• Dynamic programming "fold envelopes" (iterators): DartSrc:scfg/foldenv.h
• Dynamic programming matrices (containers): DartSrc:scfg/paircfgdp.h

RNA sequence analysis

• Dowell RD, Eddy SR.  Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction.  BMC Bioinformatics. 2004 Jun 4;5:71.
• Holmes I.  Accelerated probabilistic inference of RNA structure evolution.  BMC Bioinformatics. 2005 Mar 24;6:73.
• Rivas E.  Evolutionary models for insertions and deletions in a probabilistic modeling framework.  BMC Bioinformatics. 2005 Mar 21;6:63.
• Pedersen JS, Meyer IM, Forsberg R, Simmonds P, Hein J.  A comparative method for finding and folding RNA secondary structures within protein-coding regions.  Nucleic Acids Res. 2004 Sep 24;32(16):4925-36. Print 2004.
• Rivas E, Eddy SR.  Noncoding RNA gene detection using comparative sequence analysis.  BMC Bioinformatics. 2001;2:8. Epub 2001 Oct 10.
• Grate L, Herbster M, Hughey R, Haussler D, Mian IS, Noller H.  RNA modeling using Gibbs sampling and stochastic context free grammars.  Proc Int Conf Intell Syst Mol Biol. 1994;2:138-46.
• See also Covariance Models

Linguistic comparisons

Code comparisons

Phylogenetic tree comparisons

• Rzhetsky A, Fitch WM.  Listening to viral tongues: comparing viral trees using a stochastic context-free grammar.  Mol Biol Evol. 2005 Apr;22(4):905-13. Epub 2004 Dec 29.

Other links

• UCSC SCFG papers

-- IanHolmes - 03 Apr 2005