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. DavidSearls and (later, in a probabilistic modeling context) by SeanEddy, RichardDurbin, DavidHaussler, YasubumiSakakibara et al.

• Stochastic grammar programs in the Handel package:
  • Xgram (xfold, xprot, xrate): user-hackable phylo grammars
  • Stem Loc: 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
  • Stem Loc
  • Handel package
• Stochastic Grammar Applications: advanced applications of SGs