Systematic Biology

Systematic Biology 2008 57(2):243-250; doi:10.1080/10635150802033014

This Article Abstract FREE Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Search for citing articles in: ISI Web of Science (3) Request Permissions Google Scholar Articles by Steel, M. Articles by Rodrigo, A. Search for Related Content PubMed Articles by Steel, M. Articles by Rodrigo, A. Social Bookmarking          What's this?

© 2008 Society of Systematic Biologists

Maximum Likelihood Supertrees

Mike Steel¹ and Allen Rodrigo²

¹ Allan Wilson Centre for Molecular Ecology and Evolution, Department of Mathematics and Statistics, University of Canterbury Christchurch, New Zealand; E-mail: m.steel{at}math.canterbury.ac.nz
² The Bioinformatics Institute and the Allan Wilson Centre for Molecular Ecology and Evolution, University of Auckland New Zealand and Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier France; E-mail: a.rodrigo{at}auckland.ac.nz

	Abstract

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
We analyze a maximum likelihood approach for combining phylogenetic trees into a larger "supertree." This is based on a simple exponential model of phylogenetic error, which ensures that ML supertrees have a simple combinatorial description (as a median tree, minimizing a weighted sum of distances to the input trees). We show that this approach to ML supertree reconstruction is statistically consistent (it converges on the true species supertree as more input trees are combined), in contrast to the widely used MRP method, which we show can be statistically inconsistent under the exponential error model. We also show that this statistical consistency extends to an ML approach for constructing species supertrees from gene trees. In this setting, incomplete lineage sorting (due to coalescence rates of homologous genes being lower than speciation rates) has been shown to lead to gene trees that are frequently different from species trees, and this can confound efforts to reconstruct the species phylogeny correctly.

Keywords: Gene tree; maximum likelihood; phylogenetic supertree; species tree; statistical consistency

Received August 15, 2007; Revised November 19, 2007; Accepted January 15, 2008

---

Combining trees on different, overlapping sets of taxa into a parent "supertree" is now a mainstream strategy for constructing large phylogenetic trees. The literature on supertrees is growing steadily: new methods of supertree reconstruction are being developed (Cotton and Wilkinson, 2007) and supertree analyses are shedding light on fundamental evolutionary questions (Bininda-Emonds et al., 2007). Despite this surge in research activity, it is probably fair to say that biologists are still confused about what supertrees really are and what it is we do when we build a supertree. Are we, as some maintain, simply summarizing the phylogenetic information contained in a group of subtrees? Or are we trying to derive the best estimate of phylogeny given the information at hand? Nor is it clear which of these two conceptually different objectives underpin the various supertree reconstruction methods.

We take the view that what biologists really want a supertree reconstruction method to deliver is the best hypothesis of evolutionary relationships that can be inferred from the data available. Obviously, it is not the case that the supertree constructed as a summary statistic will necessarily be the best estimate of phylogeny. Nonetheless, if we are prepared to consider supertree reconstruction a problem of phylogenetic estimation, we have at our disposal an arsenal of phylogenetic tools and methods that have been tried and tested. Matrix representation with parsimony (MRP; Baum and Ragan, 1992), weighted MRP (Bininda-Emonds and Sanderson, 2001), matrix representation with compatibility (MRC; Rodrigo, 1996; Ross and Rodrigo, 2004), and, most recently, Bayesian supertree reconstruction (BSR; Ronquist et al., 2004) are undoubtedly inspired by standard phylogenetic methods. A gap remains, though, as there has been remarkably little development of likelihood-based methods for supertree reconstruction.

In this paper, we analyze an approach to obtain maximum likelihood (ML) estimates of supertrees, based on a probability model that permits errors in subtree topologies. The approach is of the type described by Cotton and Page (2004), and it permits supertrees to be estimated even if there is topological conflict amongst the constituent subtrees. We show that ML estimates of supertrees so obtained are statistically consistent under fairly general conditions. By contrast, we show that MRP may be inconsistent under these same conditions. We then consider a further complication that arises in the supertree setting when combining gene trees into species trees—in addition to the possibility that the input gene trees are reconstructed incorrectly (either a consequence of the reconstruction method used, or some sampling error), there is a further stochastic process that leads to the (true) gene trees differing from their underlying species tree (a consequence of incomplete lineage sorting). Although simple strategies such as gene concatenation have recently been shown to be potentially misleading (Degnan and Rosenberg, 2006), we show that an ML supertree approach for combining gene trees is also statistically consistent.

	Terminology

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
Throughout this paper, unless stated otherwise, phylogenetic trees may be either rooted or unrooted, and we will mostly follow the notation of Semple and Steel (2003). In particular, given a (rooted or unrooted) phylogenetic tree on a finite set X of taxa (which will always label the leaves of the tree), any subset Y of X induces a phylogenetic tree on taxon set Y, denoted |Y, which, informally, is the subtree of that connects the taxa in Y only. In the supertree problem, we have a sequence = (₁, ₂, ..., _k) of input trees, called a profile, where _i is a phylogenetic tree on taxon set X_i. We wish to combine these trees into a phylogenetic tree on the union of the taxon sets (i.e., X = X₁ X₂ ... X_k). We assume that the trees in are either all rooted or all unrooted, and that is rooted or unrooted accordingly. We will mostly assume that trees are fully resolved (i.e., binary trees, without polytomies); in a remark following Theorem 4, we briefly describe how this restriction can be lifted. Furthermore, in this paper we consider just the tree topology, not the branch lengths.

A special case of the supertree problem arises when the taxon sets of the input trees are all the same (X₁ = X₂ = ... = X_k). This is the much studied consensus tree problem. In an early paper, McMorris (1990) described how, in this consensus setting, the majority-rule consensus tree can be given a maximum likelihood interpretation. However, this approach is quite different from the one described here (it is restricted to the consensus setting and is based on a very particular probability model).

In this paper, we will denote the underlying ("true") species tree as ₀ (assuming that such a tree exists and that the evolution of the taxa has not involved reticulate processes such as the formation of hybrid taxa). In an ideal world, we would like _i = ₀ | X_i for each tree _i in the profile—that is, we would like each of the reconstructed trees to be identical to the subtree of the true tree for the taxa in X₀. But in practice, the trees ₁,...,_k are unlikely to even be compatible (i.e., no phylogenetic tree exists for which _i = |X_i for all i).

	An Exponential Model of Phylogenetic Error

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
Species trees that have been inferred from data may differ from the true underlying species tree for numerous reasons, including sampling effects (short and/or site-saturated sequences, or poorly defined characters), model violation, sequencing or alignment errors, and so forth. In this section, we will assume a simple model of phylogenetic error in which the probability of observing a given tree falls off exponentially with its distance from an underlying generating tree (e.g., the true species tree ₀). This type of model has been described by Holmes (2003) in the general setting of Bayesian statistical analysis in phylogenetics. Suppose d is some metric on resolved phylogenetic trees. There are several possible choices for d, depending on the biological context and computational considerations, and we describe some of these shortly. In the exponential model, the probability, denoted _{, Y}['] (or more briefly [']) of reconstructing any species tree ' on any taxon set Y (where Y X), when is the generating tree (on taxon set X) is proportional to an exponentially decaying function of the distance from ' to |Y. In other words,

(1)

The constant β can vary with Y and other factors (such as the quality of the data); for example, trees constructed from long high-fidelity sequences are likely to have a larger β than trees constructed from shorter and/or noisier sequences. The constant is simply a normalizing constant to ensure that _{', Y}['] = 1, where the sum is over all fully resolved phylogenetic trees ' on taxon set Y. When we have a sequence (X₁, X₂, ...) of subsets of X, we will reflect the dependence of , β on X_i by writing _i and β_i. Note that _i is determined entirely by β_i and |X_i|.

Note that, implicit in (1), the probability of ' depends only on the subtree of connecting the species in ' and not on the other species in that are not present in '.

Now, suppose we observe the profile of trees = (₁, ₂, ..., _k) as above, where _i has leaf set X_i. Assume that, for each i, the tree _i has been independently sampled from the exponential distribution (1) with β = β_i. Select a phylogenetic X tree that maximizes the probability ((₁, ..., _k)) of generating the observed profile —we call this type of a tree an ML supertree for .

An ML supertree has a simple combinatorial description as a (weighted) median tree, as the following result shows. Note that the use of sums of tree-to-tree distances as optimality criteria has previously been suggested by Wilkinson et al. (2001).

Proposition 1.For any metric d on phylogenetic trees, an ML supertree for a profile under the exponential model (1), is precisely a tree that minimizes the weighted sum:

Proof. By the independence assumption,

and, by (1), _{, Xi} [_i] = _iexp [–β_id(_i, |X_i)]. Consequently, [(₁, ₂, ..., _k)] is proportional to

and this is maximised for any tree that minimizes _{i = 1}^k β_id(_i, |X_i). This completes the proof.

Note that there may exist more than one ML supertree. This would be more likely if one has a small number of input trees and the distance metric is "coarse" (e.g., the symmetric difference metric) rather than "fine" (e.g., SPR: subtree-prune-and-regraft distance) and if the β_i values are all equal.

In the special case where d is the nearest-neighbor interchange (NNI) metric, and the β_i values are all equal, this ML supertree was described by Cotton and Wilkinson (2007). Moreover, in the consensus tree setting, and where d is the symmetric difference (Robinson-Foulds) metric, the consensus of the ML supertrees is the same as the usual majority-rule consensus tree. This follows from earlier results by Barthélemy and McMorris (1986; see also Cotton and Wilkinson, 2007).

The choice of metric d should be guided by the biological context and computational expediency—-for example, the SPR metric appropriately models horizontal gene transfer events, whereas the NNI metric may be appropriate for trees that lack local resolution; however, the symmetric difference metric may also be useful as it is fast to compute.

Note also that the β_i values are not regarded as variables to be optimized in the ML procedure (to do so would lead to all trees being optimal solutions because β_i = 0 would be the optimal selection for all i). Rather, they allow other external factors (e.g., how well supported each input tree is by the data) to be reflected in the model. As a default option (in the absence of such knowledge), one might set all the β_i values equal.

The use of the exponential error model requires some explanation. In standard, character-based, or sequence-based phylogenetic analysis, the probability of obtaining the data is derived using a model of character or sequence substitution. This "process-based" approach to calculating the likelihood differs from the "error-based" approach we have adopted here. With an error-based approach, we model the probability distribution of outcomes, in this case the distribution of trees one may obtain from subsets of data. The value of this approach is that it is independent of process. The choice of an exponential distribution to describe the fall-off in probability of a tree as one moves further from the true tree is somewhat arbitrary but is due to simplicity and computational efficiency (Proposition 1). Regardless of the reasons why subtrees differ from the true supertree (i.e., regardless of the process), if the distribution of these differences can be modeled using an exponential distribution, our results hold.

	Statistical Consistency of ML Supertrees under the Exponential Model

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
Is the ML procedure statistically consistent as the number (k) of trees in the profile grows? More precisely, under what conditions is the method guaranteed to converge on the underlying generating tree ₀ as we add more trees to the analysis? The problem is slightly different from other settings (such as the consistency of ML for tree reconstruction from aligned sequence data) where one has a sequence of i.i.d. random variables. In the supertree setting, it is perhaps unrealistic to expect that the data sets are generated according to an identical process, since the sequence of subsets X₁, X₂,..., of X is generally deliberately selected.

To formalize the statistical consistency question in this setting, let X₁, X₂,..., be a sequence of subsets of finite set X. It is clear that the X_is must cover X in some reasonable way in order for the ML supertree method to be consistent—for example, if some taxon is not present in any X_i, or is present in only a small number of input trees, then we cannot expect the location of this taxon in any supertree to be strongly supported.

Thus, we will assume that the sequence of subsets of X satisfies the following covering property: For each subset Y of taxa from X of size m (where m = 3 for rooted trees or m = 4 for unrooted trees), the proportion of subsets X_i that contain Y does not decay to 0 as the sequence length (of subsets) increases. More formally, for each such subset Y of X we assume there is some > 0 and some K sufficiently large for which:

(2)

If a subset of taxa, Y, is only found in one or a few trees and is never seen again in trees that are subsequently added, this property will not hold.

We now establish statistical consistency of ML supertrees under a much more general class of models than the exponential model. Consider any model M for generating phylogenetic trees (without branch lengths) on subsets of X that has a generating phylogenetic X tree as its sole underlying parameter. Such a model will typically derive from a more complex model containing other parameters (such as branch lengths, population sizes, and so forth), but we will assume that these have a prior distribution and that they have been integrated out, so our model has just one parameter—the tree topology.

Given a sequence (X₁, X₂, ..., X_k...) of subsets of X we say that M satisfies the property of centrality if, for some > 0, and all i 1, we have:

(3)

for all trees ' on leaf set X_i that are different from |X_i. This condition says that, if is the generating tree, then amongst all phylogenetic trees on leaf set X_i, the one that induces on X_i is always (strictly) more probable than any other tree.

As a related condition, we say that M satisfies the property of basal centrality if, for some > 0, and all i 1, we have:

(4)

for all trees ' on leaf set Y that are different from |Y, and all Y eqX_i, of size m (= 3 for rooted trees and = 4 for unrooted trees). This condition says that, if is the generating tree, then amongst all the small (m element) subsets Y of X_i the tree that induces on Y is (strictly) more probable that any other tree.

Notice that the exponential model (with the β_i values bounded away from 0) satisfies centrality (take = min _{i 1} [_i(1–e^–β_i)]). We will see later that basal centrality is a useful concept for another setting (lineage sorting). Note also that basal centrality (for a sequence X_i) is not a special case of centrality, and, conversely, centrality is not a special case of basal centrality, though of course the two notions coincide in the special case where |X_i| = m for all i.

We now show that the selection of an ML supertree is statistically consistent for any model M that satisfies either centrality or basal centrality when applied to a sequence of subsets of X that obeys the covering property. Its proof (along with the proofs of all following propositions and theorems) is given in the Appendix.

Theorem 2.Given a sequence X₁,X₂,..., which satisfies the covering property (2), consider a profile _k = (₁, ..., _k), where _i is generated independently, from a tree ₀ with taxon set X, according to a model M that satisfies either the centrality or basal centrality property for this sequence. Then the probability that _k has a unique ML supertree and that this tree is ₀ tends to 1 as k .

Remarks

• We can easily modify the ML process if some of the input trees are not fully resolved (due to "soft" polytomies). For a general phylogenetic tree t_i (possibly with polytomies) on taxon set X_i eqX, and a generating fully resolved phylogenetic tree on taxon set X, let (t_i|) be the probability of the event that the tree _i that generates under the exponential model is a refinement of t_i. More precisely,
  

  where _i t_i indicates that the (fully resolved) tree _i contains all the splits present in t_i and has the same leaf set (X_i). Notice that (t_i|) is not a probability distribution on phylogenetic trees with the leaf set X_i (its sum is > 1). Nevertheless, given a profile = (t₁, ..., t_k) of phylogenetic trees (some or all of which may have polytomies), one can perform ML to select the tree that maximizes the joint probability _{i = 1}^k (t_i|) of the events _i t_i for i = 1,..., k.
  

• We point out an alternative way of viewing this ML procedure applied to a profile = (₁, ..., _k) when d is one of two well-known metrics on trees (SPR and TBR). Suppose that we were to extend each tree _i in to a tree '_i on the full set of taxa (X). We could regard the placement of those taxa that are missing in _i (namely the taxa in X–X_i) to form a tree _i' on the full leaf set X to be "nuisance parameters" in a maximum likelihood framework (under the exponential model), and thereby seek to find the tree and extensions (₁', ..., _k') to maximize the joint probability:
  

  We call such a tree an extended ML tree for the profile ; it turns out to be just the same as the ML trees we have defined above, as the next result shows.
  

Proposition 3.For d = SPR or d = TBR, and any profile of fully resolved, unrooted phylogenetic trees, the extended ML tree(s) for coincides precisely with the ML tree(s) for .

	Relation to MRP and Its Statistical Inconsistency

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
In the MRP (matrix representation with parsimony) supertree method, the input trees are coded as characters—one for each interior edge of each tree—with character states 0, 1, ? depending, respectively, on whether the taxon in question is on one side, or the other, of the edge, or is absent from the tree. A most parsimonious tree (or trees) is then reconstructed from this data matrix. As shown recently by Bruen and Bryant (2007), there is a close analogy between MRP and consensus tree methods, which seek a median tree computed using the SPR (subtree prune and regraft) or TBR (tree bisection and reconnection) metric d (recall that a median tree for a profile = (₁, ... _k) of trees that all have same leaf set X, is a tree that minimizes the sum _{i = 1}^kd(, _i); cf. Proposition 1). However, the result from Bruen and Bryant (2007) does not guarantee that MRP produces an ML supertree even when β_i = 1 for all i, as their approach constructs a median on a space of trees that are defined by splits rather than particular trees.

We turn now to the question of the statistical consistency of MRP under the exponential model (1). It can be shown that MRP will be statistically consistent under the covering property (2) in some special cases. Two such cases that can be formally established (details omitted) are (i) when all the subsets X_i are of size m (= 3 for rooted trees and = 4 for unrooted trees); or (ii) when β_i is sufficiently large (in relation to |X|). However, in general, we have the following result.

Theorem 4.A β > 0 exists for which MRP is statistically inconsistent even in the special (consensus) case where, for all i, X_i is the same set of six taxa and β_i = β. More precisely, for this value of β and with unrooted fully-resolved phylogenetic trees on these (equal) taxon sets, the probability that ₀ is an MRP tree (for a profile of trees generated under (1)) converges to 0 as k tends to infinity.

Remarks

• The formal proof of Theorem 4 is given in the Appendix. However, the intuition behind the proof is that if β is sufficiently small (but still positive), then trees generated by the exponential model are close to a uniform random distribution on trees. For such input there is a slight bias of MRP towards unbalanced trees. This shape bias property of MRP has been explored (in related settings) by Wilkinson et al. (2005).
  
• The exact condition (on the β_is) at which inconsistency of MRP occurs is not clear, though some general comments can be made. For large values of β_i, the decay of the exponential function is rapid, and the probability of producing an incorrect subtree some distance away from the true tree is small. In these cases, MRP is likely to work well. However, when β_i is small, the probability of producing an incorrect subtree is relatively high, even when this subtree is some distance away from the true tree. An interesting theoretical question is whether a value s (0,1) exists for which MRP is statistically consistent (for arbitrarily large taxon sets) under the conditions of Theorem 4, whenever β_i = β s.
  

	Statistical Consistency of ML Species Supertrees from Multiple Gene Trees

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
A current problem in phylogenetics is how best to infer species trees from gene trees (Degnan and Rosenberg, 2006; Gadagkar et al., 2005; Liu and Pearl, 2007). Even in the consensus setting (i.e., when the set of taxa for each gene tree is the complete set of taxa under study), Degnan and Rosenberg (2006) have demonstrated how incomplete lineage sorting on gene trees can mean that the most likely topology for a gene tree can differ from the underlying species tree (for certain rooted phylogenetic trees on four taxa and for all rooted phylogenetic trees on five or more taxa). This surprising result implies that simplistic majority-rule approaches to finding a consensus species tree can be problematic.

The phenomenon described by Degnan and Rosenberg (2006) is based on the coalescent model for studying lineage sorting in evolving populations. The surprising behavior arises only when the effective population sizes and the branch lengths of the species tree are in appropriate ranges. Moreover, for rooted three-taxon trees, the most probable gene tree topology always agrees with the species tree topology. Nevertheless, the fact that larger gene trees can favor an incorrect species tree might easily complicate some standard statistical approaches.

In this section, we show how, despite the phenomena described above (from Degnan and Rosenberg, 2006), and even in the more general supertree setting (where some gene trees may have some missing taxa), a maximum likelihood approach to supertree construction of a species tree from gene trees is statistically consistent.

Consider first a somewhat idealist situation where we have a sequence of rooted gene trees, each correctly inferred (but possibly differing from the species tree due to lineage sorting) for a sequence of (arbitrary size) subsets of X that satisfy the covering property. The statistical consistency of ML under this scenario follows immediately from Theorem 2 (using basal centrality, not centrality) because lineage sorting (regarded as an error model M for deriving gene trees from species trees under the coalescent model) satisfies basal centrality. This is because, under the coalescent model, ^c_{, Y}[|Y] = 1–2/3e^–, whereas ^c_,Y[''] = 1/3e^– for the two other choices of '' |Y, where is (up to a factor of 2) the ratio of time (measured in generations) to the effective population size (see, e.g., Rosenberg, 2002; Tajima, 1983). Consequently,

for all subsets Y of X_i of size 3. The limitation of this consistency result is that it invokes the unrealistic assumption that the gene trees have all been correctly inferred. We thus consider a more realistic scenario; however, in order to prove a consistency result, we must restrict the input trees to have just 3 leaves each. We thus consider the following situation:

Triplet-based supertree with dual error: a sequence of rooted gene trees inferred, possibly with error, on subset of X of size 3 that satisfy the covering property, provided the error in the reconstructed gene tree (differing from the true gene tree) is described by the exponential model.

The statistical consistency of ML supertrees under this scenario (Triplet-based supertree with dual error) is due to the following result (where M₁ is the lineage sorting model that derives a gene tree from a species tree, whereas M₂ models the error in reconstructing the gene tree correctly).

Proposition 5.Given a sequence X₁,X₂,..., of subsets of X of size 3 that satisfies the covering property (2), consider a profile _k = (₁, ..., _k), where tree _i is generated independently, from a tree ₀ with taxon set X, by first generating a tree on taxon set X_i under some central model, M₁, and then, independently, using this tree to generate _i according to an exponential model, M₂. Then the probability that _k has a unique ML supertree and that this tree is ₀ tends to 1 as k .

	Discussion

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
To develop a likelihood-based supertree reconstruction method, it is necessary to define a model that delivers the probability of obtaining a series of subtree topologies, given a hypothesized supertree. We have chosen a very simple yet intuitive probability function whereby the probability of observing a wrong subtree (i.e., one where the topology differs from that of a pruned supertree) decreases exponentially as its topology becomes increasingly distant from that of the hypothesised supertree. Consequently, the ML supertree can be estimated even when the constituent subtrees have conflicting topological signals.

Our approach is model based, but one may reasonably ask whether the model described here is a biologically realistic one. We suggest that it is. For one thing, we expect, for a variety of reasons, to see conflicts between the topologies of subtrees and the reconstructed supertree. With gene sequences obtained from different species, for instance, incomplete lineage sorting and ancestral heterozygosity frequently lead to differences between gene trees and species trees. Convergent and parallel evolution can confound phylogenetic reconstruction, as can long-branch attraction. We have chosen to use the exponential distribution to describe this steady decrease in probabilities as the distances between subtrees and supertrees increase. The value of using the exponential distribution lies in the ease with which it can be manipulated when we compute log-likelihoods. Additionally, we have noted that our model is an error-based model; i.e., it describes the distribution of subtree-to-supertree distances without regard for the underlying processes that cause topological conflicts. However, we suggest that one fruitful research project may be to explore other possible probability distributions, other tree-to-tree distance metrics, as well as process-based models of topological conflict. In this respect, coalescent-based models of incomplete lineage sorting (Carstens and Knowles, 2007) may hold some promise. As with the original phylogenetic likelihood methods designed for character and sequence data, we hope to see new models emerge as other researchers explore the use of ML supertrees. Even if one is reluctant to use the exponential distribution, the statistical consistency of ML supertrees is nonetheless guaranteed, provided the probability distribution of subtree-to-supertree distances assigns the highest probability to a distance of zero.

The likelihood framework provides an additional benefit: a rich body of statistical and phylogenetic methods already use likelihood. Moreover, statistical consistency holds for maximum likelihood supertrees under weak conditions, in contrast to MRP, which can be inconsistent in some cases. We also show that the ML supertree approach developed here provides a statistically consistent strategy for combining gene trees even when there is the possibility that these trees may be different from the true species tree. An obvious application of ML supertrees will be their use in statistical tests of topological hypotheses, and we already know how to do this with standard ML phylogenies (Goldman et al., 2000).

We also recognize that our particular likelihood implementation is closely related to the Majority-Rule(–) Supertree construction proposed by Cotton and Wilkinson (2007). More precisely, when the tree metric is the symmetric difference (Robinson-Foulds) metric, then the Marjority-Rule(–) Supertree is, in effect, the strict consensus of our ML supertrees. However, the approach in Cotton and Wilkinson (2007) is quite different: they show how to extend majority rule from the consensus to the supertree setting. Nonetheless, they converge on the same optimality criterion that we use; i.e., a supertree that minimizes the sum of distances to a set of trees. One should not be surprised that the same optimality criterion can emerge from different conceptual bases. With standard phylogenetic reconstruction, choosing the tree that minimizes the number of evolutionary changes can be justified philosophically (with the principle of maximum parsimony) as a consensus method (Bruen and Bryant, 2007) or by using an explicitly statistical approach such as likelihood (Steel and Penny, 2000).

We have not discussed algorithms to search for ML supertrees. As with classical phylogenetic likelihood methods, maximum likelihood supertrees will be obtained using a variety of approaches, including heuristic methods, genetic algorithms, simulated annealing, and so on. We also direct readers to the discussion in Cotton and Wilkinson (2007), because the criterion we use is similar to theirs.

	Appendix. Proofs of Main Results

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 
In this section we collect together the proofs of the main results. We start by stating a general sufficient condition for the consistency of ML in non-i.i.d. settings.

Consistency of ML for General (non-i.i.d.) Sequences
Here we describe a convenient way to establish the statistical consistency of maximum likelihood when we have a sequence of observations that may not be independent or identically distributed. We frame this discussion generally, as the result may be useful for other problems. In particular, in this result, we do not need to assume the sequence samples are independent (though in our applications, they are), nor identically distributed (in our applications, they are not). Suppose we have a sequence of random variables Y₁, Y₂, ..., that takes values in some finite set W and are generated by some process that depends on an underlying discrete parameter a that can take values in some finite set A. In our setting, the Y_is are trees constructed from different data sets (e.g., gene trees), whereas a is the generating species tree topology. We assume that the model specifies the probability distribution of (Y₁,..., Y_k) given (just) a—for example, in our tree setting this would mean specifying prior distributions on the branch lengths and other parameters of interest (e.g., ancestral population sizes) and integrating with respect to these priors.

Given an actual sequence (y₁,..., y_k) of observations, the maximum likelihood (ML) estimate of the discrete parameter is the value a that maximizes the joint probability

(i.e., the probability that the process with parameter a generates (y₁, ..., y_k)). Now suppose that the sequence Y₁,... Y_k, ..., is generated by a₀. We would like the probability that the ML estimate is equal to a₀ to converge to 1 as k increases. If this holds for all choice of a₀ A, then ML is statistically consistent. The following result provides a convenient way to establish this; indeed, it characterises the statistical consistency of ML.

Proposition 6.In the general setup described above, ML is statistically consistent if and only if the following condition holds: for any two distinct elements a,b A, we can construct a sequence of events E₁, E₂,..., where E_k is dependent on (Y₁, ... Y_k), for which, as k :

1. the probability of E_k under the model with parameter a converges to 1.
   
2. the probability of E_k under the model with parameter b converges to 0.
   

Proof. The "only if" direction is easy: Suppose ML is statistically consistent and a, b A are distinct. Let E_k be the event that a is the unique maximum likelihood estimate obtained from (Y₁, ..., Y_k). Then E_k satisfies conditions (i) and (ii).

For the converse direction, recall that the variation distance between two probability distributions p,q on any finite set W is

where _p(E) = _{w E}p(w) is the probability of event E under distribution p (similarly for _q(E)). This variation distance can also be written as 1/2||p–q||₁, where ||p–q||₁ = _{w W}|p(w) – q(w)| is the l₁ distance between p and q. Thus, if we let d^(k)(a,b) denote the l₁ distance between the probability distribution on (Y₁, ..., Y_k) induced by a and by b, then conditions (i) and (ii) imply that

(5)

Now, by the first part (equation 3.1) of Theorem 3.2 of Steel and Szekely (2002), the probability that the ML estimate is the value of A that generates the sequence (Y₁, ..., Y_k) is at least 1 – _{b a} [1– 1/2d^(k)(a,b)] and so, by (5), this probability converges to 1 as k .

Proof of Theorem 2. To establish the theorem, using Proposition 6 (stated above) it is enough to specify for each choice of distinct resolved phylogenetic X-trees ₀ and , a sequence of events E_k (dependent on _k) for which, as k grows, E_k has a probability that tends to 1 under the distribution obtained from ₀ and tends to 0 under the distribution obtained from . Since differs from ₀ a subset Y exists of size m (= 3 for rooted trees and = 4 for unrooted) for which |Y ₀|Y. Notice that the covering property (2) implies that

(6)

Let E_k be the event that among all those i {1, ..., k} for which |X_{i 0}|X_i, we have _i = ₀|X_i more often than _i = |X_i. Now, for a profile generated by ₀ according to the model satisfying the centrality property, we have, for each i for which |X_{i 0}|X_i,

(7)

Similarly, for a profile generated by according to a model satisfying the centrality property, and for each i for which |X_{i 0}|X_i, we have

(8)

By condition (6), there is a positive limiting proportion ( > 0) of i for which |X_{i 0}|X_i. By independence (and the law of large numbers) it follows from inequality (7) that event E_k has a probability that tends to 1 as k for a profile generated by ₀. Similarly, by (8), event E_k has a probability tending to 1 as k for a profile generated by . Statistical consistency of ML now follows by Proposition 6.

For a model M satisfying basal centrality the same argument applies if we select Y as above and modify event E_k to be the event that among all those i {1, ..., k} for which Y eqX_i we have _i|Y = ₀|Y more often than _i = |Y.

Proof of Theorem 4. For two unrooted fully-resolved phylogenetic X-trees , ', let L(,') denote the total parsimony score on ' of the set of splits of . That is,

(9)

where () is the set of splits of and l(, ') is the parsimony score of the split on ' (treating as a binary character; Semple and Steel, 2003). For any fully resolved phylogenetic X tree ', let e('; ₀) be the expected total parsimony score on ' of the set of splits of a tree randomly generated by ₀ according to the exponential model (1). Then,

(10)

To establish Theorem 4, it is enough to show, for some β > 0 and for two unrooted fully resolved trees ₀, ₁ on X = {1, ..., 6}, that e(₀; ₀) – e(₁; ₀) > 0, because if ₀ is the generating tree, then ₁ will be favored over ₀ by MRP. We first show that this can occur when β = 0. In that case, exp [–β d(, ₀)] = 1/105 for all (there are 105 unrooted fully-resolved phylogenetic trees on X) and so, by (10), we have

