Page 36 - Tequio 11

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
34 On some polytopes in phylogenetics/Hoessly/27-40
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
decompositions that are of interest in phylogenetics. Furthermore, the 1-skeleton of the Tight span is a graph
9
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
application to, e.g., First we consider an unbounded polytope
(ô,j) : = ö ∈ ℝ ∣ P + Ä ≥ (, ) ∀, ∈ ú.
ô

Definition 3.1 The Tight span of (, ) is given by the minimal points of (ô,j) , which are defined as (ô,j) : =
ö ∈ (ô,j) ∣ ∈ (ô,j) and ≤ implies = ú.

Note that the Tight span (ô,j) corresponds to the bounded faces of the polyhedron (ô,j) . The Tight span is a
polytopal complex that is associated to any finite metric space (, ), whose structure often catches features
of (, ). The Kuratowski embedding is a map (ô,j) : → ℝ that sends elements of = { - , ⋯ , / } to its Tight
ô
span, while preserving their pairwise distance. It is defined as

(ô,j) : → ℝ ô

P ↦ (ô,j) ( P ): = (( P , Ä )) Ä∈ô
We have the following.

Lemma 3.2 The function (ô,j) : (, ) → ( (ô,j) , || ⋅ || û ) (where (ô,j) ⊆ ℝ ) is an isometric map into the tight
ô
span (ô,j) , where for ∈ ℝ , |||| û : = max î 2 ∈ô {| P |}.
ô

Example 3.3 Consider the metric on = { - , * } with ( - , * ) = 1. As a tree-like metric, it can be illustrated
as

1
0
The upper map sends - to † ( - , - ) ° = ¢ £, * to ¢ £, hence
( - , * ) 1 0

0
1
|| (ô,j) ( - ) − (ô,j) ( * )|| û = || ¢ £ − ¢ £ || û = 1 = ( - , * ),
0 1

and the Tight span looks as follows.

Figure 7.
The Tight-span as the blue line.

Example 3.3 generalises as follows to tree-like metric spaces, which can be classified via their Tight span

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