Transducer legend

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

A string transducer is a finite-state machine that processes an input sequence, X, into an output, Y.

The transducers described here (and in the above-cited paper, Holmes 2003) impose certain restrictions, classifying states into various types and permitting only certain transitions between state types.

On many of the transducer pages to be found on this wiki, these state types are indicated by consistent diagrammatic conventions. These conventions are described on this page.

Transducer state types

The following state types are permitted:

digraph G {

Start [shape=doublecircle, color=red];

Wait [shape=doubleoctagon, color=red];

Insert [shape=house, color=red]; Match [shape=rect, color=red]; Delete [shape=invhouse, color=red];

End [shape=doublecircle, color=red];

Null;

label="Transducer state types"; }

"Null" states are allowed purely for representational convenience (e.g. to reduce the number of transitions in densely-connected models). They should be eliminated before applying transducer composition algorithms, since they are not meaningful. Contrast this with "Wait" states which are similar (in that they don't absorb or emit any symbols) but play a key role in composition (specifically, they are used to queue up "Match" and "Delete" states on inactive branches, while events are occurring on other branches).

Permitted connections between transducer states

The following transitions between state types are permitted:

digraph G {

S [shape=doublecircle, color=red]; E [shape=doublecircle, color=red];

I [shape=house, color=red];

W [shape=doubleoctagon, color=red];

M [shape=rect, color=red]; D [shape=invhouse, color=red];

S->I [label="-/y" fontname="Courier"]; S->W [style=dashed];

W->E [style=dashed];

W->M [label="x/y" fontname="Courier"]; W->D [label="x/-" fontname="Courier"];

I->I [label="-/y" fontname="Courier"]; I->W [style=dashed];

M->I [label="-/y" fontname="Courier"]; M->W [style=dashed];

D->I [label="-/y" fontname="Courier"]; D->W [style=dashed];

label="Transducer edge types"; }

Permitted "transition types" in a string transducer for sequence alignment. The edge labels have the following meaning:

Edges with no inputs or outputs are represented by dashed lines. Edges with inputs, outputs or both (x, y or xy) are represented by solid lines.

Every transition into a given state must have the same input symbol (x) and/or the same output symbol (y). Thus, although the above diagram shows inputs and outputs occurring on transitions between states (as in the Mealy machine) it's actually more appropriate to think of the inputs/outputs occurring in the states themselves (as in the Moore machine).

References

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