Applying (9) and interchanging the order of summation gives:

(11)

where n() is the number of unrooted fully resolved phylogenetic X trees containing split and the summation is over all the splits of X = {1,..., 6}. Moreover, if any difference l(, ₀)– l(, ₁) is non-zero in (11), then is necessarily a split that partitions the taxa into sets of sizes either 2,4 or 3,3, and for such a split we have n() = 15 and 9, respectively.

Now suppose ₀ has a symmetric shape (i.e., an unrooted fully resolved tree of six leaves with three cherries) and ₁ has a pectinate shape (i.e., an unrooted fully resolved tree of six leaves with two cherries). Then, by using earlier results (Steel et al., 1992, table 3) concerning the number of splits that partition the taxa into sets of size 2,4 and 3,3 and have parsimony score 1,2,3 in these two trees, it can be shown from (11) that

So far, we have assumed that β = 0; however, e(₀; ₀) – e(₁; ₀) is a continuous function of β, so a strictly positive value of β exists for which

This completes the proof.

Proof of Proposition 3. For d = SPR or d = TBR, and for any resolved unrooted phylogenetic trees on taxon set X, and _Y on taxon set Y eqX we claim that:

(12)

where ' ranges over the set of all unrooted resolved phylogenetic tree on taxon set X that induce _Y when restricted to Y. To establish this claim, note firstly that, for any ' with taxon set X, and Y eqX, we have d('|Y, |Y) d(', ) and so the inequality holds in (12). To establish equality induction on k (starting with the base case k = 1) shows that if _Y and |Y are k SPR (or TBR) moves apart, then there exists an unrooted resolved phylogenetic ' on taxon set X that induces _Y when restricted to Y, and which is at most k SPR (or TBR, respectively) moves apart from . Having established (12), Proposition 3 now follows by Proposition 1.

Note that Equation (12) does not necessarily hold for other tree metrics such as the NNI (nearest-neighbor interchange) or the partition (Robinson-Foulds) metric.

Proof of Proposition 5. By Proposition 2 it suffices to show that the composite model satisfies centrality. Given a rooted phylogenetic tree on taxon set X, and a subset Y of X of size 3, label the three rooted binary trees on Y, ₁, ₂, ₃, so that ₁ = |Y. We need to show that, for some ' > 0, _,Y(₁) _,Y(_j) + ' for j = 2,3. By the independence assumption,

where _,Y⁽¹⁾(_j) is the probability of generating _j under model M₁ from generating tree , and _{j, Y}⁽²⁾(_k) is the probability of generating _k under model M₂ with generating tree _j. Now, _{j, Y}⁽²⁾(_k) takes the value for j = k, and the value e^–β for j k. Thus, _,Y(₁) = _,Y⁽¹⁾(₁) + e^–β[_,Y⁽¹⁾(₂) + _,Y⁽¹⁾(₃)], whereas _,Y(₂) = _,Y⁽¹⁾(₂) + e^–β[_,Y⁽¹⁾(₁) + _,Y⁽¹⁾(₃)]. Consequently,

A similar expression holds for other difference _,Y(₁) – _,Y(₃) and because M₁ is central, we can take ' to be the minimal value of (1–e^–β)[_,Y(₁) – _,Y(_k)] over k = 2,3.

	Acknowledgements

 
We thank the Allan Wilson Centre for Molecular Ecology and Evolution for supporting this work. Allen Rodrigo began this project while he was working with Olivier Gascuel at the Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier.

	References

Top Abstract Terminology An Exponential Model of... Statistical Consistency of ML... Relation to MRP and... Statistical Consistency of ML... Discussion Appendix. Proofs of Main... References

 

Barthélemy J. P., McMorris F. R. The median procedure for n-trees. J. Classif. (1986) 3:329–334.[CrossRef]

Baum B. R., Ragan M. A. Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon (1992) 41:3–10.[CrossRef][Web of Science]

Bininda-Emonds O. R. P., Cardillo M., Jones K. E., MacPhee R. D. E., Beck R. M. D., Grenyer R., Price S. A., Vos R. A., Gittleman J. L., Purvis A. The delayed rise of present-day mammals. Nature (2007) 446:507–512.[CrossRef][Medline]

Bininda-Emonds O., Sanderson M. J. Assessment of the accuracy of matrix representation with parsimony analysis supertree construction. Syst. Biol. (2001) 50:565–579.[Abstract/Free Full Text]

Bruen T., Bryant D. Parsimony as consensus. Syst. Biol. (2007) In press.

Carstens B., Knowles L. Estimating phylogeny from gene tree probabilities in melanoplus grasshoppers despite incomplete lineage sorting. Syst. Biol. (2007) 56:400–411.[Abstract/Free Full Text]

Cotton J. A., Wilkinson M. Majority-rule supertrees. Syst. Biol. (2007) 56:445–452.[Abstract/Free Full Text]

Degnan J. H., Rosenberg N. A. Discordance of species trees with their most likely gene trees. PLoS Genet. (2006) 2(5):e68.[CrossRef][Medline]

Gadagkar S. R., Rosenberg M. S., Kumar S. Inferring species phylogenies from multiple genes: Concatenated sequence tree versus consensus gene tree. J. Exp. Zool. (2005) 304B:64–74.

