%WEBLOGOALT%

This site is powered by the TWiki collaboration platform Powered by PerlBiowiki content is in the public domain.
Comments on this site? TreeTransducers">Send feedback

Biowiki . Main . TreeTransducers

Biowiki . Main . TreeTransducers

Tree transducers

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

Software

The EvolDeeds package uses tree transducers:


----- Revision r28 - 2010-05-18 - 07:34:57 - IanHolmes
Biowiki content is in the public domain.
Comments on this site? TreeTransducers">Send feedback