# Renormalized Transducer Composition

## Contents

**Renormalized Transducer Composition**

## Introduction

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.

### 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. (pdf)(errata)