On the Balanced Minimum Evolution polytope

Abstract

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the characterization of a number of facets of its convex hull (also referred to as the BMEP polytope) as well as the discovery of connections between this polytope and the permutoassociahedron. In this article, we extend these studies, by presenting new results concerning some fundamental characteristics of the BMEP polytope, new facet-defining inequalities in the case of six or more taxa, a number of valid inequalities, and a polynomial time oracle to recognize its vertices. Our aim is to broaden understanding of the polyhedral combinatorics of the BMEP with a view to developing new and more effective exact solution algorithms.

Introduction

Consider a set $\Gamma =\{1,2,\dots ,n\}$ of $n\ge 4$ vertices, hereafter referred to as taxa. A phylogeny $T$ of $\Gamma$ is an Unrooted Binary Tree (UBT) having $\Gamma$ as leaf-set. By definition, a phylogeny of $\Gamma$ has $(n-2)$ internal vertices having degree 3 and an overall number of $(2n-3)$ edges, $n$ of which are external, i.e., incident to a taxon, and $(n-3)$ are internal, i.e., incident to two internal vertices. The labeling of the internal vertices of a phylogeny is usually less important than the labeling of the leaves, hence it is generally omitted. However, whenever the context requires us to specify a particular vertex under study, we will use the convention to label it as an integer in $\{n+1,n+2,\dots ,2n-2\}$. Fig. 1(a) shows a possible phylogeny of a set $\Gamma$ of seven taxa, shaped as a caterpillar. Fig. 1(b) shows a phylogeny with a more complex topology together with a terminology of its components that we will formally define in the next section. In Fig. 1(a) the internal vertices are labeled as indicated above. On the other hand, in Fig. 1(b), the labeling of the vertices of this phylogeny is omitted to better highlight the terminology.

Let $\mathcal{T}$ be the set of the possible distinct phylogenies of $\Gamma$. The cardinality of $\mathcal{T}$ is known to be a function of the cardinality of $\Gamma$ and can be easily shown to be equal to $(2n-5)!!=1\times 3\times 5\cdots \times (2n-5)$ [1]. Given a phylogeny $T$ of $\Gamma$ and a taxon $i\in \Gamma$, let ${\Gamma }_i$ be the set $\Gamma \setminus \left\{i\right\}$ and let ${\tau }_{ij}$ be the topological distance between taxa $i,j\in \Gamma$, $i\ne j$, i.e., the number of edges belonging to the (unique) path from taxon $i$ to taxon $j$ in $T$. For example, by referring to the phylogeny shown in Fig. 1(a), ${\tau }_{13}=3$, ${\tau }_{15}=5$, and ${\tau }_{35}=4$.

Let $\mathbf{D}$ be a given $n\times n$ symmetric distance matrix, whose generic entry $d_{ij}\in {\mathbb{R}}_{0^{+}}$ represents a measure of dissimilarity between the corresponding pair of taxa $i,j\in \Gamma$. Then, the Balanced Minimum Evolution Problem (BMEP) is to find a phylogeny $T$ of $\Gamma$ that minimizes the following length function [2], [3]:

$$L\left(T\right)=\sum _{i\in \Gamma }\sum _{j\in {\Gamma }_i}\frac{d_{ij}}{2^{{\tau }_{ij}}}.$$

The BMEP is a version of the network design problem [4] defined over UBTs. It was introduced in the literature on phylogenetics in 2000 by Pauplin [5] and systematically investigated from a biological perspective in Desper and Gascuel [6] and Gascuel and Steel [7]. The problem is $\mathcal{NP}$-hard and inapproximable within $c^n$, for some constant $c>1$, unless $\mathcal{P}=\mathcal{NP}$ [8]. This fact has justified the development of a number of implicit enumeration algorithms to exactly solve the problem [3], [9], [10] as well as a number of heuristics to approximate its optimal solution [10], [11], [12].

The current state-of-the-art exact solution algorithm for the BMEP, described in Catanzaro et al. [3], is based on an Integer Linear Programming (ILP) model that exploits some combinatorial connections between the BMEP and the Huffman Coding Problem [13], [14], [15]. Such connections proved fundamental to identify a number of properties that characterize phylogenies, such as the Kraft equalities or the Third Equality (see Section 2 and [3]), and had a central role in the study of tight lower bounds on the optimal solution to the problem. The algorithm is however unable to solve instances of the BMEP containing more than two dozen taxa within one hour computing time. Thus, in the attempt to develop algorithms able to exactly solve increasingly large instances of the problem, particular attention has been recently devoted to the study of its polyhedral combinatorics. The earliest attempts were the works Eickmeyer et al. [16] and Haws et al. [17]. Eickmeyer et al. [16] introduced the convex hull of the BMEP (hereafter also referred to as the BMEP polytope) and characterized its vertices. Haws et al. [17] characterized instead some faces of the polytope in the space of the topological distances. Neither studies led to results directly applicable in implicit enumeration approaches. Moreover, due to the nonlinearity of some specific equations that characterize phylogenies (see Section 2), it is difficult to carry out the analysis of the polytope in the chosen space. Hence, Forcey et al. [18] investigated alternative spaces to perform such analysis and proposed the use of Polymake [19] to assist in this task. Their empirical approach proved successful in unveiling connections between the BMEP polytope and the permutoassociahedron [20], [21], [22], [23] as well as in characterizing the BMEP polytope in low and fixed dimensions. In particular, they succeeded in characterizing all of its facets for five taxa and some of the facets for six taxa. Unfortunately, the very large number of facets to analyze in the latter case (over 90 000, see Section 6.2) prevented the complete description of the polytope.

In this article, we extend the results of Eickmeyer et al. [16] and Forcey et al. [21], [18], by presenting both alternative and novel proofs concerning the polyhedral combinatorics of the BMEP as well as algorithms that may inspire the development of new exact solution approaches to the problem based on implicit enumeration. Some alternative proofs (e.g., the characterization of the dimension of the BMEP polytope) are interesting per se because they enable the analysis of aspects not trivially deducible from previous studies [16], [18], [21]. We also characterize new facets of the BMEP polytope for six or more taxa as well as valid inequalities. We address the problem of consistently generating the vertices of the BMEP polytope as well as the problem of recognizing its vertices. We present a set of necessary and sufficient conditions to address the vertex generation problem and we show how to translate such conditions into a set of nonlinear constraints in order to develop new exact solution approaches to the problem similar to those already proposed in [3] and [10]. We will show that these conditions also suggest a possible polynomial-time oracle to solve the recognition problem as well. The article is organized as follows. In Section 2 we introduce some notation, definitions, and fundamental properties of the topological distances that will prove useful throughout the article. In Section 3, we review Forcey et al. [18] space. In Section 4, we show a possible basis for the space of Forcey et al. [18]. In Sections 5 On the convex hull of the set, 6 Valid inequalities and facets of we discuss some fundamental characteristics of the BMEP polytope and we extend the analysis of Eickmeyer et al. [16] and Forcey et al. [18]. Finally, in Section 7, we address the problem of recognizing and consistently generating the vertices of the BMEP polytope.