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

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

Currently there is only one correction.

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

## Collapsed EHMM transition probability

The correction applies to the following portion of the manuscript as published:

• Final paragraph, Section "THE COLLAPSED EHMM" (second column, page i154)
• "For the collapsed transition probability to be nonzero, it is required [...] or back up (to an ancestor)."

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 where is the source state and the destination state can be written as a product of factors:

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
• 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
• is the transition probability from to for a branch transducer with branch length
• is the state space of the branch transducer (and is assumed to be independent of branch length)
• is the state type of for , and takes values in

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 , that:

• is the state of the transducer on the branch leading to node
• is the state type of
• is the emitter node of , i.e. the highest-numbered Insert node:

We introduce some new definitions:

• is the first node that is "eclipsed" by the emitter in state , or N+1 if none are:
• is the effective transition probability via intermediate wait states:
• 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

A description of factors follows.

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

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

Factor collects contributions from descendants of the destination emitter:

where

These transitions can use intermediate Wait states, which is why we use rather than .

Factor collects contributions from newly eclipsed transducers:

where

It is trivial to generalize the above formalism so that the state space of the branch transducer can depend on the branch label , as in the phylocomposer program.

IanHolmes - 07 Jun 2007

Error during latex2img:
ERROR: problems during latex
INPUT:
\documentclass[fleqn,12pt]{article}
\usepackage{amsmath}
\usepackage[normal]{xcolor}
\setlength{\mathindent}{0cm}
\definecolor{teal}{rgb}{0,0.5,0.5}
\definecolor{navy}{rgb}{0,0,0.5}
\definecolor{aqua}{rgb}{0,1,1}
\definecolor{lime}{rgb}{0,1,0}
\definecolor{maroon}{rgb}{0.5,0,0}
\definecolor{silver}{gray}{0.75}
\usepackage{latexsym}
\begin{document}
\pagestyle{empty}
\pagecolor{white}
{
\color{black}
\begin{math}\displaystyle \psi\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \phi'\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \gamma(\phi) = \min \{ N+1,\ \ n : n > \beta(\phi), n \notin {\bf D}(\beta(\phi)) \}\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \chi(\psi)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \tau(\psi,\psi';T)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \beta(\phi') < n < \gamma(\phi')\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \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)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle T_n\end{math}
}
\clearpage
{
\color{black}
\begin{multline*}\displaystyle 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.\end{multline*}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle W,X,Y,Z\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \upsilon(\psi,\psi';T)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle T\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \upsilon\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \displaystyle \beta(\phi) = \max \left\{ 2,\ \ n : \chi_n = \stackrel{y}{\tt I} \right\}\end{math}
}
\clearpage
{
\color{black}
\begin{multline*}\displaystyle 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.\end{multline*}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle Z\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle n = \beta(\phi')\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle t(\phi,\phi') = WXYZ\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle W\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle T_2\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle X\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \left\{ {\tt S}, {\tt E}, {\tt W}, \stackrel{xy}{{\tt M}}, \stackrel{x}{{\tt D}}, \stackrel{y}{{\tt I}} \right\}\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \tau\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \max\left(\gamma(\phi),\gamma(\phi')\right) \leq n \leq N\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle {\bf D}(n)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \chi_n \equiv \chi(\psi_n)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \phi\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \displaystyle Z = \prod_{n = \gamma(\phi')}^{\gamma(\phi) - 1} z_n\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \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)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \psi_n\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle n\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \psi_n = \psi'_n\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle t(\phi,\phi')\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \psi'\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \Psi\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \tau(\psi_n,\psi'_n;T_n) > 0\ \vee\ \left(\psi_n = \psi'_n\ \wedge\ \chi_n={\tt W}\right)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \tau(\psi_n,\psi'_n;T_n) > 0\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle X = \tau (\psi_m, \psi'_m ;T_m)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \displaystyle Y = \prod_{n = m + 1}^{\gamma(\phi') - 1} y_n\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle m = \beta(\phi')\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \psi \in \Psi\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \beta(\phi)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle 2 \leq n < \beta(\phi')\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \gamma(\phi') \leq n < \gamma(\phi)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle Y\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \gamma(\phi)\end{math}
}
\clearpage
{
\color{black}
\begin{math}\displaystyle \upsilon(\psi_n,\psi'_n;T_n) > 0\ \vee\ \left(\psi_n = \psi'_n\ \wedge\ \chi_n={\tt W}\right)\end{math}
}
\clearpage
\end{document}
STDERR:
This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian)
entering extended mode
(/tmp/lzSnE2KeOa/10lFnnhg9E
LaTeX2e <2009/09/24>
Babel  and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, farsi, arabic, croatian, bulgarian, ukrainian, russian, czech, slov
ak, danish, dutch, finnish, french, basque, ngerman, german, german-x-2009-06-1
9, ngerman-x-2009-06-19, ibycus, monogreek, greek, ancientgreek, hungarian, san
skrit, italian, latin, latvian, lithuanian, mongolian2a, mongolian, bokmal, nyn
orsk, romanian, irish, coptic, serbian, turkish, welsh, esperanto, uppersorbian
, estonian, indonesian, interlingua, icelandic, kurmanji, slovenian, polish, po
rtuguese, spanish, galician, catalan, swedish, ukenglish, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/fleqn.clo)
(/usr/share/texmf-texlive/tex/latex/base/size12.clo))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty
For additional information on amsmath, use the ?' option.
(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty
(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty)
(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty))
(/usr/share/texmf/tex/latex/xcolor/xcolor.sty
(/etc/texmf/tex/latex/config/color.cfg)
(/usr/share/texmf-texlive/tex/latex/graphics/dvips.def))
(/usr/share/texmf-texlive/tex/latex/base/latexsym.sty)
No file 10lFnnhg9E.aux.
(/usr/share/texmf-texlive/tex/latex/base/ulasy.fd) [1] [2] [3] [4] [5] [6]
[7] [8]
! Argument of \multline* has an extra }.

