Difference between revisions of "Renormalized Transducer Composition"
(Imported from TWiki)
m (Move page script moved page RenormalizedTransducerComposition to Renormalized Transducer Composition: Rename from TWiki to MediaWiki style)
Latest revision as of 23:43, 1 January 2017
Renormalized Transducer Composition
String Transducers can be viewed as conditionally-normalized Pair HMMs modeling the mutation process over a finite time interval . Two such string transducers, and , can be composed in series (Holmes, 2003). States involving only the intermediate sequence can be eliminated from the composite transducer , yielding a transducer with an inflated state space modeling the time interval .
Let's say each of the -transducers has states, then the composed -transducer has around states. The purpose of this exercise is (i) to find this -state transducer and (ii) to find an approximately equivalent, renormalized -state transducer, that approximates the time interval (e.g. in a minimum-relative-entropy sense; c.f. Wikipedia:Variational_Bayes).
Applications: to find efficient approximations to difficult string transducer compositions, and to better understand the structure of such compositions.
Some first ideas:
- As a first start, a minimal affine-gap transducer should be considered.
- An empirical/simulation approach might also be taken to this problem.
- The TKF91 model should be exactly renormalizable (we can model it exactly with a fixed-topology transducer at all time scales). Is this borne out by the analysis?
See Teaching.PrincipledApproximationToLongIndelModel for more background.
State diagrams for a minimal affine-gap transducer
The Graph Viz diagrams on the following pages illustrate the state spaces of the elementary () and composite () transducers, when the original transducer is based on a simple three-state pair HMM for global alignment with an affine gap penalty.
Section moved to separate page: Gotoh Transducer.
Serial composition of two Gotoh transducers
Section moved to separate page: Serial Composition Of Gotoh Transducers.
Section moved to separate page: Singlet Transducer.
Holmes &: Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics 2003;19 Suppl 1:i147-57. (pdf)(errata)