description of an algorithm for detecting whether or not a character pattern is parsimony informative when there are ambiguously scored OTUs

parsimony-informative-check.tex

\documentclass{article}
\usepackage{amsmath}
\usepackage{paralist}
\DeclareMathOperator*{\argmin}{argmin}
\begin{document}
\section*{Note on detecting whether a pattern is parsimony informative}
Let $\ell(T, c)$ be the unordered parsimony length of discrete character pattern $c$ on 
tree $T$ and $\ell(T, c, i)$ be the parsimony length that combination of pattern and tree
 when state $i$ is  enforced as the state for the root of the tree.
Data pattern $c$ is ``parsimony informative'' if and only if, 
there exist 2 trees $T_1$ and $T_2$ such $\ell(T_1, c) < \ell(T_2, c)$.

\subsection*{The maximum length for a character}
Conveniently, the ``star tree'', $T_{\ast}$, (a tree with no internal branches), is guaranteed
to have the largest parsimony length.
So, the determination of whether or not a pattern is parsimony informative boils down to: Does there
    exist a tree $T_1$ such that $\ell(T_1, c) < \ell(T_{\ast}, c)$?

Note that the parsimony length for the star tree is:
\begin{equation}
    \ell(T_{\ast}, c) = \min_i \ell(T_{\ast}, c, i) \mbox{ for } i\in \mathcal{S}
\end{equation}
where $\mathcal{S}$ is the set of states for the datatype, 
and we can refer to a ``star-MP'' state as any member of the set $\mathcal{M}$ where:
\begin{equation}
\mathcal{M} := \argmin_i \left[\ell(T_{\ast}, c, i)\right] \mbox{ for } i\in \mathcal{S}.
\end{equation}

Let $\mathcal{D}(c, i)$ denote the set of OTUs which have state sets for character $c$
    which do not contain state $i$.
Note that:
\begin{equation}
   \ell(T_{\ast}, c, i) = \left|\mathcal{D}(c, i) \right|
\end{equation}
because each of these leaves will require a change when placed on a star tree with root state $i$.

\subsection*{Checking for a tree with a better length}
We can find a tree $T_1$ with a better length than $T_{\ast}$, if
To find tree $T_1$, imagine that we can join two leaves, $x$ and $y$, from the polytomy
    to form a cherry.
$\ell(T_1, c) < \ell(T_{\ast}, c)$ the branches leading to $x$ and $y$ each
    required a change in $T_{\ast}$ and if we can infer a change along the internal branch of 
    $T_1$ and no changes along the terminal edges leading to $x$ and $y$ in $T_1$.
For this to be the case, for a root state $i\in \mathcal{M}$ and leaves $x$ and $y$ such that
\begin{compactenum}
    \item $i\notin c_x$ and $i \notin c_y$ (where $c_x$ is the set of states compatible the
    observations for leaf $x$ for character $c$), and
    \item $c_x \cap c_y \neq \emptyset$.
\end{compactenum}

\subsection*{Algorithm}
A high level description of the algorithm to determine if $c$ is parsimony informative is to:
\begin{compactenum}
    \item find the set of star-MP states, $\mathcal{M}$. see FindMPStateSet
    \item for each state $i \in \mathcal{M}$, find $D(c, i)$, check to see if any state is compatible with
    more than one OTU in $D(c, i)$. If there is such a state then $c$ is parsimony informative.
    \item If that check fails for every member of $M$, then $c$ is not parsimony informative.
\end{compactenum}

\subsection*{Example}
Consider: \\
\begin{tabular}{cl}
name of the OTU & its state set 
\\
A & $\{0,1\}$ \\
B & $\{0,1\}$ \\
C & $\{2\}$ \\
D & $\{0\}$ \\
E & $\{1,2\}$ \\
\end{tabular}\\
In this case, $\mathcal{M} = \{0,1\}$ because putting either of those states at the
root of the star tree would give you a length of 2 steps.

Note that if you considered putting state 1 at the root, it is not clear that you can
    improve on this parsimony length: the only 2 tips that don't show state 1 are tips
    C and D, and they do not overlap in their state sets.
However, if you put state 0 at the root, you realize that a tree that pinches off tips
    C and E as a split could explain the character with only 1 step (a transition to
    the shared state 2).
Thus, the character is parsimony informative.
\end{document}