Phylo Grammars

Phylo Grammars

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 Holmes Lab implementation of phylo-grammars (with examples)
• The original XRATE paper:
  Klosterman et al.: XRate: a fast prototyping, training and annotation tool for phylo-grammars. BMC Bioinformatics 2006;7:428.
• Stochastic Grammars - big page of references on stochastic grammars in general
  • Knudsen Hein - page of links to PFOLD and the Knudsen-Hein algorithm... the first phylo-SCFG
  • Phylogenetic Alignment Reader - evolution-based grammars
  • Multiple RNAAlignment - RNA-based grammars