\par
l.57 ...\neq {\tt W}$or$\chi'_n \neq {\tt W}$} } \\ \delta(\psi_n = \psi'_... Runaway argument? \displaystyle y_n = \left \{ \begin {array}{rl} \upsilon (\psi _n,\psi \ETC. ! Paragraph ended before \multline* was complete. \par l.57 ...\neq {\tt W}$ or $\chi'_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

! Missing $inserted.$
l.57 ...\neq {\tt W}$or$\chi'_n \neq {\tt W}$} } \\ \delta(\psi_n = \psi'_... ! Missing \endgroup inserted. \endgroup l.57 ...\neq {\tt W}$ or $\chi'_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

! Display math should end with . \par l.57 ...\neq {\tt W} or \chi'_n \neq {\tt W}} } \\ \delta(\psi_n = \psi'_... ! Extra }, or forgotten \endgroup. } l.57 ...\neq {\tt W} or \chi'_n \neq {\tt W}} } \\ \delta(\psi_n = \psi'_... ! LaTeX Error: There's no line here to end. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.57 ...W} or \chi'_n \neq {\tt W}} } \\ \delta (\psi_n = \psi'_n) & \mbox... ! Missing  inserted.  l.57 ...W} or \chi'_n \neq {\tt W}} } \\ \delta (\psi_n = \psi'_n) & \mbox... ! Misplaced alignment tab character &. l.57 ... {\tt W}} } \\ \delta(\psi_n = \psi'_n) & \mbox{if \chi_n = \chi'_... ! Misplaced \crcr. \endarray ->\crcr \egroup \egroup l.57 ... \chi_n = \chi'_n = {\tt W}} \end{array} \right.\end{multline*} ! Extra }, or forgotten . \endarray ->\crcr \egroup \egroup l.57 ... \chi_n = \chi'_n = {\tt W}} \end{array} \right.\end{multline*} ! Extra }, or forgotten . \endarray ->\crcr \egroup \egroup l.57 ... \chi_n = \chi'_n = {\tt W}} \end{array} \right.\end{multline*} ! LaTeX Error: \begin{multline*} on input line 57 ended by \end{array}. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.57 ... \chi_n = \chi'_n = {\tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.57 ... \chi_n = \chi'_n = {\tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.57 ...n = \chi'_n = {\tt W}} \end{array} \right .\end{multline*} ! Extra \right. l.57 ... = \chi'_n = {\tt W}} \end{array} \right. \end{multline*} ! Misplaced \cr. \math@cr@@@ ->\cr l.57 ...tt W}} \end{array} \right.\end{multline*} ! Misplaced \noalign. \math@cr@@ ... \iffalse }\fi \math@cr@@@ \noalign {\vskip #1\relax } l.57 ...tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.57 ...tt W}} \end{array} \right.\end{multline*} ! Missing } inserted. } l.57 ...tt W}} \end{array} \right.\end{multline*} Underfull \hbox (badness 10000) in paragraph at lines 57--57 []\OML/cmm/m/it/12 ^^N\OT1/cmr/m/n/12 (\OML/cmm/m/it/12 [] \OT1/cmr/m/n/12 = \OML/cmm/m/it/12 []\OT1/cmr/m/n/12 )[]  [] ! Too many }'s. \egroup l.57 ...tt W}} \end{array} \right.\end{multline*} ! LaTeX Error: \begin{document} ended by \end{multline*}. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.57 ...tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.57 ...tt W}} \end{array} \right.\end{multline*} ! Display math should end with.

\endgroup
l.57 ...tt W}$} \end{array} \right.\end{multline*} ! Extra \endgroup. \endgroup l.57 ...tt W}$} \end{array} \right.\end{multline*}

