Phylogenetic Tree Reconstruction: Geometric Approaches - Mathematical Concepts and Methods in Modern Biology - page 333

FIGURE 10.9
A representation of the BME polytope

B 5

B 5 is graph isomorphic to the complete
graph on 15 vertices, shown below (see Figure 10.9 ).
These and many other facts about BME polytopes appear in [ 27 , 23 ]. For n

= , | T 5 |=

Example 10.9. For n 5 15, so

= 7,

7
2

[ 27 ] observed that in the actual polytope B 7 ⊂ R , the graph isomorphismwith the

T ∈ T 7
for which the BME vectors are not connected by an edge of the polytope. That is, the
line joining

complete graph on n = 7 vertices no longer holds: there are pairs of trees T ,

T is not itself an edge of the polytope, but must sit somewhere

T and

w w

inside B 7 is convex. See [p. 5][ 27 ] for a picture and description of these

pairs, and other information about faces, facets, and more for small n .For n

B 7 , since

7,
computational complexity prevents the hands-on geometric methods explored in [ 27 ]
from being exploited for higher n .
Describing more fully the edges and other features of the the BME polytope could
have practical implications for phylogenetic tree reconstruction. In the language of the
well-known mathematical methods of linear optimization, the BME method becomes
a linear programming problem: using the correspondence between T

>

∈ T n and

n
2 T

w , carrying out the BME method for D is the same as minimizing the

linear objective d over the (convex) BME polytope

∈ R

B n . This framing of the prob-
lem motivated further theoretical studies of the BME polytope in [ 23 ], where a new
version of a cherry-picking algorithm, this time for the BME method, was developed