Page 35 - Tequio 11

On some polytopes in phylogenetics/Hoessly/27-40 33

A phylogenetic tree is an -tree where only the leaves are labelled and all internal vertices have a degree of
at least 3. As in the case of -trees, a phylogenetic tree is binary if all internal vertices have degree three. As a
more concrete example of a binary phylogenetic tree consider

Figure 6.
A binary phylogenetic tree.

For = || ≥ 3 denote by / the set of all binary -trees with leaves. If the context is clear we will also simply
say binary tree for binary phylogenetic -trees.
Given an -tree, there is an associated system of splits on obtained by considering the two connected
components obtained by the removal of in for each edge ∈ (). Denote the so-obtained set of splits by
∑(). For an example we refer to example [ex_dist]. On the other hand, by Theorem [tree], we get that for ∑ a
system of splits, there is an -tree such that ∑ = ∑() if and only if the system of splits is compatible.
More general split systems are employed for generalizations of unrooted phylogenetic trees, where graphs
in such split networks are not necessarily trees, and one or more edges in the graph are used to represent a
split (Dress et al., 2011; Huson et al., 2010).

3. Polytopes in phylogenetics
Both the Tight span and the Lipschitz polytope are associated to a (finite) metric space and relate to a distance-
preserving embedding in a bigger space. The minimum evolution polytope on the other hand is associated to
natural numbers ∈ ℕ nA . In the following, we aim to introduce and motivate the main objects. However, the
topics are mature research directions and we restrict to a non-exhaustive treatment.

3.1 Tight span
Isbell studied the tight span in his investigation of injectivity for metric spaces (Isbell, 1964). In phylogenetics,
it appeared in relation to reconstruction of phylogenetic trees from finite metric spaces (Dress, 1984).
Representations of distances of phylogenetic trees can be seen as a connected one-dimensional polytope.
Distances between vertices correspond to the sum of the edge lengths of the shortest paths. Hence it is natural
to ask whether we can embed a given finite metric space distance-preserving into a low-dimensional compact
polytope. One such possibility is the so-called Tight span.
The Tight span often helped to establish properties of classes of metrics, particularly in relation to
9
decompositions that are of interest in phylogenetics. Furthermore, the 1-skeleton of the Tight span is a graph
realisations of the metric (Dress, 1984). For more on the motivation and connection of the study of Tight span
to phylogenetics we refer to, e.g., (Dress et al., 2011) or (Huson et al., 2010), and for a concrete algorithmic
9 I.e. the one dimensional faces.

Tequio, enero-abril 2021, vol. 4, no. 11