Combinatorics of leastsquares trees
See allHide authors and affiliations

Edited by Peter J. Bickel, University of California, Berkeley, CA, and approved May 21, 2008 (received for review March 3, 2007)
Abstract
A recurring theme in the leastsquares approach to phylogenetics has been the discovery of elegant combinatorial formulas for the leastsquares estimates of edge lengths. These formulas have proved useful for the development of efficient algorithms, and have also been important for understanding connections among popular phylogeny algorithms. For example, the selection criterion of the neighborjoining algorithm is now understood in terms of the combinatorial formulas of Pauplin for estimating tree length. We highlight a phylogenetically desirable property that weighted leastsquares methods should satisfy, and provide a complete characterization of methods that satisfy the property. The necessary and sufficient condition is a multiplicative fourpoint condition that the variance matrix needs to satisfy. The proof is based on the observation that the Lagrange multipliers in the proof of the Gauss–Markov theorem are treeadditive. Our results generalize and complete previous work on ordinary least squares, balanced minimum evolution, and the taxonweighted variance model. They also provide a timeoptimal algorithm for computation.
The leastsquares approach to phylogenetics was first suggested by CavalliSforza and Edwards (1) and Fitch and Margoliash (2).
Definition 1. (Pairedge incidence matrix) A phylogenetic Xtree is a semi labeled tree with leaves labeled by elements of a set X (see ref. 3 for basic definitions). Given such a tree T with edge set E and X = n, the pairedge incidence matrix of T is the
Definition 2. (Treeadditive map) Let T be a phylogenetic Xtree. A dissimilarity map D is Tadditive if for some vector l ∈ R^{E},
Problem 1. [Ordinary least squares (OLS) (1)] Find the phylogenetic Xtree T and Tadditive map D̂that minimizes for a fixed tree, the solution of Problem 1 is a linear algebra problem (Theorem 3). However Rzhetsky and Nei (4) showed that the OLS edge lengths could instead be computed by using elegant and efficient combinatorial formulas. Their result was based on an observation of Vach (5), namely that OLS edge lengths obey the desirable independence of irrelevant pairs (IIP) property [our choice of terminology is inspired by social choice theory (6)]. Let T be a phylogenetic Xtree and e an edge in T. A linear edge length estimator for e is a linear function from dissimilarity maps to the real numbers, i.e. Î_{e} = Σ_{ij}p_{ij}D_{ij}. We say that such an estimator satisfies the IIP property if p_{ij} = 0 when the path from i to j in T (denoted i̅,̅j̅) does not contain either of e's endpoints.
In other words, the IIP property is equivalent to the statement that the sufficient statistic for the leastsquares estimator of the length of e is a projection of the dissimilarity map onto the coordinates given by pairs of leaves whose joining path contains at least one endpoint ofe. It has been shown that this crucial property, motivated by the Markovian tree models used in phylogenetics, is satisfied not only by OLS estimators, but also by specific instances of weighted least squares (WLS) estimators (e.g., ref. 17).
Problem 2. (WLS) Let T be a phylogenetic Xtree and D be a dissimilarity map. Find the Tadditive map D̂ that minimizes
The variance–covariance matrix for WLS is the
Theorem 3. (Leastsquares solution) The solution to Problem 2 is given by D̂ = S_{T}Î, where We note that the OLS problem reduces to the case V = I. The statistical significance of the variance matrix together with a statistical interpretation of Theorem 3 is provided in the next section.
It follows from Eq. 4 that the lengths of the edges in a weighted leastsquares tree are linear combinations of the entries of the dissimilarity map. A natural question is therefore which variance matrices V result in edge length estimators that satisfy the IIP property? Our main result is an answer to this question in the form of a characterization (Theorem 6): A WLS model is IIP if and only if the variance matrix is semimultiplicative. We show that such matrices are good approximations to the variances resulting from popular distance estimation procedures. Moreover, we provide combinatorial formulas that describe the WLS edge lengths under semimultiplicative variances (Lemma 3) and show that they lead to optimal algorithms for computing the lengths (Theorem 8).
The key idea that leads to our results is a connection between Lagrange multipliers arising in the proof of the Gauss–Markov theorem and a weak form of the tree metric theorem of phylogenetics that provides a combinatorial characterization of treeadditive maps (Remark 1). This explains many isolated results in the literature on least squares in phylogenetics; in fact, as we show in The Multiplicative Model and Other Corollaries, almost all the known theorems and algorithms about leastsquares estimates of edge lengths follow from our results.
Best Linear Unbiased Estimator (BLUE) Trees
The foundation of leastsquares theory in statistics is the Gauss–Markov theorem. This theorem states that the BLUE for a linear combination of the edge lengths, when the errors have zero expectation, is a leastsquares estimator. We explain this theorem in the context of Problem 2.
Lemma 1. For any phylogenetic Xtree T, the matrix S_{T} is full rank.
Proof: We show that for any e ∈ E, the vector f_{e}^{t}=(0,…,1,…,0) of size E with a 1 in the eth position and 0 elsewhere, lies in the row span of S. Choose any i,j,k,l ∈ X such that the paths i̅,̅j̅ and k̅,̅l̅ in T do not intersect, and the intersection of the paths i̅,̅k̅ and j̅,̅l̅ is exactly the edge e. Note that where (S_{T})_{ik} is the row of S_{T} corresponding to the taxon pair i,j.
Theorem 4. (Gauss–Markov Theorem) Suppose that D is a random dissimilarity map of the form D = S_{T}l + ε, where T is a tree, and ε is a vector of random variables satisfying E(ε) = 0and Var(ε) = V, where V is an invertible variance–covariance matrix for ε.
Let M(S_{T}) be the linear space generated by the rows of S_{T} and f^{t} ∈ M(S_{T}). Then f^{t}Î = p^{t}D (where Î given by Eq. 4) has minimum variance among the linear unbiased estimators of f^{t} l.
Proof: Observe that the problem of finding p is equivalent to solving a constrained optimization problem: The first condition specifies that the goal is to minimize the variance; the second constraint encodes the requirement that the estimator is unbiased. Using Lagrange multipliers, it is easy to see that the minimum variance unbiased estimator of f^{t}l is the unique vector p satisfying In other words where U = S^{t}_{T}V^{−1}S_{T}.
The Gauss–Markov Theorem can also be proved directly by using linear algebra, but the Lagrange multiplier proof has two advantages: First, it provides a description of p different from Eq. 4 that is simpler and more informative. Second, the technique is general and can be used in many similar settings to find minimumvariance unbiased estimators. Hayes and Haslett 9 provide pedagogical arguments in favor of Lagrange multipliers for interpreting leastsquares coefficients and discuss the origins of this approach in applied statistics 10.
In phylogenetics, Theorem 4 (and its proof) are useful because for each edge e, the vector f_{e} in the standard basis for M(S^{t}_{T}) is associated with a vector p such that p^{t} D is the best linear unbiased estimator for the length of e. Similarly, the tree length is estimated from f_{T}^{t}=(1,1,…,1), which is also in M(S_{T}). The condition of Eq. 7 is particularly interesting because it says that there exists some Tadditive map Λ = S^{t}_{T}μ =V_{p}, whose (possibly negative) edge lengths are given by the Lagrange multipliers μ.
The following theorem provides a combinatorial characterization of treeadditive maps and, hence, of the Lagrange treeΛ.
Definition 3. (Weak fourpoint condition) A dissimilarity map D satisfies the weak fourpoint condition if for any i,j,k,l ∈ X, two of the following three linear forms are equal:
Theorem 5. A dissimilarity map D is treeadditive if and only if it satisfies the weak fourpoint condition.
Theorem 5 was first proved in ref. 11. For a recent exposition, see Corollary 7.6.8 of ref. 3, where it is derived by using the theory of groupvalued dissimilarity maps. We note that the pair of equal quantities in the fourpoint condition defines the topology of a quartet. Furthermore, the topology of the tree is defined uniquely by the topologies of all its quartets. We again refer the reader to ref. 3 for details.
The Lagrange equations (Eqs. 7 and 8) together with Theorem 5 form the mathematical basis for our results:
Remark 1. The condition 7 specifies that Vp must be a Tadditive map. It follows that Vp satisfies the weak fourpoint condition. In other words, Eq. 7 amounts to a combinatorial characterization of Vp, and hence p. The condition of Eq. 8 imposes a normalization requirement on p. Together these conditions are useful for finding p and also for understanding its combinatorial properties.
The structure of the Lagrange tree in the case of OLS is the middle quartet of the tree shown in Fig. 1. It immediately reveals interesting properties of the estimator. For example the fact that it is a tree on four taxa implies the IIP property. The content of ref. 12, Appendix 2 is that for tree length estimation under the balanced minimum evolution model, the Lagrange tree is the star tree. In fact, we will see that most of the known combinatorial results about leastsquares estimates of edge and tree lengths can be explained by Remark 1 and interpreted in terms of the structure of the Lagrange tree.
Main Theorem
Our main result is a characterization of IIP WLS estimators. In the sections that follow, we will see that the IIP property for WLS is not only biologically desirable but also statistically motivated and algorithmically convenient. We begin by introducing some notation and concepts that are necessary for stating our main theorem.
Definition 4. (Clade) A clade of a phylogenetic Xtree T is a subset A ⊂ X such that there exists an edge in T whose removal induces the partition {A,X\A}. We also use clade to mean the induced topology T_{A}.
Given a dissimilarity map D and a variance matrix V, we set where A,B are disjoint clades. If e_{1},…,e_{k} ∈ E(T) form a path with ends determining disjoint clades A and B, then D_{e1…ek} and Z_{e1…ek} represent D_{AB} and Z_{AB}, respectively. For a single edge e defining clades A,B,D_{e}, and Z_{e} represent D_{AB} and Z_{AB}.
Note that if e* is an edge in a tree T then Eqs. 7 and 8 imply that setting D = Λ above, where Λ is the Lagrange tree for any WLS edge length estimate Î(e*), gives where A,B are the clades defined by edge e.
Definition 5. (Semimultiplicative map) A dissimilarity map D is multiplicative with respect to disjoint clades A,B if for any a_{1},a_{2} ∈ A and b_{1},b_{2} ∈ B
We say that D is semimultiplicative with respect to T if it is multiplicative with respect to any pair of disjoint clades A,B, not defined by the same edge of T.
The following lemma is left as an exercise.
Lemma 2. D is semimultiplicative if and only if, for a diagonal variance matrix V with entries given by V_{ij} = D_{ij} for all pairs i,j, every clade A of T has the property that for any A′⊂A, and any clade B disjoint from A and induced by a different edge, for all x ∈ B, where ξ_{A′A}^{B} does not depend on x.
In fact, A satisfies Eq. 13 for all relevant B if and only if Eq. 13 holds for the two clades disjoint from A and defined by the two edges adjacent to the edge defining A.
The semimultiplicative condition is slightly weaker than log(V) being treeadditive. Removing the requirement that the clades A,B are defined by different edges of T results in the multiplicative analog of the fourpoint condition. By Theorem 5, this is equivalent to V_{ij}=Π_{eεi̅,̅j̅}w(e)^{−1} for some w : E(T) → R_{+}. Such dissimilarity maps are called treemultiplicative, and are studied in ref. 13.
Theorem 6. (Characterization of IIP WLS estimators) A WLS edge length estimator for an edge in a tree T has the IIP property if and only if the variance matrix is semimultiplicative with respect to T.
The proof of the theorem reduces to the WLS solution for the length of an edge in a tree with at most eight leaves (edge e* in Fig. 1):
Proposition 7. Let T be the phylogenetic Xtree shown in Fig. 1. The Lagrange tree Λ = S_{Tμ} for the WLS problem of estimating the length of the edge e* satisfies the property that μ_{1} = −μ_{2}, μ_{3} = −μ_{4}, μ_{5} = −μ_{6} and μ_{7} = −μ_{8}. Furthermore, these Lagrange multipliers and the remaining ones μ_{9},…,μ_{13} can be computed by solving μ=(S^{t}_{T}V^{−1}S_{T})−1f_{e*}.
Proof: Using the notation of Fig. 1, with the convention that the edge labeled by μ_{i} is e_{i}, it follows from Eq. 8 that Λ_{ei}=0 for i = 1,2,9. But Λ_{ei}=Λ_{eiej}+Λ_{eiek} for {i,j,k} = {1,2,9}, which implies that Λ_{eiej}=0∀i,j∈{1,2,9}. Therefore Λ_{e1e2}=Λ_{AB}=V_{AB}^{−1}(μ_{1}+μ_{2})=0. The arguments for e_{3},e_{4}, e_{5}, e_{6} and e_{7}, e_{8} are identical, and the result follows. The complete solution μ for a given V is obtained from μ=(S^{t}_{T}V^{−1}S)^{−1}f_{e*}, which reduces to the inversion of a 13 × 13 matrix.
Note that the proof only uses the fact that e_{1}, e_{2} are adjacent leaf edges not adjacent to e*. The conclusion μ_{e1}=−μ_{e2} will hold identically in any tree for a pair of edges of this type.
Proof of Theorem 6: We begin by showing that if V is semimultiplicative, then the WLS edge length estimators have the IIP property. This calculation involves showing that for any phylogenetic Xtree T and edge e* ∈ T, the Lagrange tree for e* is the tree in Fig. 1, where A,B,C,D,E,F,G,H are clades with the property that their intraclade Lagrange multipliers are zero.
Let e_{1},…,e_{k}, with k ≤ 8, be the edges of T such that either d(e*,e_{i}) = 2 or d(e*,e_{i}) < 2 and e_{i} is a leaf edge. For i ∈ {1,…,k}, let C_{i} be the clade defined by e_{i} such that e* ∉ C_{i}. Let T^{/e*} be the phylogenetic X^{/e*}tree, where X^{/e*} = {C_{1},…,C_{k}}, with topology induced by T in the natural way (see Fig. 1). Let V^{/e*} be the diagonal variance matrix on pairs of nodes in X^{/e*} given by V_{CiCj}^{/e*}=Z_{CiCj}^{−1}.
We let μ^{/e*} be the Lagrange multipliers and Λ^{/e*} be the Lagrange tree for the problem of estimating the WLS edge length of e* from variance V^{/e*} and topology T^{/e*}. Let Î^{/e*} (e*) = (Λ^{/e*})^{t}(V^{/e*})^{−1}D^{/e*} be the resulting estimator given the distance matrix D^{/e*} on X^{/e*}:D_{CiCj}^{/e*}=D_{CiCj}Z_{CiCj}^{−1}.
Lemma 3. If V is semimultiplicative, the Tadditive map given by Λ = S_{Tμ} with satisfies the Lagrange equations for T and V. Thus μ are the Lagrange multipliers for Î(e*) and Î(e*) = Î^{/e*}(e*).
Proof of Lemma 3: It is an easy exercise to check that for all e ∈ E(T^{/e*}), we have Z_{e}^{/e*}=Z_{e} and Λ_{e}^{/e*}=Λ_{e}, where Z^{/e*} is an analog of Z for variance V^{/e*} and topology T^{/e*}. This implies that Λ_{e} = f_{e*}(e) for all e ∈ E(T^{/e*}), i.e. the Lagrange equation (Eq. 8) is satisfied for e ∈ E(T^{/e*}).
Now consider edge e ∈ E(C_{1}). We need to verify that Λ_{e} = 0. Because Λ_{ij} = 0 for all i,j∈C_{1},Λ_{e}=Λ_{e…e2}+Λ_{e…e9}. Now for all i ∈ C_{1} and j ∈ C_{2}, Λ_{ij}=μ_{1}^{/e*}+μ_{2}^{/e*}=0, so Λ_{e…e2}=0. Finally, let A′⊂A be a clade defined by e and let A″ be the clade defined by e_{9} that does not intersect A. The fact that V is semimultiplicative implies that for any taxon x ∈ A″ where ξ_{A′A} does not depend on the taxon x. This implies Λ_{e…e9}=Λ_{e1…e9}ξ_{A′A}^{C1}=Λ_{e1…e9}^{/e*}ξ_{A′A}^{C1}=0 by the proof of Proposition 7. This shows that Λ_{e} = 0 for e ∈ E(T)\E(T^{/e*}) and shows that μ are the Lagrange multipliers corresponding to Î(e*).
Also, Λ_{uv}=Λ_{CiCj}^{/e*} for all u∈C_{i},v∈C_{j}, which easily implies which is in turn equivalent to Î(e*) = Î^{/e*}(e*).
Because μ_{e} = 0 for all e ∉ T^{/e*}, it is enough to show that Λ^{/e*} satisfies the IIP property. This follows from Proposition 7. Therefore, V has the IIP property with respect to T, i.e. Λ_{ij} = 0 for all i,j ∈ X such that i̅,̅j̅ does not contain an endpoint of e*. This concludes the proof for the “if” part of Theorem 6.
For the “only if” direction, we will prove by induction that Eq. 13 is satisfied by all clades A of T, and thus the variance V is semimultiplicative with respect to T. The base case is provided by clades formed by a single leaf, for which Eq. 13 holds vacuously.
For the induction step, suppose clades A and B both satisfy Eq. 13, and that they are defined by adjacent edges e_{A} and e_{B} (see Fig. 2). Let e_{C} be the other edge adjacent to e_{A} and e_{B} and let C = X\(A ∪ B) be the clade it defines. We would like to prove that the clade (A ∪ B) also satisfies Eq. 13. If C = 1, this holds vacuously. We may therefore assume that there exist two more edges e_{1},e_{2} incident with e_{C}. Let C_{i}⊂C be the clade defined by e_{i}, for i = 1,2. It suffices to prove that (A ∪ B) satisfies Eq. 13 with respect to C_{1} and C_{2}. Notice that A and B already satisfy Eq. 13 with respect to C_{1} and C_{2}. Therefore it is enough to show that
Now consider the problem of estimating Î(e_{A}). Let μ be the corresponding Lagrange multipliers and Λ = S_{Tμ} be the Lagrange tree they define. By the IIP property, Λ defines an identically zero tree additive map on the clade C. Therefore the edge lengths corresponding to this map are all zero. This implies μ_{e} = 0 for all e ∈ E(C),e ≠ e_{1},e_{2}, and also μ_{e1}+μ_{e2}=0.
Let A_{1},…,A_{k}, with k ≤ 4 and B_{1},…,B_{t}, with t ≤ 2, be the subclades of A, respectively B, corresponding to nodes of T^{/eA}. Then for any x ∈ C_{1} and y ∈ A_{i}, and z ∈ B_{j}, Λ_{xy}=Λ_{C1Ai}^{/eA} does not depend on x,y, and Λ_{xy}=Λ_{C1Bj}^{/eA} does not depend on x,z.
Now pick leaf x ∈ C_{1} and let e be the leaf edge adjacent to it. Then Λ_{e} = 0. Because all Lagrange multipliers are 0 inside the clade C_{1},Λ_{e}=Λ_{e…e1}=Λ_{e…e2}+Λ_{e…ec}. Because μ_{e1}+μ_{e2}=0 and all Lagrange multipliers in C_{1} and C_{2} are 0, Λ_{e…e2}=. Thus Λ_{e…eC}=Λ_{{x}A}+Λ_{{x}B}=0. Equivalently, This imposes a nontrivial linear equation on Z_{{x}A} and Z_{{x}B} whose coefficients do not depend on x. Thus, does not depend on x.
An Optimal Algorithm for WLS Edge Lengths
Theorem 8. (Computing WLS edge lengths) Let D be a dissimilarity map and V an IIP variance matrix. The set of all WLS edge lengths estimates for a tree T can be computed in O(n^{2}), where n is the number of leaves in T.
Proof: Consider a given edge e*. Preserving the notation of the previous section, let C_{1},…,C_{k} be the clades of T corresponding to the vertices of T^{/e*}. By Lemma 3 we have: where S^{/e*} is the pairedge incidence matrix of T^{/e*}, and f^{/e*} is the standard basis vector corresponding to e* in T^{/e*}.
Once D^{/e*} and V^{/e*} are known, by Proposition 7, all the above steps take constant time to compute: The dominant computation is the inversion of a matrix of size at most 13 × 13. But for any edge e*, the elements of V^{/e*} and D^{/e*} are Z_{AB}^{−1} and D_{AB}/Z_{AB} for clades A,B of T, separated by at least two edges. Thus it only remains to show that we can compute D_{AB} and Z_{AB}, for all pairs of disjoint clades A,B, in O(n^{2}) time.
We define the height of a tree to be the distance between its root and its farthest leaf, where the root is taken to be the closest endpoint of the edge defining the clade. Thus the height of a clade formed by just one leaf is 0. Now consider the configuration in Fig. 3. The clades A,B,C are all pairwise disjoint and A and B are adjacent. It is easy to see that A ∪ B form a clade for which
Thus, we need only constant time to compute D_{A∪B,C} and Z_{A∪B,C} if D_{AC}, Z_{AC}, D_{CB}, and Z_{CB} are known. There are O(n) clades and, thus, O(n^{2}) pairs of disjoint clades. We can compute D_{AB} and Z_{AB} for all pairs AB through a simple dynamic program: We start with pairs of clades of height 0 (leaves), for which the values of D and Z are trivially given by D and V^{−1}. After round 2t of the algorithm, we will know D_{AB} and Z_{AB} for all disjoint pairs A,B of height at most t. After round 2t + 1 we know D_{AB} and Z_{AB} for all disjoint pairs A,B of height t + 1 and t respectively.
The algorithm is optimal because its running time is proportional to the size of the input.
The Multiplicative Model and Other Corollaries
In this section, we begin by giving formulas for the WLS edge lengths using a treemultiplicative variance model, i.e. V_{ij}=Π_{e∈i̅,̅j̅}w_{e}^{−1} for some w : E(T) → R_{+}. Throughout the section, e* ∈ E(T) denotes the edge for which the WLS length is being computed. If e* is an internal edge, then A,B,C,D are disjoint clades induced by adjacent edges. In the case that e* is adjacent to a leaf, that leaf is labeled i, and the adjacent clades are A,B.
Note that in Proposition 9, Z_{AB} and D_{AB} are as defined in the previous section, however for all the other examples, these quantities are redefined locally.
Proposition 9. The WLS edge length of an internal edge e* under dissimilarity map D and treemultiplicative variance V is if e* is adjacent to a leaf then the WLS length is
At first glance, these formulas may seem surprising, but the derivation is straightforward after solving for the Lagrange multipliers. By Lemma 3, is enough to solve for the Lagrange multipliers in the tree T^{/e*}, for (multiplicative) variance V^{/e*}. The proof of the above theorem is left as an instructive exercise for the reader. It rests on the following analog of Lemma 3 for treemultiplicative variances.
Proposition 10. The Lagrange tree for the WLS estimation of a single edge length under multiplicative variance is a quartet tree.
We now present a number of previous results about least squares that can be interpreted (and in some cases completed) by using Theorems 6 and 8, and Proposition 9. All the models we discuss here are special cases of the multiplicative variance model and our statements can be easily proven by substituting the appropriate form of V into Eqs. 21 and 22 and modifying the expressions for Z and D accordingly.
OLS. This is the first, and most studied, model for leastsquares edge and tree length estimation. It corresponds to a variance matrix equal to the identity matrix.
Corollary 11. [Rzhetsky 4] The OLS estimate Î(e*) = p^{t}D = f_{e}^{t}(S^{t}_{T}S_{T})^{−1}S^{t}_{T}D for the length of edge e is given by where n_{A}, n_{B}, n_{C}, and n_{D} are the number of leaves in the clades A,B,C, and D, and D_{AC}=∑_{a∈A,c∈C}D_{ac}/n_{A}n_{C}.
If e* is a leaf edge, î(e*) is given by: Our algorithm for computing edge lengths (Theorem 8) reduces, in the case of OLS, to that of ref. 14. It has the same optimal running time as the algorithms in refs. 5, 15 and 16.
Balanced minimum evolution (BME)
The BME model was introduced by Pauplin in ref. 17. The motivation was that in the computation of î(e*) in the OLS model, the distances D_{ac} and D_{bd} can receive different total weight from D_{ad} and D_{bc}, where a ∈ A, b ∈ B, c ∈ C, and d ∈ D. Pauplin therefore suggested an alternative model where all clades are weighted equally. One then defines recursively:

D_{{a}{b}} = D_{ab} for leaves a and b

D_{AB} = (D_{A′B} + D_{A″B}/2 for disjoint clades A and B such that A′ and A″ are the two clades of A pointing away from B.
Corollary 12. (Pauplin's edge formula) The WLS edge lengths with variance model V_{ij}∝2^{i̅,̅j̅} are given by î(e*) =
This corresponds to the multiplicative variance model with w_{e} = 0.5 for all edges e and follows easily from Proposition 9. As far as we are aware, this proof that the formulas given by Pauplin for edge lengths are in fact the WLS edge weights under the variance model described above has not been previously stated.
This result accompanies the connection between Pauplin's tree length formula and WLS tree length under the BME model established by Desper and Gasquel in ref. 12. They proved the following:
Corollary 13. [Desper and Gascuel 12] The tree length estimator given by î = ∑_{ab}D_{ab}2^{1−a̅,̅b̅} is the minimum variance tree length estimator for the BME model. It is also identical to the one given by the coefficients p^{t}=f^{t}(S^{t}_{T}V^{−1}S_{T})^{−1}S^{t}_{T}V^{−1}.
Proof: The second part of the corollary follows trivially from Theorem 4. For the first part, notice that p_{ab}=2^{1−a̅,̅b̅}, therefore p_{ab} V_{ab} is the uniform vector and thus defines a Tadditive map corresponding to the star topology (equallength leaf edges and zerolength internal edges). Finally, ∑_{i,j}S_{ij,e}p=1 follows from an easy counting argument.
The taxonweighted variance model. Another well known WLS model was introduced in ref. 18. Under this model, V_{ij}^{−1}=t_{i}t_{j} for some t_{1},…,t_{n} ∈ R_{+}. In the treemultiplicative model, this corresponds to setting w_{e} = 1 for internal edges and w_{e} = t_{i} when e is the edge adjacent to leaf i. Ref. 18 gives a beautiful proof for the statistical consistency of this model (which implies statistical consistency of OLS), and also provides an O(n^{2}) algorithm for computing the WLS edge lengths. However, the algorithm is based on a recursive agglomeration scheme, and an explicit formula for the edge lengths based on the values of D is not given. Such a formula follows from Theorem 6:
Corollary 14. For e an internal edge of T, the WLS edge length Î(e*) is given by
where T_{X}=∑_{x∈X}t_{x} and
If e* is adjacent to a leaf,
Final Remarks
An important question is whether the variance matrices required for the IIP property to hold are realistic for problems where branch lengths are estimated by using standard evolutionary models. We argue that although variances of distances estimated by using maximum likelihood are not multiplicative, they are approximately so for large distances.
We illustrate this for the Jukes–Cantor model 19. Because the estimated distance between two sequences can be infinite with small, but nonzero probability, the expected distance and its variance are infinite. However, the large sample “δ approximation” in the following proposition is commonly used in practice.
Proposition 15. (20,21) Let Y be the fraction of different nucleotides between two length n sequences, generated from the Jukes–Cantor process with branch length δ. Then the expected value of the empirical distance
Theorem 6 sheds light on the Fitch–Margoliash model. The assumption that the variance V_{ij}=Var(D_{ij})∝D_{ij}^{2} results in a WLS estimator that is not IIP because V is not semimultiplicative. This means that for generic dissimilarity maps, the Fitch–Margoliash leastsquares estimates of edge lengths will depend on irrelevant distance estimates. On the other hand, Corollary 12 is useful for interpreting the neighborjoining algorithm. In fact, it is possible to show that the edge length estimates of ref. 23 are precisely the Pauplin formulas (and hence leastsquares formulas) for the trees at each agglomerative step.
Our optimal algorithm for weighted leastsquares edge length estimates for multiplicative matrices is similar in spirit to some of the algorithms in ref. 15. In fact, we believe that all the fast algorithms for WLS edge lengths can be understood within a single framework. The unifying concept is the observation that they all essentially estimate the Lagrange tree, either via a topdown or bottomup approach. We defer a detailed discussion.
Finally, a key issue is that of consistency of the minimum evolution principle for weighted leastsquares tree length, under specific forms of variance matrices assigned to all trees 18, 24. An obvious question is what classes of semimultiplicative variance matrices result in consistent tree estimates and, moreover, which semimultiplicative variance matrices give identical treelength estimates. In the latter direction, we note that although it follows from Theorem 4 that for any V and f there is a unique BLUE p for f^{t} l, the converse of this statement is not true. In fact, for some tree topologies, it is even possible that the OLS tree length is equal to the BME WLS tree length (for example for five taxa trees). This means that by minimizing the tree length, some information about the variance is being discarded. This may be viewed as a weakness rather than as a strength of minimum evolution frameworks. A full discussion of this topic is beyond the scope of this article.
Acknowledgments
R.M. was supported by a National Science Foundation (NSF) Graduate Fellowship and partially by the Fannie and John Hertz foundation. L.P. was supported in part by NSF Grant CCF0347992.
Footnotes
 ^{‡}To whom correspondence may be addressed. Email: lpachter{at}math.berkeley.edu or mihaescu{at}berkeley.edu.

Author contributions: R.M. and L.P. designed research, performed research, and wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.
 © 2008 by The National Academy of Sciences of the USA
References
 ↵
 ↵
 Fitch WM,
 Margoliash E
 ↵
 Semple C,
 Steel M
 ↵
 ↵
 Vach W
 Opitz O
 ↵

 Semple C,
 Steel M

 Matheron G
 ↵
 Patrinos AN,
 Hakimi SL
 ↵
 Desper R,
 Gascuel O
 ↵
 ↵
 ↵
 ↵
 Gascuel O
 ↵
 ↵

 Jukes TH,
 Cantor C
 Munro HN
 ↵
 Bulmer D
 ↵

 Felsenstein J
 ↵