PhyloGrammars

A "phylo-grammar" is a stochastic grammar whose emissions (i.e. terminals) are alignment columns, typically generated by evolving a continuous-time Markov process on a phylogenetic tree.

As a class of models, phylo-grammars include all simple point substitution models (including e.g. codon substitution, conditional approximations to context-dependent substitution, etc). They also include HMM- and SCFG-like models for co-ordinated evolution of features and domains (e.g. exon/intron predictors, or autocorrelated models of ultraconserved genomic regions).

Notable bioinformatics programs that use phylo-grammars include Pfold, Phastcons, Exoniphy and Dless.

For references see the following pages

• Lecture notes to Ian Holmes' graduate class
• xrate, the HolmesLab implementation of phylo-grammars (with examples)
• The original XRATE paper:
  Klosterman PS, Uzilov AV, Bendana YR, Bradley RK, Chao S, Kosiol C, Goldman N, Holmes I.  XRate: a fast prototyping, training and annotation tool for phylo-grammars.  BMC Bioinformatics. 2006 Oct 3;7:428.
• StochasticGrammars - big page of references on stochastic grammars in general
  • KnudsenHein - page of links to PFOLD and the Knudsen-Hein algorithm... the first phylo-SCFG
  • PhylogeneticAlignmentReader - evolution-based grammars
  • MultipleRNAAlignment - RNA-based grammars