10.3.1 Trees as Points

In the last section, we discussed trees, phylogenetic X-trees (and more so, binary ones) in particular, as graphs, and developed a bit of intuition supporting their interpretation in some biological situations. In this section, we move beyond the visual appeal of trees, as graphical models, in order to interpret them in a geometric framework that better sets the stage for implementing algorithmic and computational methods to reconstruct the phylogeny of a set of species (or genes, or other organisms) and for describing geometrically the advantages and pitfalls of those methods.

By definition, phylogenetic X-trees have leaves that are labeled, but for phylogenetic tree reconstruction, one may also want to label the edges. Thinking of the vertices V, of a phylogenetic X-tree , as species for the moment, then labels on the edges can, depending on the biological context, be regarded as providing some attribute of the sequences, often a measure of evolutionary change from one species to the next. In graph-theoretic terms, a labeling of the edges E of T is an edge-weighting, a function that assigns a real number , say, to every edge . In many cases, such edge-weightings are assumed to take nonnegative values, but for phylogenetic tree reconstruction algorithms, it is useful to allow for more general edge-weightings. In phylogenetics, the graphical notion of an edge-weighting corresponds to an evolutionary distance map. Determination of evolutionary distances is a process anchored in the choice of a so-called model of evolution, which describes how (and how frequently or with what probabilities) sequences change, e.g., via substitutions, insertions, or deletions in their character strings. This is a very large and significant area of research for which there are a number of nice treatments in both biology and biomathematics texts; see the references in the Introduction.

We also do not discuss in any detail here the many ways by which evolutionary distances are defined and determined, we do give two examples in Exercise 10.8 below.

Trees , together with weightings , will be the outcomes of the distance-based reconstruction methods we examine. We let denote the set of all ordered pairs of unrooted binary phylogenetic X-trees T together with positive edge weightings on T. Some distance-based reconstruction methods may produce edge weightings with negative values or zero, so it may be useful to extend to include these weightings.

The Hamming distance represents an easy, but rather crude measure of difference between sequences. For example, it fails to take into account the possibility that sequences could have characters change over time, and then change back. Also, there is no accounting for well-known biochemical phenomenon such as the fact that the probability that one DNA character might change to another is not generally uniform, but likely differs on the particular DNA bases themselves, or how they are arranged or grouped along the sequence. So-called “evolutionary models” describe special sets of additional assumptions that are made to account for these kinds of issues, and methods for determining the related evolutionary distances between any two given leaves , that are represented by two aligned sequences (of DNA, RNA, proteins, etc.) , generally depend on the choice of particular models of evolution. For example, the model of evolution that eventually gives rise to the Jukes-Cantor correction in Exercise 10.8 above is obtained from the Jukes-Cantor model of evolution; see e.g., [4] or [1], for more details on this model and [3] a derivation of this distance from the model by an algebraic geometry approach.

The evolutionary model for Hamming distance is very simple; it assumes all bases have equal probability of changing into one another, all sites in the string of DNA are independent, and that the only change that has occurred over time is that which is observed. As with the Hamming distance or the Jukes-Cantor model and Jukes-Cantor correction, in general, evolutionary distances incorporate information differences or distinctions between sequences and , and hence give rise to a so-called dissimilarity map, to be defined precisely further below. Sequences which are the same provide no new information; it’s the sense in which they are dissimilar that shows change and hence evolution.

10.3.2 Fitting Trees: A Distance-Based Approach

With the previous comments in mind, one approach (a “distance-based approach”) to solving the central problem of phylogenetic tree reconstruction is to

Each of the three steps above is highly significant; for this chapter, we will be focusing on the last step. In particular, since real sequence data contains “noise,” it is not usually possible to find a tree which “fits” the data exactly, so in the last step above it becomes necessary to look for a tree T on X which “best fits” the data , and we will be exploring some ways to do this in much greater detail. As preparation, we want first to return to some mathematical formulations that will be instrumental in what follows. We start with the definition of a dissimilarity measure (also called a dissimilarity map).

Mathematically, for any finite set X, a dissimilarity map on X is simply a real-valued ( for all ) symmetric ( for all ) square matrix with diagonal entries zero ( for all ).

