Renormalized Transducer Composition

From Biowiki
Jump to: navigation, search

Renormalized Transducer Composition

Introduction

String Transducers can be viewed as conditionally-normalized Pair HMMs a\stackrel{\Delta T}{\to}b modeling the mutation process over a finite time interval \Delta T. Two such string transducers, a\stackrel{\Delta T}{\to}b and b\stackrel{\Delta T}{\to}c, can be composed in series (Holmes, 2003). States involving only the intermediate sequence b can be eliminated from the composite transducer a\stackrel{\Delta T}{\to}b\stackrel{\Delta T}{\to}c, yielding a transducer a\stackrel{2\Delta T}{\to}c with an inflated state space modeling the time interval 2\Delta T.

Let's say each of the \Delta T-transducers has N states, then the composed 2\Delta T-transducer has around N^2 states. The purpose of this exercise is (i) to find this N^2-state transducer and (ii) to find an approximately equivalent, renormalized N-state transducer, that approximates the time interval 2\Delta T (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 (\Delta T) and composite (2\Delta T) transducers, when the original transducer is based on a simple three-state pair HMM for global alignment with an affine gap penalty.

Gotoh transducer

Section moved to separate page: Gotoh Transducer.

Serial composition of two Gotoh transducers

Section moved to separate page: Serial Composition Of Gotoh Transducers.

Singlet transducer

Section moved to separate page: Singlet Transducer.

References

Holmes &: Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics 2003;19 Suppl 1:i147-57. TWikiDocGraphics.pdf.gif (pdf)(errata)