can be viewed as conditionally-normalized Pair HMMs
modeling the mutation process over a finite time interval
Two such string transducers,
, 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
states, then the composed
-transducer has around
The purpose of this exercise is (i) to find this
-state transducer and (ii) to find an approximately equivalent, renormalized
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?
for more background.
State diagrams for a minimal affine-gap transducer
diagrams on the following pages illustrate the state spaces of the elementary (
) and composite (
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: GotohTransducer
Serial composition of two Gotoh transducers
Section moved to separate page: SerialCompositionOfGotohTransducers
Section moved to separate page: SingletTransducer
Holmes I. Using guide trees to construct multiple-sequence evolutionary HMMs.
Bioinformatics. 2003;19 Suppl 1:i147-57. (pdf)