As matrices, dissimilarity maps show up frequently in mathematics. For example, by the polar decomposition theorem, every real-valued square matrix M can be expressed as a sum of a symmetric and a skew-symmetric matrix via , so if M begins as a zero-diagonal matrix, then the symmetric component, , will be a dissimilarity map. As another example, a map is called a metric if , and for all . The last inequality is the well-known triangle inequality, familiar from Euclidean geometry; think of points , and z as lying on the vertices of a triangle. Recall that, for is the distance from x to 0 on the real line, and is the distance between any two real numbers on the number line. Likewise, for two points in the plane , setting gives the usual distance between the two points (length of line segment joining x and y). For two points and in three-space , by reducing to a picture with two triangles, each in their own plane, it is not hard to generalize the Pythagorean theorem and show that setting gives the standard distance between the two points (length of line segment joining x and y) in . Distances can take on other forms, but going back to general metrics, we have, by definition, that they are dissimilarity maps with the triangle inequality as an additional property. Metrics are prominent in the study of mathematical real analysis, as they generalize distance measures like the absolute value, as we have just seen.

Turning back to biology, starting with a labeled X-tree (T rooted or unrooted) with edge-weighting , a dissimilarity map arises naturally. As demonstrated in the example below, simply sum up the edge-weightings , over all distinct edges e on the path in T joining any two leaves in X, to get each value .

The four-point condition for a dissimilarity map D on a set X is satisfied if

for any , where by definition the right-hand side of the inequality is the largest (“max”) of the two sums indicated.

Returning to an arbitrary labeled X-tree with edge-weighting , we have, by assumption, that there’s no edge between a leaf and itself, so for any . This is consistent with notions of evolutionary distance: there’s zero dissimilarity between any sequence and itself. It is also presumed that the information encoded by evolutionary distance measures on pairs of sequences is independent of the ordering of the two (i.e., it does not matter which is “first” or “second”). From Exercise 10.8, one can see explicitly that the evolutionary distances dJ and dH are dissimilarity maps.

We have seen that if one begins with an edge-weighted X-tree T, using the tree and the weighting, one can use the edge labels to find a value for each pair of leaves , that has an interpretation as a “distance,” namely, the path length between x and y along the tree T, if the “length” of an edge e is taken to be its edge weight . The resulting matrix of all values is a dissimilarity map. Again, the fundamental biological problem of phylogenetics is to start the other way around—from a relevant set X (species, genes, etc. or sequences standing in for the species, genes, and so on) and a collection of relevant “distances,” find a tree T and an edge-weighting for which the natural dissimilarity map fits the data “well.” This is what is meant by “reconstructing a phylogenetic tree” from the given data, using a distance-based approach. In the most ideal case of “fitting well,” fits D exactly, that is, they agree as functions: for all . If one begins with a phylogenetic X-tree T, and a nonnegative edge-weighting for T, and takes as data D by setting , then trivially fits D exactly. This raises the issue of consistency in tree reconstruction methods, that is, whether a tree reconstruction method applied to data D that is derived from a tree T (perhaps weighted, with weight ) actually outputs this tree T (and the corresponding weights ). One can also speak more generally of statistical consistency of a tree reconstruction method, namely, the probability that the method outputs the correct tree given sufficient data about the input.

10.3.3 Tree Metrics and Tree Space

Dissimilarity maps D for which there is some labeled tree T and some nonnegative edge-weighting for T such that are called tree metrics.

These results lead, in part, to a fundamental characterization theorem of tree metrics:

Part (2) of Exercise 10.15 gives one half of part (1) of Theorem 10.1, showing how to recognize tree metrics out of all possible dissimilarity maps; for a proof, see, e.g., [2, Theorem 7.2.6]. Part (2) of Theorem 10.1 shows that any dissimilarity map which is a tree metric for a phylogenetic X-tree not only comes from such a tree, but corresponds to essentially one and only one pair of a phylogenetic X-tree and edge-weighting on T; see [2, Theorem 7.1.8] and its proof. Part (2) of Theorem 10.1 implies that tree metrics on X correspond exactly to edge-weighted phylogenetic trees on X.

If a given dissimilarity map D on a set X is in fact a tree metric, then by definition, there is a tree and an edge weighting that fits D exactly. As previously noted, in general, evolutionary distance data D from real sequence data for species, genes, etc., is noisy, and in our new language, although D will be a dissimilarity map, D will usually not already be a tree metric. Consequently, one looks for ways to find a phylogenetic X-tree T with edge-weighting for which and D will be “close” in some specified way, and in this sense, say a tree with a “best fit” has been found. To discuss “closeness,” it would be helpful to have a notion of distance that could be used to compare dissimilarity maps D coming from sequence data with induced tree metrics . Having discussed previously how to find distances between two points on a line , in the plane , or in three space , and more generally in for by means of a standard distance (via Pythagorean theorem analog), we might be motivated to seek a way to regard both D and as points, and then seek a distance between those points that we would then try to minimize in order to find an edge-weighted tree T that “best fits” the original data. Taking that step is our next focal point.

