Main > TWikiUsers > IanHolmes > StringTransducers > TreeTransducers

TWiki webs: Main | TWiki | Sandbox   Log In or Register

Users | Groups | Changes | Index | Search | Go

Tree transducers

• Tree transducers
  • Introduction
    • Alternate names
  • References
  • Software

Introduction

Tree transducers are extensions of string transducers. Rather than locally mutating strings, tree transducers locally mutate parse trees.

Formal rules for intersection and composition of tree transducers make them amenable to phylogenetic alignment and in particular multiple RNA alignment.

Tree transducers can be used to perform structural alignment of multiple RNAs or even reconstruct possible ancestral RNA structures. Our programs, EvolDoer and IndieGram, can (respectively) align & fold two non-coding RNAs (evoldoer) or reconstruct the most-probable ancestral structure of three non-coding RNAs (evolstar), using tree transducers to model RNA structural change.

Alternate names

Tree transducers (or parse tree transducers) are essentially equivalent to Pair Stochastic Context-Free Grammars.

They are also closely related to pushdown automata.

"Pair HMMs on Tree Structures" (Sakakibara) are similar models.

References

• Bradley RK, Holmes I.  Evolutionary triplet models of structured RNA.  PLoS Comput Biol. 2009 Aug;5(8):e1000483. doi: 10.1371/journal.pcbi.1000483. Epub 2009 Aug 28.
  • Link to article

• Computational linguistics
  • Rounds, William C. 1970. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257–287.
  • Thatcher, J. W. 1970. Generalized sequential machine maps. Journal of Computer and System Sciences, 4:339–367.
  • Grael and Knight: http://www.isi.edu/natural-language/projects/rewrite/ttt.pdf
  • TATA: http://tata.gforge.inria.fr/

• Bioinformatics
  • Holmes I.  A probabilistic model for the evolution of RNA structure.  BMC Bioinformatics. 2004 Oct 26;5:166. (PDF)
  • Sakakibara Y.  Pair hidden Markov models on tree structures.  Bioinformatics. 2003;19 Suppl 1:i232-40.

Software

The EvolDeeds package uses tree transducers:

• EvolSayer does forward-simulation of a continuous-time model (the TKF structure tree) whose finite-time transitions can be described by a time-parameterized tree transducer
• EvolDoer does pairwise alignment & inference under this same model (TKF structure tree), using pair SCFGs
• IndieGram, RobertBradley's graduate project, creates a 4-tape SCFG via a three-transducer composition on a star toplogy, then uses this for multiple alignment & ancestral inference on 3 sequences

Edit | Attach | Print version | History: r28 < r27 < r26 < r25 < r24 | Backlinks | Raw View | Raw edit | More topic actions

Copyright © 2008-2013 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback