Gotoh transducer

A transducer, , capable of global alignment with affine gap penalty.

See TransducerLegend for explanations of symbols in this diagram.

digraph G {

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

W [shape=doubleoctagon, color=red]; X [shape=doubleoctagon, color=red];

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

S->I [label=a]; S->W [label=b]; S->X [label=c];

M->I [label=d]; M->W [label=e]; M->X [label=f];

D->I [label=p]; D->W [label=q]; D->X [label=r];

I->I [label=v]; I->W [label=w]; I->X [label=x];

W->E [label=1]; W->M [label=1];

X->E [label=1]; X->D [label=1];

label="Transducer version of Gotoh machine"; }

Probabilistic constraints:

• a + b + c = 1,
• d + e + f = 1,
• p + q + r = 1,
• v + w + x = 1.

Typically outgoing transitions from S are the same as those from M:

• a = d;
• b = e;
• c = f.

The D->I transition (weight p) is unnecessary for separable distributions over insertions & deletions, but may be desirable for several purposes:

1. it appears in TKF91;
2. without it, alignments like have zero likelihood, while those like do not;
   • note that fp = dx required for strict symmetry, but this is NOT the case in TKF91;
3. (speculatively) it may be required to approximate the serial composition of gotoh transducers (see RenormalizedTransducerComposition).
   • apparent support for this is the observation that it's required for reversible affine gaps in the GotohPairHMM.

The W and X states are equivalent if the condition b/c = e/f = q/r = w/x is satisfied (as is the case in TKF91).

A fuller discussions of the symmetry constraints imposed by reversibility may be found on the GotohPairHMM page.

See also:

• SerialCompositionOfGotohTransducers
• SingletTransducer
• GotohPairHMM
• RenormalizedTransducerComposition