Since any matrix is really just a nicely ordered list of elements (i.e., listed by row and cross-listed by column), there is already an immediate way to regard matrices as points (vectors): just start writing out the entries of the matrix across row 1; when you get to the end, start adding the elements of row 2, and so on, until all elements are listed. For example, if M is a matrix, then there is a correspondence of M and a vector with entries:

(10.2)

Other orderings of the elements of M to create a 16-tuple could be taken, of course, but as long as we are consistent this has no effect on our definition of distance.

Given the symmetry and existence of all zero-diagonal elements of any dissimilarity map , there is a lot of redundancy in the entries; in fact, if , then for the non-zero entries of D, there are at most distinct entries in the n by n matrix D. Starting with D, it is straightforward to create a streamlined vector in carrying the same information as D, by choosing an ordering for reading off, and then listing in that order, the elements of D above the diagonal. This is illustrated for one choice of such an ordering below, for D as in Eq. (10.1):

With this adjustment, it is now possible to represent any two n by n dissimilarity maps by vectors , where . One can use the standard Euclidean distance measure to measure a distance between D and in . In particular, suppose D is a dissimilarity map coming from evolutionary distances between elements in a set X (or their representative sequences). Suppose for an edge-weighted phylogenetic X-tree T (with ). Then one can phrase the problem of finding a ( edge-weighted) phylogenetic tree T that “best fits” the observed data D on X as one of finding a pair so that is as small as possible. Equivalently, one may take a least-squares approach, since minimizing is the same as minimizing . When there is an exact fit, .

To summarize:

In this way, a fundamental problem of biology is turned into a geometric problem. In particular, one wants to understand better the set regarded as a set of points . The set is often called “tree space,” though there is one for each n.

The treatment of the tree space is handled somewhat differently by different authors, to take advantage of simplifications in representing trees (and to use rooted trees in some cases, unrooted in others). For instance, if one extends to include nonnegative edge-weightings (that is, some values can be zero), then one may include positively weighted, (unrooted) nonbinary trees on n leaves as part of tree space, and then compare how edge-weighted binary n-trees are related to one another through the collapsing of one or more edges. For an original definition of tree space and helpful pictures of this sort in the rooted tree case, as well as a discussion of how the positive orthants are “glued” together along spaces corresponding to (nonbinary) trees with collapsed edges, see [18]; for another analogous but different perspective on the unrooted case, also with nice pictures, see [19]. Using another variation on tree space, there has been a lot of work done to examine distances, particularly geodesics, in tree space; see [18,20,21]. Regardless of the precise formulation of tree space, as the example and brief treatment above may geometrically suggest, it can be useful to group points by their phylogenetic trees T or even by their underlying topologies. This is, again, the perspective that for each there is the “same” copy of attached to it, so to determine a point in , it is often useful to focus on determining just the tree alone, and then think of the associated weighting , even though the two are linked. (Again, this is analogous to thinking of a point in our everyday four-dimensional space-time lives first by its time coordinate, then as a point in space at that time.)

In any case, for practical purposes, however, the notion of standard distance in may not be the best distance measure for comparing trees and fitting trees to dissimilarity maps. In fact, it is shown in [22] that taking a least-squares approach to picking an edge-weighted tree T with weighting and induced metric to best fit a given dissimilarity map is an NP-complete problem. The same holds true for minimizing (the f-statistic) rather than the corresponding sum of squares.

In the search for heuristics to carry out tree reconstruction, many fitting algorithms proceed instead by wandering among the trees (points) in tree space, and rather than use a least-squares or f-statistic approach, use metrics that record points as being “close” when their trees (edge-weighted by , resp., ) can be transformed into one another explicitly by means of a small number of iterations of a few well-known operations on trees as graphs. In the case of Robinson-Foulds (RF) topological distance, the two relevant operations are a form of merging nodes and then splitting nodes on the underlying tree topologies (ignoring weightings), as illustrated in the picture below for two trees of RF-distance apart (see Figure 10.5).

