# How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider the following random process which labels the nodes of $T$ in a bottom-up order. Given an unlabeled node $x$ whose children $y,z$ have been labeled with words $w_y,w_z$, we assign to $x$ a word $w_x$ as follows:

For each $i \in [n]$:

(1) if $w_y[i], w_z[i]$ are equal to the same letter $a$, then set $w_x[i]$ to $a$;

(2) if $w_y[i], w_z[i]$ are equal to different values $a,b$, then set $w_x[i]$ to $a$ with prob. $p(a)/(p(a)+p(b))$, and to $b$ otherwise.

Let $w_r$ be the random word assigned to the root at the end of this process. Can we devise a polynomial-time strategy to maximize $Var(w_r) = \sum_{i \in [n]} Var(w_r[i])$? This could be done either 'globally' (by constructing the tree at once) or 'online' (by selecting a 'locally optimal' matching for each generation).

The intuition is that a node $u$ represents a 'genetic group' which profiles is described by the distribution of $w_u$, and that we would try to mix groups at each generation in order to maximize the genetic diversity. This is probably NOT desirable in practice due to the possible effects of dominant/recessive mutations.

• So the "degree of freedom" here is the topology of the tree ? If the tree is leaf-labelled by the elements of $S$, is it ok to return a star consisting of root connected to all leaves ? Also, what does it mean to talk about the variance in a categorical domain ? Apr 23 '14 at 14:16
• I couldn't make from the text if the tree is always binary or we can pick the tree structure.
– R B
Apr 23 '14 at 14:53
• At SureshVenkat and RB: I assumed $T$ to be binary by analogy with an artificial breeding process. An extension to higher arities does not seem biologically realistic, but it might be interesting to study what are its potential benefits, if any. I suspect that you can only obtain a faster mixing time at the price of a lesser diversity in the final population, but I don't have any concrete evidence of this intuition. Apr 23 '14 at 20:28