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:- Holmes I. Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics. 2003;19 Suppl 1:i147-57.
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)."
- "For the collapsed transition probability
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):, that: 
We introduce some new definitions: 
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:
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
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 
, 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 |
 |
 |
|
 |
 |
|
 |
 |
|
 |
 |
|
 |
|
|
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
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 
Site map
Blog web
Users
Groups
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
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