Other well-known operations in tree space include the nearest-neighbor interchange (NNI move) the subtree-pruning-and-regrafting move (SPR move), and the tree bisection and reconnection move (TBR move). A generic NNI move is illustrated in Figure 10.6 above, where each triangle represents a clade, that is, a subtree arising from a node and all its descendants and edges connecting them; here it could be a single leaf. For clades , an NNI move is essentially a move on a quartet, exchanging the neighbor of one cherry for a neighbor of the other cherry (see Figure 10.6). The SPR moves and TBR moves are more general but can be similarly pictured; see, e.g., [2, Section 2.6] for definitions and representative pictures, or [23, Section 3] for a definition and picture of an SPR move relevant to our later discussion.

10.4.1 Neighbor-Joining

The Neighbor-Joining (NJ) Algorithm [16] takes as input a dissimilarity map and builds an edge-weighted unrooted binary phylogenetic X-tree , by iteratively picking cherries out of X. There are three essential steps in the NJ Algorithm:

If , one then continues the procedure by eliminating from the set of leaves X (i.e., replace by in the set X) and seeking the next cherry in the remaining set of leaves to join, until the total number of remaining leaves n is 3. The result is an edge-weighted unrooted binary phylogenetic X-tree. Visually, one can proceed by picturing a star tree on -leaves and seeing the NJ Algorithm as a set of instructions for successively splitting off leaves onto their own branches (see Figure 10.7).

The key component of the NJ Algorithm is the method for picking cherries, accomplished by the Q-criterion, described in Theorem 10.2 below. The formulation of the cherry-picking step of the NJ Algorithm, as a problem of minimizing the Q-values, comes from a reworking of [16] by [24].

The NJ Algorithm is predicated upon the Q-criterion in the sense that if one starts with a tree metric, then the minimum value of Q gives a cherry, so if one is looking to build a tree from an arbitrary dissimilarity map, one might likewise try calculating the Q-values, and hope it works. As it turns out, this is practically and mathematically effective, yielding an algorithm with running time [24], but in its current formulation, the rationale for the Q-criterion is nonobvious. The next exercise helps shed some light on the cherry-picking criterion, when .

Exercise 10.17 shows that the cherry-picking criteria at least makes sense for unrooted binary quartet trees, since there is only one topology to consider. There is a much stronger connection between quartets and the NJ Algorithm, as is given by the next theorem, shown, e.g., in [25].

As suggested by the last part of Exercise 10.17, in general, while the NJ Algorithm will pick out the pair of cherries with minimal distance between them first, if there are two or more pairs of cherries with the same distance between them, any of these may be chosen first. Thus, more generally, the order of choosing cherries in the NJ Algorithm may not be unique (i.e., when multiple pairs of leaves have the same Q-values). If the NJ Algorithm selects taxa as a cherry, and is the new node joining , then the new dissimilarity map is defined to be

Recall our geometric perspective that, for a given a fixed , and a dissimilarity map (distance matrix) D, to “fit” a tree to D is to find a pair so that and D are “close.” The NJ method is at least consistent: If a tree metric is given as the input D, then will be returned as the output.

The NJ Algorithm constructs a weighted (binary) phylogenetic X-tree from a dissimilarity map D on X. As a tree, T has vertices V, with , and the NJ Algorithm proceeds by constructing the set V, edges E, and edge-weights from the data D on X. An order of picking cherries in the NJ Algorithm when outputting the pair from D could be defined as a sequence of pairs of elements , for which is the kth cherry to be picked. The first cherry is a subset of X, but the remaining pairs may involve interior vertices. For fixed, no matter what phylogenetic X-tree T is constructed, by Exercise 10.4, the number of vertices is always the same. Without loss of generality (that is, by relabeling the elements of V), it makes sense to speak of an ordering of cherries or cherry-picking order as a sequence of pairs of elements of (with, say, the elements of corresponding to ), for which the NJ Algorithm produces some binary phylogenetic X-tree T from some input dissimilarity map , by picking cherries according to .

For a cherry-picking order on V, with , and , for , take to be the set of all dissimilarity maps D in for which the NJ Algorithm applied to D proceeds using . (The NJ Algorithm also outputs a weighting on T, but that’s not important for the definition of .) Applying Exercise 10.19, if then for any positive multiple . Thus, is a cone in . This cone is called a neighbor-joining (NJ) cone. The entire space is the union of NJ cones, running over all cherry-picking orderings . Take to be the set of all dissimilarity maps D in for which the NJ Algorithm outputs the unrooted binary phylogenetic X-tree with some weighting . For each (binary) phylogenetic X-tree , one has for cherry-picking orders that are compatible with T. In some cases, a tree can arise from more than one ordering, and in that case, the boundaries of the corresponding NJ cones intersect. Neighbor-joining cones describe the NJ Algorithm geometrically—the output of the NJ on a point is a weighted tree with underlying topology T if and only if D is in the union of NJ cones .

Neighbor-joining cones are defined and studied in detail for small trees () in [26]. By studying and comparing the volumes of the NJ cones, [26] can geometrically formulate results about the behavior of the NJ Algorithm. These include how likely the NJ Algorithm is to return a particular tree topology given a random input vector (dissimilarity map), and the robustness of the NJ Algorithm. More complete information about these NJ cones, including information about “dimensions” of the cones, rays of the cones, faces, and other results, also appears in [27]. In both [27,23], geometric information is used to gain further insight into a comparison between the NJ Algorithm as a phylogenetic tree reconstruction method and another distance-based method, the balanced minimum evolution (BME) method, a topic we now explore.

10.4.2 Balanced Minimum Evolution

Recall that for any set with , and any edge-weighted phylogenetic X-tree , with , there is a naturally associated tree metric . One can set the total length of the tree to be the total sum of all the edge weights: . The minimum evolution principle for tree reconstruction uses the idea of minimizing tree length in order to find the best-fitting tree to a given dissimilarity map . Specifically, given a dissimilarity map as input, a minimum evolution method seeks to locate as output an edge-weighted tree so that for all , and is as small as possible. Biologically, the minimum evolution principle is driven by the idea that evolution is efficient. Since branch lengths represent amount of evolutionary change leading from one, say, species to the next, the total tree length is a measure of that efficiency across the whole tree, and hence should be minimal under a minimum evolution perspective.

There are many different minimum evolution methods; for all, it is necessary to start from D and come up with not only with the phylogenetic tree T, but also the edge weighting (branch lengths) . Since there are finitely many possible phylogenetic X-trees, one approach is, starting with any dissimilarity map and starting with any tree , to come up with a branch length estimation scheme for T based on the data D. One then computes the resulting tree length and, looking over all possible T, seeks T so that in minimized.

One approach for producing from D, the Balanced Minimum Evolution (BME) method, uses an approach of Pauplin’s [14]. Pauplin’s scheme for branch length estimation from D, applied to the case of just a quartet, should now be very familiar to us from our previous exercises on the four-point condition and the NJ Algorithm. Specifically, if is the interior edge joining u and in the (unrooted) quartet tree ((A,B), (C,D)); as in Example 10.3, then is given by setting . This idea is extended in [14] to the case when are replaced by entire subtrees in an arbitrary tree . The result gives an iterative formula for for any interior edge in T that accounts for the relative size (say, number of leaves) in each subtree. (This is the “balance” of the BME method.) The (easier) case of edges that are external is also handled there. Rather than say more about these formulas, however, we instead make use of a very nice result by which the total tree length can be calculated more easily, without first finding all the branch lengths .

Starting from , define to be one divided by the product of for every interior node x encountered on the path in T from i to j. Equivalently, set to be the number of edges between leaves i and j on the path . In this case, we can see that . Now set

Notice that only depends on the topology of T, so we may call it the BME vector of T.

Using the BME vectors, Pauplin’s[14]formula for the balanced tree length estimation (i.e., estimated BME length) , starting with the dissimilarity map D, is given by

(10.4)

Equivalently, in the standard language of innner products of vectors, upon rewriting D as a vector d using the ordering from before, one gets . The BME method proceeds by seeking so that in Eq. 10.4 is minimal.

In [28], the authors in fact defined terms for any phylogenetic X-tree T (not necessarily binary) in terms of certain cyclic permutations of (“circular orderings”) of X that respect the structure of T. In the case of edge-weighted binary X-trees, one recovers the expression for in the BME vector and Pauplin’s formula. In [28] this perspective was used to establish the consistency of the balanced tree length estimation. The consistency (and statistical consistency) of the BME method as a whole was established in [29].

Like all methods that would require a complete search over all trees , combinatorial explosion is a problem. The large number of trees to consider quickly overwhelms computer capacity, so that in practice, one must come up with a heuristic. In [29,15], the theoretical underpinnings for the BME method were further examined, and a heuristic proposed and implemented for the BME method via the program FastME. This program essentially uses only nearest-neighbor interchange (NNI) moves among trees to seek out a tree T/BME vector that is a good candidate for having minimal . For more details, see [29,15].

