Tree Optimization Criteria and Tree Search Methods in Phylogenetics

Distance-matrix clustering methods such as UPGMA and Neighbor-Joining construct a phylogenetic tree directly through a fixed, well-defined algorithm, without explicitly comparing alternative trees against one another. In contrast, several other important phylogenetic approaches work by defining a numerical criterion of optimality and then searching among many possible tree topologies to find the one tree that best satisfies this criterion. This general strategy underlies the Fitch–Margoliash method as well as the maximum-likelihood and parsimony methods, which are among the most important approaches used in modern phylogenetics. Since the number of possible tree topologies grows extremely rapidly with the number of species, an efficient strategy for searching through this enormous “tree space” is required. This involves defining what is meant by “neighboring” trees, and using systematic search strategies to move from an initial tree towards a tree that optimizes the chosen criterion.

Criteria for Judging Trees

The Fitch–Margoliash Method

As explained in relation to the Neighbor-Joining method, NJ constructs an additive tree such that the distances measured along its branches are approximately equal to the distances specified in the original distance matrix. Building on this idea, it is possible to define a function, E, which measures the total error made when a given tree is used to represent the distances in the input matrix:

E = Σ [(d_ij − d_ij(tree))² / d_ij²] (summed over all pairs of species i, j)

where d_ij is the distance between species i and j as specified in the original distance matrix, and d_ij(tree) is the corresponding distance measured by summing branch lengths along the tree. This function E is essentially the sum of the squares of the relative errors made in reproducing each of the pairwise distances using the tree.

• Fitch and Margoliash (1967) proposed a phylogenetic method that searches for the particular tree topology and set of branch lengths that minimizes the function E.
• This can be understood as finding the additive tree that differs least from the input distance data.
• If the original distance matrix is exactly additive, it is possible, in principle, to find a tree for which every term in the sum is exactly zero.
• In practice, this exact fit is usually not possible, because the number of pairwise distances in the matrix is N(N − 1)/2, which is far greater than the number of independent branch lengths available to be optimized on an unrooted tree, namely 2N − 3. Since there are many more distance constraints than free parameters (branch lengths), the tree can only be fitted approximately, and E is minimized rather than reduced exactly to zero.

Comparison with Clustering Methods

• Clustering methods such as NJ and UPGMA operate through a well-defined step-by-step algorithm for constructing a single tree, but they do not involve any explicit criterion by which multiple candidate trees can be compared against one another.
• Such a comparative criterion is not required for these clustering methods, because the clustering algorithm itself directly produces one particular tree as its output.
• In contrast, methods such as Fitch–Margoliash, maximum likelihood, and parsimony are fundamentally different in approach: they define an explicit numerical criterion of optimality, and then require a search through many candidate tree topologies to identify the tree that best satisfies this criterion.

Maximum-Likelihood and Parsimony Criteria (Brief Overview)

• The maximum-likelihood criterion selects the tree on which the likelihood of observing the given set of sequences is the highest.
• The parsimony criterion selects the tree that requires the fewest number of substitutions to explain the observed sequences.

Both of these criteria depend on the same general principle of testing alternative tree topologies against an optimality criterion, though the detailed mathematical basis of each method differs and is treated separately elsewhere.

Practical Comparison: Fitch–Margoliash versus Neighbor-Joining

• The Fitch–Margoliash method is considerably slower than Neighbor-Joining in practice, since it must search among many candidate trees rather than constructing a single tree directly.
• If the distance matrix is approximately additive, NJ will typically produce a very similar result to Fitch–Margoliash, but in a much shorter computational time.
• If the distance matrix is far from additive, then neither method is appropriate, and both are likely to produce inaccurate tree topologies in such cases.

Moves in Tree Space

The Concept of Tree Space

Even for a fairly small number of species, the total number of possible unrooted tree topologies is extremely large. This is illustrated by the fact that the number of possible trees grows according to a double-factorial expression; for example, for nine species the number of possible trees, denoted U₉, equals 9!! (the product of successive odd numbers up to 9), which comes out to 945. Because of this explosive growth in the number of possible topologies, it is only feasible to exhaustively test every possible tree when the number of species is very small (fewer than about eight). For any larger, more realistic data set, heuristic search programs must be used instead, which explore only a subset of all possible trees in an efficient and systematic manner.

It is useful to conceptualize the complete set of all possible tree topologies as forming a “tree space”. Search strategies then work by moving through this tree space from one tree to a neighboring tree, gradually approaching an optimal tree according to the chosen criterion.

Nearest-Neighbor Interchange (NNI)

Two trees are generally considered to be neighboring points in tree space if they differ from one another by a single topology change known as a nearest-neighbor interchange (NNI).

• To perform an NNI, an internal branch of the tree is first selected.
• This internal branch connects two subtrees on either side; a subtree may consist of either a single species or a larger branching structure containing several species.
• The NNI move consists of swapping one subtree from one end of the selected internal branch with one subtree from the other end.
• For any single internal branch, there are exactly two possible NNI moves that can be made, giving rise to two alternative neighboring tree topologies in addition to the original tree.
• All trees related to one another by a single NNI about the same branch are considered neighbors of each other, and no other trees can be produced by rearrangement about that particular branch.
• A tree that requires more than one NNI to reach from a given starting tree is not considered a direct neighbor of that starting tree in tree space.
• By carrying out a sequence of multiple NNIs, one after another, it is possible to transform any given tree topology into any other possible tree topology.

Subtree Pruning and Regrafting (SPR)

Subtree pruning and regrafting (SPR) is a different, longer-range type of topology change.

• It consists of selecting any subtree within the original tree (which may be a single species or a larger branching group).
• This subtree is cut (pruned) away from its original position in the tree.
• The pruned subtree is then reconnected (regrafted) onto any other branch remaining in the rest of the original tree.
• SPR is described as a type of long-range move in tree space, since it can produce a tree that differs substantially from the starting tree in a single step, unlike the more localized NNI move.

Tree Bisection and Reconnection (TBR)

Tree bisection and reconnection (TBR), described by Swofford et al. (1996), is another type of long-range move in tree space.

• An internal branch of the tree is selected and removed, which splits the original tree into two separate subtrees.
• These two subtrees are then reconnected by randomly selecting one branch from each of the two subtrees and joining them together using a new internal branch.

Tree Search Strategies

Hill-Climbing Algorithm

Having defined a criterion of optimality (such as likelihood, parsimony, or the least-squares error E) and a notion of neighboring trees, the next step is to search tree space for the tree that best satisfies this criterion. This is generally done using the following strategy:

1. Begin with an initial guess at an optimal tree. This starting tree could, for example, be the tree produced by a distance-matrix method such as NJ, which would be expected to already be a reasonably good tree according to the optimization criterion.
2. Examine the neighboring trees of the current tree (for example, using NNIs).
3. If a neighboring tree is found to be better than the current tree according to the chosen criterion, move to this new tree.
4. Repeat the process of examining neighbors and moving to better trees, continuing until a tree is reached that has no neighbors better than itself.

This procedure is known as a hill-climbing algorithm, because the search always proceeds “uphill” toward better trees at each step. The tree reached at the end of this process is called a local optimum, since it cannot be improved upon by considering only its immediate neighbors.

Limitation: Local versus Global Optimum

• Hill climbing cannot guarantee that the local optimum reached is also the true global optimum tree, that is, the single best tree among all possible tree topologies.
• This limitation arises because the search can become “trapped” at a tree that is better than all of its immediate neighbors, but which is still not the overall best tree available in the entire tree space.

Sequential Addition of Species

One method commonly used to generate multiple different starting points for hill climbing is sequential addition of species:

• The species under study are arranged in a random order.
• There is only one possible unrooted tree topology for the first three species in this list.
• Species are then added to the growing tree one at a time, with each new species connected to the existing tree in whichever position is locally optimal at that stage.
• This process continues until all species have been added, producing a single complete starting tree.
• Hill climbing (using NNIs) is then applied to this starting tree until a local optimum is reached.
• This entire procedure (random ordering, sequential addition, and hill climbing) is repeated many times, using different random orderings of the species each time.
• Multiple runs of this kind may produce several different local optima.
• If the procedure is repeated for a sufficiently long time, it becomes very likely that the best of all the local optima found will be the true global optimum.

This overall approach is called a heuristic search procedure. Because it does not exhaustively examine every possible tree, it cannot guarantee that the global optimum has actually been found; the only practical indication of success is that if the search has been run for a long time without finding any further improvement, the best tree found so far is probably the correct, optimal tree.

Role of the Neighbor Definition

• The definition of what constitutes a “local optimum” tree depends directly on the definition used for neighboring trees.
• If neighbors are defined only using NNIs, the search may converge on a tree that cannot be improved by any NNI, but that could still be improved by a longer-range move such as SPR or TBR.
• In principle, long-range moves can also be incorporated directly into the search strategy, and some phylogenetic software programs do include them.

Problem with Long-Range Moves

• Long-range moves tend to be disruptive: if a fairly good tree has already been found, most long-range moves are likely to produce a tree that is considerably worse, making such moves computationally wasteful.
• The most extreme possible long-range move would be to generate a completely random tree at each step of the search. While this strategy would eventually locate the global optimum by chance, it would be an extremely slow and inefficient search procedure.
• For this reason, most practical phylogenetic search programs use a combination of NNIs together with occasional longer-range moves, since this combination has been found through testing to be a reasonably efficient way of locating optimal trees.

Allowing Downhill Moves

• Search strategies are not necessarily restricted to moving only uphill at every step.
• Occasionally allowing downhill moves (moves to a temporarily worse tree) can help the search avoid becoming permanently trapped at a poor local optimum, and may allow better optima to be discovered more efficiently overall.
• The Markov Chain Monte Carlo (MCMC) method is one particular way of searching tree space that explicitly allows both uphill and downhill moves during the search process.

Conclusion

Tree optimization methods differ fundamentally from simple clustering algorithms such as UPGMA and NJ, since they require an explicit numerical criterion, such as the least-squares error function E used in the Fitch–Margoliash method, the likelihood value used in maximum likelihood, or the number of substitutions used in parsimony, and they search among candidate tree topologies to identify the tree that best satisfies this criterion. Because the total number of possible tree topologies grows extremely rapidly with the number of species, exhaustive search is only feasible for very small data sets, and heuristic search strategies must be used more generally.

These strategies rely on defining neighboring trees through moves such as nearest-neighbor interchange, subtree pruning and regrafting, and tree bisection and reconnection, and on searching tree space using hill-climbing algorithms combined with strategies such as sequential addition of species and repeated random starting points to reduce the risk of becoming trapped at a poor local optimum. Since hill climbing alone cannot guarantee that the true global optimum has been found, more advanced approaches, including the incorporation of long-range moves and methods such as Markov Chain Monte Carlo that permit downhill as well as uphill moves, are often used to improve the reliability of the tree search.