<reponame>OpenTreeOfLife/otcetera<filename>doc/subproblem-creation.tex
\documentclass[11pt]{article}
\input{preamble.tex}

\newcommand{\phylogeny}{\ensuremath{P}\xspace}
\newcommand{\uncontestedTaxa}{\ensuremath{\mathcal{U}}\xspace}
\usepackage{hyperref}
\hypersetup{backref,  linkcolor=blue, citecolor=black, colorlinks=true, hyperindex=true}
\begin{document}
The source for this in the doc subdirectory of the otcetera
    repo \url{https://github.com/mtholder/otcetera/tree/master/doc}.
\begin{center}
    {\bf Detecting contested taxa using embedded trees} \\
{<NAME>$^{1}$ and <NAME>$^{1,2\ast}$}
\end{center}
\tableofcontents
\section{Contested taxa}
This document is intended to be a more thorough discussion of the
    ``Decomposition into Subproblems'' section of the Supporting
    Information of \citep{HinchliffEtAl2015}.

Here we consider the case of a complete tree representing a taxonomy \taxonomy and
    a list of $N$ phylogenetic estimates, $\mathcal{P} = (P_1, P_2, \ldots, P_N)$, in which the leaf labels of the phylogenetic
    trees is a subset of the leaf label set of the taxonomy.
Note that in \citep{HinchliffEtAl2015}, some phylogenetic trees could have leaves labeled by
    ``higher'' taxa, but that possibility is not covered in this document, because in
    the \propinquity pipeline, these tips are replaced by exemplars of the higher taxon
    at a previous step.

As stated in the glossary for \otc, we say that taxon $K$ is contested
    if and only if 
    at least one tree in $\mathcal{P}$ has a node which must be in conflict
    with the taxon.
    Note that if a tree has members of taxon as children of a polytomy that also contains other taxa, then
        the tree does not display the taxon, but it is also does not contest the taxon.
    Thus ``contests'' is not equivalent to ``does not display'' 
    (although, if a tree {\em does} display a taxon, then 
        it cannot contest that taxon).

\section{Subproblems}
\subsection{Notation for auxiliary data structures}
Let $\uncontestedTaxa$ denote the set of uncontested higher taxa in \taxonomy,
    and $\mathbb{U}$ denote the uncontested taxonomy tree,
    which is created by collapsing any edge leading to
    an internal taxon if that taxon is not in $\uncontestedTaxa$.
$\induced{\mathbb{U}}{P_i}$ denotes the uncontested taxonomy tree induced by the leaf set
    of $P_i$.
$R_i$ denotes a resolved form of $P_i$ which has had polytomies in $P_i$ resolved
    such that $R_i$ displays all groupings in $\induced{\mathbb{U}}{P_i}$.

For every internal node $x$ in $\induced{\mathbb{U}}{P_i}$ we can identify a 
    corresponding node $\corresponding{x}{R_i}$ in $R_i$ (a node which has
    the same descendant leaf label set).
If an internal $y$ in $R_i$ corresponds to no node in $\induced{\mathbb{U}}{P_i}$,
    then $y$ will remain unlabeled.

If, on the other hand, $y$ does correspond to set of $j$ nodes 
    in the induced tree $\induced{\mathbb{U}}{P_i}$ 
    then we can convert this set to an ordered list $(x_1, x_2,\ldots, x_j)$ by mimicking the 
    tip to root ordering of those nodes in $\induced{\mathbb{U}}{P_i}$.
We assign the label of the most tipward taxon ($x_1$) to node $y$, and
    we introduce a set of in series of $j-1$ nodes with in-degree and out-degree of 1
    along the edge that connects $y$ to its parent.
For each of these new nodes we assign it the corresponding taxon $x$.
Let $A_i$ denote the resulting tree obtained from by adding the
    relevant labeled nodes for the uncontested taxa displayed by $R_i$.

\subsection{Description of an uncontested taxon decomposition}
An uncontested taxon decomposition consists of taking the $\taxonomy$
    and the inputs set of phylogenetic estimates and producing a set of 
    tree lists.
For each taxon in $\uncontestedTaxa$, a subproblem will be created.
That subproblem will consist of a set of trees corresponding to slices of input trees
    and $\mathbb{U}$
For input tree $i$, the tree in subproblem $z$ can be obtained by checking
    the resolved, augmented tree $A_i$ for a node, $a$, labelled by the label of taxon $z$.
If no such node is found, then tree $i$ does not intersect with taxon $z$.
If $a$ does exist, the subproblem tree $i$ will consist of the subtree of $A_i$ that
    is created by starting at node $a$ and including nodes and edges tipward until
    a labelled node is found; this labelled node is included in the subproblem, but
    none of its descendants are.
In this way the labelled nodes in tree $A_i$ serve as cut points for breaking each 
    tree into a smaller tree.
The edges of $R_i$ are partitioned among the subproblems.

\bibliography{otcetera}
\end{document}
