# Recovering species from a phylogenetic tree

This question is based on Problem 2 from the 'Bioinformatics contest' of 2018.

Given a phylogenetic tree $T=(V,E)$ of $n$ vertices, in which some leaves are assigned an integer color $c$ from $[1,n]$, the task is to find a coloring of the vertices $C:V\rightarrow [1,n]$ such that the subtree induced by each color is convex, i.e. there is exactly one vertex that has no parent in the induced subgraph of that color. An equivalent formulation is that the subgraphs induced by each color must be connected.

We are given that there exist a coloring meeting these constraints (there may be multiple). What is an efficient algorithm to find such a coloring?

Biological interpretation: The idea is that we're only given that some taxa (leaves in the tree) are of the same species and we do know the full ancestor tree. The assumption of convexity of a species means that each species has a common ancestor of the same species. Of course, this information isn't always sufficient to reconstruct the whole tree, but it might recover significant parts.

BONUS: So far, this is only the first case of the problem given in the contest. Observe that the above definitions remain unchanged if we replace $T$ by a DAG $D$ with a single vertex without parent (=single source DAG). Is there an efficient algorithm that solves this problem on general single source DAG's or edge-cactus single source DAG's?

I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves.

Algorithm: First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (with $v$ included).

We traverse the tree 'layer by layer' from leaves to the root: Our first layer consists of all leaves. The next layer is constructed by taking the set of parents from all vertices in the current layer, which we repeat until we reach the root.

Then, we fill in the field $v.subcolors$ for all vertices $v$ in our layer. This is easy to do, as we know that $w.subcolors$ is already set for all children of $v$, as those belong to the previous layer we've already visited.

Observe that some vertex $v$ must be of color $c$ if and only if it separates two vertices of color $c$, i.e. it lies on the (unique!) path between two vertices of color $c$. We can determine whether $v$ separates some vertices easily if we know what colors lie in the components formed by removing $v$ from the tree: if the color $c$ lies in two distinct such components, $v$ must separate some vertices in those components.

We can efficiently find the colors in the subtree of the children of $v$, as that is given by $v.subcolors$. The parent of $v$ is a bit more tricky. However, if the parent has already been colored with color $c$, $v$ can be a separator of some vertex the component of the parent only if that vertex has color $c$! Otherwise, if there were some other color $c'$, the parent of $v$ would also separate those vertices. But the parent has color $c$, which means that the coloring of the parent of $v$ is incorrect. This contradicts our assumption that we know the correct color of the parent (note that we have assumed a valid coloring exists!)

So, we can now color the vertices by traversing the tree from root to leaves, again layer by layer: we check at each vertex $v$ whether it separates vertices of some color (as a valid coloring exists, this is at most once color) and fill in that color. If it separates no vertices of the same color, we simply give it an unused color from $[1,n]$.

Efficiency: Coloring the sub-tree requires traversing the tree from bottom to top. As we need to compute with the field $v.subcolors$ at most once for every edge in the tree, this part takes $O(|E|) = O(|V|) = O(n)$ time.

For the down-traversal, we must perform a comparison again for each edge. We can check for each color and vertex adjacent to $v$ whether it occurs and see if it is a separator if it occurs twice. This takes $O(\mathrm{degree}(v)\cdot |C|)$ time if we store the color sets in a hash-table, where $|C|=n$, the number of colors. As the average degree of a tree is constant, performing this operation on all vertices takes $O(n^2)$ time.

So, in total, the algorithm runs in $O(n^2)$ time. This turned out to be fast enough for the testcases given in the contest.

This time could maybe be improved by using an efficient union algorithm to check the separator more efficiently. (Union-find doesn't seem to do the trick, as the sets aren't disjoint)

Algorithm:

1. Find the Lowest Common Ancestor of each color: this node can act as source for the color.
2. Starting from each source, paint all their descendants doing a Depth First Search (the search must stop when another LCA is visited).
3. If the root of the tree is not painted, paint it and all its unpainted descendants (via DFS) with the color of the highest LCA.

Finding the LCA of a set of nodes can be done by searching for the LCA in this way: $LCA(n_1,n_2,\ldots) = LCA(n_1, LCA(n_2, LCA(\ldots)))$.

There are many algorithms for finding the LCA of a pair of nodes. The fastest in this case would be to use some $O(n)$ preprocessing technique (Wipipedia lists some), which then allows for constant time queries (again, $O(n)$ queries tops). The complexity of this algorithm is thus $O(n)$.

In this article you can find a simpler $O(n\log n)$ approach that would suffice in the case of the Bioinformatics Contest.

• Thanks for the edits! Do you have an argument for the correctness of this algorithm or justification why this gives a valid solution? – D.W. Mar 3 '18 at 17:25