! Too many }'s.
l.58 }

[9] [10] [11] [12] [13] [14]
! Argument of \multline* has an extra }.

\par
l.87 ...n;T_n) & \mbox{if $\chi_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

Runaway argument?
\displaystyle z_n = \left \{ \begin {array}{rl} \tau (\psi _n,\psi '_\ETC.
! Paragraph ended before \multline* was complete.

\par
l.87 ...n;T_n) & \mbox{if $\chi_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

! Missing $inserted.$
l.87 ...n;T_n) & \mbox{if $\chi_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

! Missing \endgroup inserted.

\endgroup
l.87 ...n;T_n) & \mbox{if $\chi_n \neq {\tt W}$} }
\\ \delta(\psi_n = \psi'_...

! Display math should end with . \par l.87 ...n;T_n) & \mbox{if \chi_n \neq {\tt W}} } \\ \delta(\psi_n = \psi'_... ! Extra }, or forgotten \endgroup. } l.87 ...n;T_n) & \mbox{if \chi_n \neq {\tt W}} } \\ \delta(\psi_n = \psi'_... ! LaTeX Error: There's no line here to end. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.87 ...mbox{if \chi_n \neq {\tt W}} } \\ \delta (\psi_n = \psi'_n) & \mbox... ! Missing  inserted.  l.87 ...mbox{if \chi_n \neq {\tt W}} } \\ \delta (\psi_n = \psi'_n) & \mbox... ! Misplaced alignment tab character &. l.87 ... {\tt W}} } \\ \delta(\psi_n = \psi'_n) & \mbox{if \chi_n = {\tt W... ! Misplaced \crcr. \endarray ->\crcr \egroup \egroup l.87 ...& \mbox{if \chi_n = {\tt W}} \end{array} \right.\end{multline*} ! Extra }, or forgotten . \endarray ->\crcr \egroup \egroup l.87 ...& \mbox{if \chi_n = {\tt W}} \end{array} \right.\end{multline*} ! Extra }, or forgotten . \endarray ->\crcr \egroup \egroup l.87 ...& \mbox{if \chi_n = {\tt W}} \end{array} \right.\end{multline*} ! LaTeX Error: \begin{multline*} on input line 87 ended by \end{array}. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.87 ...& \mbox{if \chi_n = {\tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.87 ...& \mbox{if \chi_n = {\tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.87 ...{if \chi_n = {\tt W}} \end{array} \right .\end{multline*} ! Extra \right. l.87 ...if \chi_n = {\tt W}} \end{array} \right. \end{multline*} ! Misplaced \cr. \math@cr@@@ ->\cr l.87 ...tt W}} \end{array} \right.\end{multline*} ! Misplaced \noalign. \math@cr@@ ... \iffalse }\fi \math@cr@@@ \noalign {\vskip #1\relax } l.87 ...tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.87 ...tt W}} \end{array} \right.\end{multline*} ! Missing } inserted. } l.87 ...tt W}} \end{array} \right.\end{multline*} Underfull \hbox (badness 10000) in paragraph at lines 87--87 []\OML/cmm/m/it/12 ^^N\OT1/cmr/m/n/12 (\OML/cmm/m/it/12 [] \OT1/cmr/m/n/12 = \OML/cmm/m/it/12 []\OT1/cmr/m/n/12 )[]  [] ! Too many }'s. \egroup l.87 ...tt W}} \end{array} \right.\end{multline*} ! LaTeX Error: \begin{document} ended by \end{multline*}. See the LaTeX manual or LaTeX Companion for explanation. Type H for immediate help. ... l.87 ...tt W}} \end{array} \right.\end{multline*} ! Missing  inserted.  l.87 ...tt W}} \end{array} \right.\end{multline*} ! Display math should end with.

\endgroup
l.87 ...tt W}$} \end{array} \right.\end{multline*} ! Extra \endgroup. \endgroup l.87 ...tt W}$} \end{array} \right.\end{multline*}

! Too many }'s.
l.88 }

[15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29]
[30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44]
[45] [46] [47] (./10lFnnhg9E.aux) )
(see the transcript file for additional information)
Output written on 10lFnnhg9E.dvi (47 pages, 12852 bytes).
Transcript written on 10lFnnhg9E.log.
`
Topic revision: r108 - 2007-06-10 - IanHolmes

 Home Main Web View Edit Account

Copyright © 2008-2013 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback