Transducer Legend

From Biowiki
Jump to: navigation, search

Transducer legend

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:

This is a graph with borders and nodes that may contain hyperlinks.
About this image

"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:

This is a graph with borders and nodes that may contain hyperlinks.
About this image

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

Edge label Interpretation Transition type
x/y Input one symbol from X; output one symbol to Y "Match"
x/- Input one symbol from X; output nothing to Y "Delete"
-/y Input nothing from X; output one symbol to Y "Insert"
(none) No symbols input or output "Null"

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