Page 39 - Tequio 11

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

The tree with minimal tree length can be found by computing the tree lengths over all possible phylogenetic
trees, or equivalently by minimizing over the BME polytope, which allows to reformulate the BME problem as a
12
linear programming problem (Haws, Hodge, & Yoshida, 2011).
13
While the BME method is just a heuristic, the Neighbor joining method was shown to be a greedy version
for the BME method (Gascuel & Steel, 2006).
The combinatorial structure of the BME polytope is of interest for the application in algorithms and as a basic
mathematical object in phylogenetics. Some properties of the structure of the BME polytope are in (Eickmeyer,
Huggins, Pachter, & Yoshida, 2008; Haws et al., 2011), which were extended to the study of facets in (Forcey,
Keefe, & Sands, 2016), whereas a direct algorithmic application is, e.g., in (Lefort, Desper, & Gascuel, 2015).
We represent distance functions : × → ℝ by a vector ∈ ℝ / , where we index entries of any ∈ ℝ /
5
5
® ©
® ©
by {, } ⊂ via lexicographic order, so we write as = ( -,* , -,A , ⋯ , /g-,/ ). For every labelled binary tree
5
™
® ©
™
on vertices we consider the associated vector ∈ ℝ / defined by the entries : = 2 /g´g* where is the
P,Ä
number of interior nodes of the shortest path between , in . Note that these vectors depend only on the
™
tree topology.
The balanced tree length estimation () of Pauplin is given by

(): = N (, ).
™
P,Ä
P,Ä;PÆÄ

Note that this is just the dot-product of the vector and and the pairwise distances , i.e. () = ⋅ . The
™
™
BME principle aims at finding the tree that minimises the above balanced tree length estimation. In (Haws et
al., 2011) they showed that minimising over all trees in / is equivalent to minimising over the convex hull of
all the vectors , where ∈ / .
™
BME polytopes are associated to natural numbers ∈ ℕ nA , and not to distances (i.e. metric spaces) as in the
case of the polytopes of x 3.1 and x 3.2. We define the BME(n) polytope as follows.
Definition 3.8 The BME(n) polytope / for ≥ 3 is defined as

/ : = conv{ ∣ ∈ / }.
™

As an example consider

Example 3.9 (Eickmeyer et al., 2008) Consider the case = 4. Then first we look at ë , which consists of the
following binary trees:

12 Linear programming or LP is a method to find a maximum (or a minimum) of a linear objective function over a feasible region
Linear programming or LP is a method to find a maximum (or a minimum) of a linear objective function over a feasible region given by a convex polytope.
12
given by a convex polytope.
13
13 A popular distance-based reconstruction method.
A popular distance-based reconstruction method.
Tequio, enero-abril 2021, vol. 4, no. 11