Stochastic Grammars

Stochastic Grammars

Stochastic grammars are a probabilistic generalisation of the formalism proposed by Chomsky and developed by the early compiler writers. Grammars were popularised for biological sequence analysis by e.g. David Searls and (later, in a probabilistic modeling context) by Sean Eddy, Richard Durbin, David Haussler, Yasubumi Sakakibara et al.

• Stochastic grammar programs in the Handel package:
  • Xgram (xfold, xprot, xrate): user-hackable phylo grammars
  • StemLoc: RNA multiple alignment (pairwise stochastic context free grammars)
  • tkfalign, etc: DNA and protein multiple statistical alignment (using evolutionary hidden Markov models)
• Advanced stochastic grammar applications

See also

• Multiple RNA alignment
• Phylogenetic Alignment reader
• Transposon annotation
• Holmes lab grammar software:
  • Xgram software
  • StemLoc
  • Handel package
• Stochastic Grammar Applications: advanced applications of SGs