Transducer Composition Errata < Main

This page will be used to document corrections to the algorithms published in the following paper:

Additional documentation of transducer jargon can be found on the phylocomposer page.

Collapsed EHMM transition probability

The corrected version, shown below, has been implemented in the DART source code for some time, but has been undocumented save for a few obscure comments in one source file (DartSrc:handel/inline_ehmm.h, constructor for class CollapsedETrans).

The collapsed transition probability $t(\phi,\phi')$ where $\phi$ is the source state and $\phi'$ the destination state can be written as a product of factors:

$t(\phi,\phi') = WXYZ$

The meaning of these factors is as follows.

First, recall the following definitions from the original paper (Holmes, 2003):

Tree nodes are numbered 1,2,3...N and are sorted in preorder
The "root branch" from node 1 to node 2 must exist, and must be the only branch from node 1
${\bf D}(n)$ is the set of all descendants of node
Branches are numbered by the node they lead to, i.e. 2,3...N
is the "branch length" leading to node , so e.g. is the root branch length
A "branch transducer" is associated with every branch
$\tau(\psi,\psi';T)$ is the transition probability from $\psi$ to $\psi'$ for a branch transducer with branch length
$\Psi$ is the state space of the branch transducer (and is assumed to be independent of branch length)
$\chi(\psi)$ is the state type of $\psi$ for $\psi \in \Psi$ , and takes values in $\left\{ {\tt S}, {\tt E}, {\tt W}, \stackrel{xy}{{\tt M}}, \stackrel{x}{{\tt D}}, \stackrel{y}{{\tt I}} \right\}$

Note that "branch length" can be a continuous real variable, but it doesn't have to be; in fact it can be any label associated with the branch.

Also recall, for any Collapsed EHMM state $\phi$ , that:

$\psi_n$ is the state of the transducer on the branch leading to node
$\chi_n \equiv \chi(\psi_n)$ is the state type of $\psi_n$
$\beta(\phi)$ is the emitter node of $\phi$ , i.e. the highest-numbered Insert node:

$\displaystyle \beta(\phi) = \max \left\{ 2,\ \ n : \chi_n = \stackrel{y}{\tt I} \right\}$

We introduce some new definitions:

$\gamma(\phi)$ is the first node that is "eclipsed" by the emitter in state $\phi$ , or N+1 if none are:

$\gamma(\phi) = \min \{ N+1,\ \ n : n > \beta(\phi), n \notin {\bf D}(\beta(\phi)) \}$

$\upsilon(\psi,\psi';T)$ is the effective transition probability via intermediate wait states:

$\displaystyle \upsilon(\psi,\psi';T) = \tau(\psi,\psi';T) + \sum_{\psi'' \in \Psi:\chi(\psi'') = {\tt W}} \tau(\psi,\psi'';T) \tau(\psi'',\psi';T)$

$m = \beta(\phi')$ is a shorthand for the destination emitter.

The algorithm for deciding whether a transition is allowed is as follows. The composite transducer state is first partitioned into subtrees as in the following table. For every node within each subtree, the appropriate condition must be satisfied if the transition is to be allowed:

Subtree	Condition	Term in $t(\phi,\phi')$
$2 \leq n < \beta(\phi')$	$\psi_n = \psi'_n$
$n = \beta(\phi')$	$\tau(\psi_n,\psi'_n;T_n) > 0$
$\beta(\phi') < n < \gamma(\phi')$	$\upsilon(\psi_n,\psi'_n;T_n) > 0\ \vee\ \left(\psi_n = \psi'_n\ \wedge\ \chi_n={\tt W}\right)$
$\gamma(\phi') \leq n < \gamma(\phi)$	$\tau(\psi_n,\psi'_n;T_n) > 0\ \vee\ \left(\psi_n = \psi'_n\ \wedge\ \chi_n={\tt W}\right)$
$\max\left(\gamma(\phi),\gamma(\phi')\right) \leq n \leq N$	$\psi_n = \psi'_n$

A description of factors W,X,Y,Z follows.

Factor prevents transducers from changing state if they are prior to the destination emitter, or eclipsed by both source and destination emitters:

$\displaystyle W = \left( \prod_{n=2}^{m-1} \delta(\psi_n = \psi'_n) \right) \times \left( \prod_{n=\max\left(\gamma(\phi),\gamma'(\phi)\right)}^N \delta(\psi_n = \psi'_n) \right)$

Factor corresponds to the change of state of the transducer at the destination emitter:

$X = \tau (\psi_m, \psi'_m ;T_m)$

Factor collects contributions from descendants of the destination emitter:

$\displaystyle Y = \prod_{n = m + 1}^{\gamma(\phi') - 1} y_n$

where

$y_n = \left\{ \begin{array}{rl} \upsilon(\psi_n,\psi'_n;T_n) & \mbox{if $\chi_n \neq {\tt W}$ or $\chi'_n \neq {\tt W}$} } \\ \delta(\psi_n = \psi'_n) & \mbox{if $\chi_n = \chi'_n = {\tt W}$} \end{array} \right.$

These transitions can use intermediate Wait states, which is why we use $\upsilon$ rather than $\tau$ .

Factor collects contributions from newly eclipsed transducers:

$\displaystyle Z = \prod_{n = \gamma(\phi')}^{\gamma(\phi) - 1} z_n$

where

$z_n = \left\{ \begin{array}{rl} \tau(\psi_n,\psi'_n;T_n) & \mbox{if $\chi_n \neq {\tt W}$} } \\ \delta(\psi_n = \psi'_n) & \mbox{if $\chi_n = {\tt W}$} \end{array} \right.$

It is trivial to generalize the above formalism so that the state space $\Psi$ of the branch transducer can depend on the branch label T_n

, as in the phylocomposer program.

Corrections to "Using guide trees to construct multiple-sequence evolutionary HMMs" (Holmes, 2003)

Collapsed EHMM transition probability