Bijections for Ranked Tree-Child Networks

Here, we give a top-down construction which (uniquely) produces all RTCNs with $\ell+1$ leaves. A similar construction was described in [1] where the authors used the concept of decorated RTCNs. We will sidestep this concept which gives a (slightly) simpler construction.

Assume we have a given RTCN with $\ell$ leaves. Then, we perform either one of the following two operations (see Figure 4 for examples).

(O-i)

Pick two labels $a,b$ from the set $\{1,\ldots,\ell+1\}$, remove the label $\ell$ from the RTCN and attach to its leaf two children with labels $a,b$. Finally, relabel all the other leaves of the RTCN in an order-consistent way with the remaining labels from $\{1,\ldots,\ell+1\}\setminus\{a,b\}$.

(O-ii)

Pick two labels $a<b$ from $\{1,\ldots,\ell+1\}$ and a label $c$ from $\{1,\ldots,\ell+1\}\setminus\{a,b\}$. Next, find the relative ranks, say $a^{\prime}<b^{\prime}$, of $a<b$ in $\{1,\ldots,\ell+1\}\setminus\{c\}$. Remove $a^{\prime},b^{\prime}$ from the RTCN and attach a reticulation event to their leaves with the children corresponding to the leaf which had the label $a^{\prime}$ being a leaf with label $a$ and the reticulation vertex, the children corresponding to the leaf which had the label $b^{\prime}$ being a leaf with label $b$ and the (same) reticulation vertex and the child of the reticulation vertex being a leaf with label $c$. Finally, relabel all the other leaves of the RTCN in an order-consistent way with the labels from $\{1,\ldots,\ell+1\}\setminus\{a,b,c\}$.

Since both of these operations are reversible, we have the following result.

Moreover, this construction also immediately gives (1).

Here, we explain how all boat sequences involving $\ell+1$ people can be constructed from those involving $\ell$ people. (Note that this reveals a recursive structure inherent to boat sequences that was not considered in [1].)

First, note that a boat sequence involving $\ell$ people can be represented by an array with $2$ rows where the first row has $\ell-1$ entries and the second has $\ell-2$ entries, namely, the first row contains the set of numbers of the people sent in the $i$-th step and the second row contains the singleton of the number of the person who returned in the $i$-th step; see bottom left array in Figure 5 for an example.

Now, each such array can be mapped to a corresponding array where the numbers are replaced by the relative ranks of the people within the group on their shore, e.g., if $\{2,5\}$ are sent with $\{2,3,5,6\}$ at the same shore, then $\{2,5\}$ is replaced by $\{1,3\}$. Call the resulting map $r$; see bottom of Figure 5.

Note that the map $r$ is clearly a bijection from the above arrays representing boat sequences to arrays where in the first row, we have a subset of size $2$ of $\{1,\ldots,\ell\}$, followed by a subset of size $2$ of $\{1,\ldots,\ell-1\}$, etc. until the set $\{1,2\}$ and in the second row, we have a subset of size $1$ of $\{1,2\}$, followed by a subset of size $1$ of $\{1,2,3\}$, etc. until a subset of size $1$ of $\{1,\ldots,\ell-1\}$.

Now, we apply the following operations on the latter arrays: we shift all entries of the first row to the right by one position, add a subset of size $2$ of $\{1,\ldots,\ell+1\}$ in the (now empty) first position and add a subset of size $1$ of $\{1,\ldots,\ell\}$ at the end of the second row; see the downwards arrow in Figure 6.

Finally, by using the inverse of $r$, we obtain an array for a boat sequence involving $\ell+1$ people; see the bottom left array in Figure 6.

Since the above process is reversible, we obtain the following result.

We will now explain how to synchronize the constructions from the above two paragraphs to get a bijection between RTCNs and boat sequences. This bijection is defined recursively.

Assume we have given a RTCN on $\ell+1$ leaves. Reverse the recursive construction from Proposition 1 to obtain a RTCN on $\ell$ leaves. By induction hypothesis, this RTCN is mapped on a boat sequence which is represented by an array as described in the previous paragraph. We apply the map $r$ to this array. Now, depending on which of the two operations was used in Proposition 1 to construct the RTCN on $\ell+1$ leaves from that of $\ell$ leaves, we do the following to the array of ranks.

(i)

If Operation (O-i) was used, then move all the pairs from the first row by one position and add $\{a,b\}$ as the first entry. Also, add $\{\ell\}$ at the end of the second row.

(ii)

If Operation (O-ii) was used, then again move all the pairs from the first row by one position and add $\{a,b\}$ as the first entry. Add the relative rank of $c$ in $\{1,\ldots,\ell+1\}\setminus\{a,b\}$ to the end of the second row.

Finally, apply the inverse of $r$ to the above array to obtain the desired boat sequence.

More generally, in order to get the corresponding boat sequence for a RTCN on $\ell$ leaves, we first have to reduce it to the RTCN on $2$ leaves by applying Proposition 1 $\ell-2$ times and retain the operations from the first paragraph for each step. Then, we can start from the (trivial) boat sequence and use the above procedure $\ell-2$ times to construct the corresponding boat sequence; see Figure 7 for an example.

Also, from the above, it is clear that branching events correspond to steps where the person with the maximal rank was picked for the return trip (or, using the language introduced just before Theorem 1, the most skilled person on the opposite shore). This proves Theorem 1 from the introduction.

Given a RTCN with $\ell$ leaves labeled $1$ to $\ell$, define its profile as the sequence $(q_{i})_{i=1}^{\ell-1}\in\{0,1\}^{\ell-1}$ where $q_{i}=0$ if and only if the $i$-th event from the bottom is a branching event (see left of Figure 8). Note that we necessarily have $q_{\ell-1}=0$, as only two lineages (i.e., vertical edges) are available to merge for the last event. Suppose $\sum_{i=1}^{\ell-1}q_{i}=k$, that is, that the RTCN under consideration has $k$ reticulation events, and let $a_{1}<a_{2}<\ldots<a_{k}$ be the indices $i\in\{1,\ldots,\ell-2\}$ such that $q_{i}=1$, corresponding to the reticulation events in question (note that the reticulation event $a_{i}$ happens at time $\ell-a_{i}$, with the notation from Figure 1-(b)).

Next, note that we can consider lineages above (and below) each event to be naturally ordered as follows. Assuming that lineages just below event $i$ are labeled $1$ to $\ell-i+1$ and that the event is a branching event, label the $\ell-i$ lineages just above the event with the integers $1$ to $\ell-i$ so that their order reflects the order after the branching event, with the parent lineage identified with its child whose label is smaller. Similarly, assuming $i$ is a reticulation event, order the lineages present just above the event $i$ consistently with their order after the event (ignoring the hybrid lineage resulting from the reticulation event). This is by no means the only possible convention (other conventions would yield equivalent bijections), but we may use it to determine the left-to-right order of lineages when the RTCN is drawn in the plane (so that we can say that the $\ell-i$ lineages above event $i$ are labeled “left-to-right” with the numbers $1$ to $\ell-i$). The planar embedding induced by this convention is depicted on the right of Figure 8: the RTCN on the left is redrawn on the right with lineages ordered left to right according to their current labels, which are explicitly indicated above and below each event; in the representation on the right, parent lineages of reticulation events are drawn directly above the respective non-hybrid child lineages.

In order to obtain a ranked binary tree, we will replace each of the $k$ reticulation events of the RTCN with a branching event; at the same time, we shall keep track of additional information allowing the recovery of the original reticulation event.

Build the corresponding ranked binary tree to our RTCN by considering in turn the events $a_{1},\ldots,a_{k}$. The result of the reticulation event $a_{1}$ is given by two lineages $L_{1}<L_{2}$, labeled $l_{1}<l_{2}$ above the reticulation event, and a third hybrid lineage $L_{3}$; replace this by a branching event that yields $L_{1},L_{2}$ from a single parent lineage $P$ and leaves $L_{3}$ intact. Some convention is needed in order to match lineages $P,L_{3}$ to lineages $l_{1},l_{2}$; we identify $P$ with $l_{1}$ and assign the evolution of the hybrid lineage $L_{3}$ to the lineage $l_{2}$ (Figure 9). Labels assigned to lineages below event $a_{1}$ are unchanged by this procedure, but labels above the event are recomputed according to the rules we explained previously. In particular, labels immediately above the event $a_{1}$ range between $1$ and $\ell-a_{1}$; the lineage that used to be labeled $l_{1}$ is now labeled $l_{1}^{\prime}$ and the lineage that used to be labeled $l_{2}$ is now labeled $l_{2}^{\prime}$ where the values of $l_{1}^{\prime},l_{2}^{\prime}$ depend on $L_{1},L_{2},L_{3}$: if $L_{3}<L_{1}$, then $l_{1}^{\prime}=L_{1}=l_{1}+1$ and $l_{2}^{\prime}=L_{3}$; if $L_{2}<L_{3}$, then $l_{1}^{\prime}=L_{1}=l_{1}$ and $l_{2}^{\prime}=L_{3}-1$; if $L_{1}<L_{3}<L_{2}$, then $l_{1}^{\prime}=L_{1}=l_{1}$ and $l_{2}^{\prime}=L_{3}$.

The result of this operation is a RTCN $T_{1}$ with $k-1$ reticulation events. In order to be able to reinstate the original reticulation, it is enough to keep track of $a_{1}$ (identifying the branching event to be turned back into a reticulation event) and a number $b_{1}$ that identifies the lineage to turn back into the original hybrid. Note that the label $l_{2}^{\prime}$, for example, would allow the recovery of the original RTCN; $l_{2}^{\prime}$ is an integer between $1$ and $\ell-a_{1}$, but cannot take all values in the range independently of $T_{1}$, as it cannot be equal to $l_{1}^{\prime}$, that is, to the label of the parent lineage of the branching event $a_{1}$. We therefore define the number $b_{1}$ as $l_{2}^{\prime}$ if $l_{2}^{\prime}<l_{1}^{\prime}$ and $l_{2}^{\prime}-1$ otherwise. This way, we have $1\leq b_{1}\leq\ell-1-a_{1}$; since $l_{1}^{\prime}$ can be determined from $T_{1}$, the pair $(a_{1},b_{1})$ is enough to recover $l_{2}^{\prime}$ and thus the original RTCN (as we will further discuss later).

We repeat this operation for each reticulation to obtain a final ranked binary tree $T_{k}$ and a sequence $(a_{1},b_{1}),\ldots,(a_{k},b_{k})$ where $1\leq b_{i}\leq\ell-1-a_{i}$: see Figure 10 for an example.

This sequence of $k$ pairs can be naturally encoded by the permutation $\sigma_{k}=(a_{1},b_{1}+a_{1})\cdot(a_{2},b_{2}+a_{2})\cdot\ldots\cdot(a_{k},a_{k}+b_{k})$ in the symmetric group $\mathcal{S}_{\ell-1}$ (where we adopt the convention that composition of permutations is obtained via multiplication from the right); this is the product of $k$ transpositions such that $a_{1}<\ldots<a_{k}$ and $b_{i}+a_{i}>a_{i}$. The latter condition is actually equivalent to the permutation being a product of $\ell-1-k$ disjoint cycles, as clarified by the following lemma:

As a result, from our initial RTCN we have constructed a pair given by a ranked binary tree and a permutation in $\mathcal{S}_{\ell-1}$ which, by applying Lemma 1 with $n=\ell-1$, we find to be a product of as many disjoint cycles as the number of branching events in the original RTCN (that is, $\ell-1-k$). We have already sketched how we can revert each change made to recover the original RTCN, but we give a more complete description of the inverse construction below.

We are given a ranked binary tree with $\ell$ labeled leaves and a permutation $\sigma$ in $\mathcal{S}_{\ell-1}$ with $\ell-1-k$ cycles.

First of all, by Lemma 1 we can express $\sigma$ in a unique way as a product of transpositions of the form previously described, as $(x_{1},y_{1})\cdot\ldots\cdot(x_{k},y_{k})$ with $0<x_{1}<\ldots<x_{k}$ and $x_{i}<y_{i}\leq n$ for $1\leq i\leq k$. We then obtain our pairs $(a_{i},b_{i})_{i=1}^{k}$ as $a_{i}=x_{i}$, $b_{i}=y_{i}-x_{i}$.

All that is left to do is replace the branching events $a_{k},\ldots,a_{1}$ in our ranked binary tree (numbered from the bottom) by reticulation events. We can still number our lineages from $1$ to $\ell-i$ above branching event $i$ (again, think of the order induced by assigning to the parent the label of the smaller child).

For $i=k,\ldots,1$ in turn, consider lineages $1$ to $\ell-a_{i}$ right above branching event $a_{i}$ and let $l$ be the label assigned to the parent of the branching event $a_{i}$; pick the past of lineage $b_{i}+s$ where $s=1$ if $b_{i}\geq l$ and $s=0$ otherwise, to become the past of the larger child issued from the branching event (while the past of the branching event becomes the past of the smaller child), and make the future of lineage $b_{i}+s$ into a hybridised version of the two lineages involved in the branching event.

This operation yields a RTCN and is precisely the inverse of the one previously described (see again Figure 10 where one can follow the steps backwards to recover the RTCN from the final ranked binary tree).