Options in FastME also include implementations of the NJ Algorithm and its improved version, the BioNJ Algorithm. There is a special reason why. Although the NJ Algorithm was long a favorite among molecular and other biologists for its effectiveness in practice, after many years of investigation, reservations about the NJ Algorithm remained, due in part to an ongoing sense of uncertainty about just what the algorithm was doing (and hence why it could be successful), from a more theoretical perspective. Illumination came in the form of a result by [29] linking the BME method and NJ Algorithm by showing that the NJ Algorithm is a so-called greedy algorithm for implementing the BME principle. Since the BME method is well grounded in standard mathematical approaches (minimization problems), this link shed light on the “true” nature of the NJ Algorithm. As a greedy algorithm, the NJ Algorithm acts locally, however, and like any greedy algorithm, does not necessarily actually produce a tree T which is optimal for the BME principle (i.e., has total length minimal). The BME method for phylogenetic tree reconstruction can be reformulated still further in a neat geometric way. By definition, a convex set B (say ) is one for which any point that is on any line joining any two points is also in B, i.e., z on implies . It is an easy exercise to see that the intersection of any set of convex sets is also convex. Let be the convex hull in of all the BME vectors for ; by definition, the convex hull of a set of points is the intersection of all convex sets containing these points. This produces a polytope (analog of a polygon in higher dimensional space), which we call the nth BME polytope , inside . As a consequence of the definition of the BME vectors and the BME method, the vertices of the BME polytope are actually the BME vectors . Using the generalized notion of BME vectors as in [2], the BME vector of the star phylogeny lies in the interior of the BME polytope , and all other BME vectors lie on the boundary of the BME polytope.

By Exercise 10.23, the BME polytope for is a familiar two-dimensional object. More generally, the dimension of . If , then thinking not of the full polytope in , but considering only vertices and edges of alone, there is a graph isomorphism between and the complete graph on n vertices.

These and many other facts about BME polytopes appear in [27,23]. For , [27] observed that in the actual polytope , the graph isomorphism with the complete graph on vertices no longer holds: there are pairs of trees for which the BME vectors are not connected by an edge of the polytope. That is, the line joining and is not itself an edge of the polytope, but must sit somewhere inside , since 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 , 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 and , carrying out the BME method for D is the same as minimizing the linear objective d over the (convex) BME polytope . This framing of the problem 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 and used to show that both NNI moves and SPR (subtree-pruning-and-regrafting) moves between trees give rise to edges in the BME polytope. Since FastME uses NNI moves to heuristically implement the BME method, Haws et al. [23] implies that FastME is an edge-walk along the BME polytope. With better knowledge of the BME polytope, it might be possible to find an even faster heuristic. Results in [23] show that clades (subtrees obtained by taking all children of a parent node and the edges that join them) correspond to “faces” in the BME polytope and identify themselves with BME polytopes values inside .

Finally, as it was for NJ cones, it is possible to define BME cones. For any , a BME cone is simply the set of all for which as in Eq. 10.4 is minimal. Again, geometrically, the BME cone describes the BME method, for the cone for T consists of all D for which the BME method applied to D produces T (with weighting ). As before, is partitioned into the BME cones, running over all , although a given D may lie in more than one BME cone. A consequence in [23] of this analysis, in combination with previous work on the NJ cones, is a further refinement of the relationship between the relationship of NJ as a greedy algorithm for the BME principle. In mathematical lingo, for any cherry-picking order , the intersection of the NJ cone and the BME cone for T has positive measure. In particular, this shows that for any order of joining nodes to form a tree, there is a dissimilarity map so that the NJ Algorithm returns the BME tree, a useful phylogenetic result. The performance of the NJ Algorithm and BME method can be further analyzed through studying these cones, and the implications of their differing geometries are explored further in [27,23]. A complete characterization of edges of the BME polytope in terms of tree operations remains an open question, however.

Also, in terms of further work, [17] studied how the BME method works when the addition of an extra taxon (e.g., species) to a data set alters the structure of the optimal phylogenetic tree. They characterized the behavior of the BME phylogenetics on such data sets, using the BME polytopes and the BME cones which are the normal cones of the BME polytope, as noted in [27]. A related study for another tree reconstruction method, UPGMA, was carried out in [30].