Goldman N., Anderson J. P., Rodrigo A. G. Likelihood-based tests of topologies in phylogenetics. Syst. Biol. (2000) 49:652–670.[Abstract/Free Full Text]

Holmes S. Statistics for phylogenetic trees. Theor. Pop. Biol. (2003) 63:17–32.[CrossRef][Web of Science][Medline]

Liu L., Pearl D. K. Species trees from gene trees: Reconstructing Bayesian posterior distributions of a species phylogeny using estimated gene tree distributions. Syst. Biol. (2007) 56:504–514.[Abstract/Free Full Text]

McMorris F. R. The median procedure for n-trees as a maximum likelihood method. J. Classif. (1990) 7:77–80.[CrossRef]

Rodrigo A. G. On combining cladograms. Taxon (1996) 45:267–274.[CrossRef][Web of Science]

Ronquist F., Huelsenbeck J. J., Britton T. Bayesian supertrees. In: Phylogenetic supertrees—Bininda-Emonds O. R. P., ed. (2004) Dordrecht, The Netherlands: Kluwer Academic Publishers. Chapter 9.

Rosenberg N. A. The probability of topological concordance of gene trees and species trees. Theor. Pop. Biol. (2002) 61:225–247.[CrossRef][Web of Science][Medline]

Ross H. A., Rodrigo A. G. An assessment of matrix representation with compatibility in supertree reconstruction. In: Phylogenetic supertrees—Bininda-Emonds O. R. P., ed. (2004) Dordrecht, The Netherlands: Kluwer Academic Publishers. Chapter 2.

Semple C., Steel M. Phylogenetics (2003) Oxford University Press.

Steel M., Penny D. Parsimony, likelihood and the role of models in molecular phylogenetics. Mol. Biol. Evol. (2000) 17:839–850.[Abstract/Free Full Text]

Steel M., Szekely L. A. Inverting random functions (ii): Explicit bounds for discrete maximum likelihood estimation, with applications. SIAM J. Discr. Math. (2002) 15:562–575.[CrossRef]

Steel M. A., Hendy M. D., Penny D. Significance of the length of the shortest tree. J. Classif. (1992) 9:71–90.[CrossRef]

Tajima F. Evolutionary relationships of DNA sequences in finite populations. Genetics (1983) 105:437–460.[Abstract/Free Full Text]

Wilkinson M., Cotton J. A., Creevey C., Eulenstein O., Harris S. R., Lapointe F.-J., Levasseur C., Mcinerney J. O., Pisani D., Thorley J. L. The shape of supertrees to come: Tree shape related properties of fourteen supertree methods. Syst. Biol (2005) 54:419–431.[Abstract/Free Full Text]

Wilkinson M., Thorley J. L., Littlewood D. T. L., Bray R. A. Towards a phylogenetic supertree for Platyhelminthes? In: Interrelationships of the Platyhelminthes—Littlewood D. T. L., Bray R. A., eds. (2001) London, UK: Taylor and Francis. 292–301.

CiteULike    Connotea    Del.icio.us    What's this?

This article has been cited by other articles:

				S. Simon, S. Strauss, A. von Haeseler, and H. Hadrys A Phylogenomic Approach to Resolve the Basal Pterygote Divergence Mol. Biol. Evol., December 1, 2009; 26(12): 2719 - 2730. [Abstract] [Full Text] [PDF]

				L. Liu, L. Yu, D. K. Pearl, and S. V. Edwards Estimating Species Phylogenies Using Coalescence Times among Sequences Syst Biol, October 1, 2009; 58(5): 468 - 477. [Abstract] [Full Text] [PDF]

				J. Dong and D. Fernandez-Baca Properties of Majority-Rule Supertrees Syst Biol, July 3, 2009; (2009) syp032v1. [Full Text] [PDF]

				R. Torices and A. A. Anderberg Phylogenetic analysis of sexual systems in Inuleae (Asteraceae) Am. J. Botany, May 1, 2009; 96(5): 1011 - 1019. [Abstract] [Full Text] [PDF]

				M. T. Holder, J. Sukumaran, and P. O. Lewis A Justification for Reporting the Majority-Rule Consensus Tree in Bayesian Phylogenetics Syst Biol, October 1, 2008; 57(5): 814 - 821. [Full Text] [PDF]

This Article Abstract FREE Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Search for citing articles in: ISI Web of Science (3) Request Permissions Google Scholar Articles by Steel, M. Articles by Rodrigo, A. Search for Related Content PubMed Articles by Steel, M. Articles by Rodrigo, A. Social Bookmarking          What's this?

Online ISSN 1076-836X - Print ISSN 1063-5157

Copyright © 2009 Society of Systematic Biologists

Oxford Journals Oxford University Press

• Site Map
• Privacy Policy
• Frequently Asked Questions

Other Oxford University Press sites: Oxford University Press Oxford Journals China Oxford Journals Japan American National Biography Booksellers' Information Service Children's Fiction and Poetry Children's Reference Corporate & Special Sales Dictionaries Dictionary of National Biography Digital Reference English Language Teaching Higher Education Textbooks Humanities International Education Unit Law Medicine Music Online Products Oxford English Dictionary Reference Rights and Permissions Science School Books Social Sciences Very Short Introductions World's Classics