Gotoh Transducer

From Biowiki
Jump to: navigation, search

Gotoh transducer

A transducer, a\stackrel{\Delta T}{\to}b, capable of global alignment with affine gap penalty.

See Transducer Legend for explanations of symbols in this diagram.

Graph image creation requires permission to upload.

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 MDIM have zero likelihood, while those like MIDM do not;
    • note that fp = dx required for strict symmetry, but this is NOT the case in TKF91;
  1. (speculatively) it may be required to approximate the serial composition of gotoh transducers (see Renormalized Transducer Composition).
    • apparent support for this is the observation that it's required for reversible affine gaps in the Gotoh Pair HMM.

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 Gotoh Pair HMM page.

See also: