Combinatorial topological models for phylogenetic networks and the mergegram invariant

Figure 1.  Example of a treegram and its symmetric ultranetwork. On the left, a treegram $ \mathcal{T} _X $ build over $ X = \{x, y, z\} $, where the horizontal axis represents time (traced backwards in the phylogenetic tree setting). On the right, the corresponding symmetric ultranetwork $ U_X $

Figure 2.  Dendrograms, their persistence diagrams and mergegrams. Consider the finite metric subspaces $ X = \{0, 1, 3, 7\} $ and $ Y = \{0, 1, 5, 7\} $ of $ ( \mathbb{R}, |\cdot |) $. (A1) shows the single-linkage dendrogram of $ X $, (A2) shows the $ 0 $-dimensional persistent homology diagram of $ X $, and (A3) shows the mergegram of the single-linkage dendrogram of $ X $. (B1) shows the single-linkage dendrogram of $ Y $, (B2) shows the $ 0 $-dimensional persistent homology diagram of $ Y $, and (B3) shows the mergegram of the single-linkage dendrogram of $ Y $. The datasets $ X $ and $ Y $ have the same $ 0 $-dimensional persistent diagrams but different mergegrams

Figure 3.  Cliquegram and its phylogenetic network. On the left there is a cliquegram $ \mathcal{C} _X $, on the right - the associated phylogenetic network $ N_X $

Figure 4.  The join of two treegrams in the cliquegram setting. An example of cliquegram $ \mathcal{C}_X $ over $ X $ obtained as the join of two treegrams over $ X $. The associated phylogenetic network $ N_X $ of the cliquegram $ \mathcal{C}_X $ can be obtained as the pointwise minimum of the associated ultranetworks of the spanning treegrams of $ \mathcal{C}_X $

Figure 5.  Facegram and its filtration. An example of facegram and its associated filtration

Figure 6.  Comparison of the join of treegrams as cliquegrams and facegrams. Consider the set of three treegrams in the middle of the picture. The structure on the left is obtained by taking the join operation on those treegrams (viewed as cliquegrams) in the lattice of cliquegrams. On the right, the join of the same treegrams (now viewed as facegrams) in the lattice of facegrams is presented. Note that the cliquegram can be obtained from the facegram on the right by squashing the three loops. Hence, sometimes, the facegram contains reticulation loops that are not present in the cliquegram

Figure 7.  Concepts overview. Overview of concepts examined and their relations to each other. Those in bold font are introduced in this work

Figure 8.  On the left there is a cliquegram $ \mathcal{C} _X $, on the right is the associated phylogenetic network $ N_X $

Figure 9.  An example of a facegram and its associated filtration

Figure 10.  The left shows the join operation on cliquegrams. On the right, there is the join operation on the richer structure of facegrams. The cliquegram can be obtained by the facegram by squashing the three loops. So, the facegram contains reticulation cycles that are not seen by the cliquegram

Figure 11.  Facegrams and their face-Reeb graphs for small perturbations. On the top there are three facegrams and on the bottom their associated face-Reeb graphs. On the top of the figure, on the left and to the right of the middle facegram there are two facegrams that are $ \varepsilon $-close to it, in the interleaving distance. However, for small $ \varepsilon\geq0 $, at least for $ \varepsilon $-values that are smaller than half the height of the loop of the middle facegram, the associated Reeb graphs of those facegrams are not $ \varepsilon $-close to the middle facegram, since their difference is at least as large as half of the height of the loop of the middle facegram. That means that a small perturbation of the facegrams can lead to a large difference in the face-Reeb graph of the facegrams

Figure 12.  Visualizations of two facegrams with the same mergegram but different labeled mergegram. Visualizations (a), (c) of two facegrams having isomorphic face-Reeb graphs (if we forget the labels of their edges) and thus the same mergegrams, however differently labeled. The mergegrams correspond in this visualization to the vertical bars without their labels; (b), and (d) show the bars/intervals $ I_\sigma $ together with their label; these are the labeled mergegrams of facegrams (a) and (c), respectively. The coloring associated with each interval is the colors of taxa in the clique. Interpreting the mergegram as a persistence diagram gives plot (e), where the multiplicity of the points is given by the numbers next to the points. The point with lower opacity is the point with infinite lifetime. We can see that the mergegrams are the same in (e) or in (b) and (d) when ignoring the coloring of the bars. On the other hand, the labeled mergegram (and the associated coloring of the bars) shows that the two facegrams differ in one face-set, namely $ (\{x, y, z\}, [2, 3)) $ and $ (\{y, z\}, [2, 3)) $. Finally, note that: the facegram (c) is a dendrogram and in particular a treegram. However, for the facegram (a) its associated face-Reeb graph is a merge tree and yet that facegram is neither a dendrogram nor a treegram. This implies in particular that the facegram (a) is the join span of at least two different treegrams (viewed as facegrams). Moreover, by definition, the face-Reeb graph of a facegram would not be a merge tree if and only if there exists a taxon that can be joined with the root by at least two different consecutive paths of maximal faces through time, and this is clearly not the case for the facegram (a) since $ \{x\} $ cannot be joined by a consecutive path of inclusions of maximal faces with $ \{x, y, z\} $ through time

Figure 13.  Perturbed facegrams and their mergegrams. Facegrams and their respective mergegrams. Points with multiplicity $ 2 $ and $ 3 $ are shown by drawing multiple rings around a point

Figure 14.  Overview over the algorithmic structures. To compute the join of treegrams we can use the join operation of the lattice of cliquegrams or of facegrams and then calculate the respective mergegram invariants. Similarly, we can compute the mergegram for metric spaces either using cliquegrams or facegrams. The arrows represent the different paths to be taken and represent different algorithms to be used

Figure 15.  Worst case scenario for a tree in terms of run-time in the algorithm. Example of a tree with the maximal number of different height values which are $ 2n-1 $ for $ n $ taxa/leaves

Figure 16.  Dendrograms of random trees. The dendrograms of two random trees. The coloring is corresponding to certain clusters by scipy

Figure 17.  Mergegrams of random trees. The mergegrams of the two random trees (left and middle). Treegrams viewed as either cliquegrams or facegrams always give the same mergegram. Coloring as well as the size of the points show the multiplicity of each point. Mergegram of the join-cliquegram and of the join-facegram (right) of the two treegrams are the same in this case. Coloring is done by the multiplicity of each point

Figure 18.  Three different dendrograms for a specific dataset. Three different dendrograms on the same taxa set

Figure 19.  Mergegrams for three treegrams. The mergegrams of the treegrams shown in Fig. 18

Figure 20.  The Mergegram of the join in the cliquegram and facegram setting. The mergegrams of the joins of the treegrams in Fig. 18. We can see that the mergegrams are different for the cliquegram and facegram setting

Figure 21.  Example dendrogram for phylogentic tree dataset. The dendrograms of one trees from the 161 different trees available for this dataset. The two outlier taxa with numbers 66 and 67 are marked in red

Figure 22.  Mergegram of the join-facegram for phylogenetic tree dataset. Heatmap of the 2d-Histogram plot taken for tuples $ (b, d-b) $ for $ b $ birth and $ d $ death pairs of the original persistence diagram of the mergegrams of the join-facegram. We excluded three points in the diagram which correspond to the singletons 66, 67 as well as the cluster formed by all taxa not being 66, 67 in this plot

Figure 23.  Comparison between the joins of a subset and the all trees with bottleneck distance for the cliquegram and facegram setting. Progression of bottleneck distances between the mergegram of the join of the first $ n $ treegrams and the mergegram of the join of all 21 treegrams for different number of taxa for the case of cliquegrams and facegrams