{'fraction_non_alphanumeric': 0.04604348551409665, 'fraction_numerical': 0.016571206139131402, 'mean_word_length': 4.158921399885255, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Neighbor joining with phylogenetic diversity estimates

The Neighbor-Joining algorithm is a recursive procedure for reconstructing trees that is based on a transformation of pairwise distances between leaves. We present a generalization of the neighbor-joining transformation, which uses estimates of phylogenetic diversity rather than pairwise distances in the tree. This leads to an improved neighbor-joining algorithm whose total running time is still polynomial in the number of taxa. On simulated data, the method outperforms other distance-based methods. We have implemented neighbor-joining for subtree weights in a program called MJOIN which is freely available under the Gnu Public License at http://bio.math.berkeley.edu/mjoin/ .


Introduction
Distance based methods for phylogenetic reconstruction are based on the observation that edge weighted phylogenetic X-trees (trees that have a set X as their leaves, all interior vertices of degree at least three and non-negative weights w T : E(T ) → R >0 on every edge) can be encoded by certain metrics on X.
Theorem 1 (Four-point condition [Buneman, 1971]). Given a metric D : X × X → R there exists an edge weighted phylogenetic X-tree T such that D(i, j) = e∈E(T ) w T (e) iff D(i, j) + D(k, l) ≤ max(D(i, k) + D(j, l), D(j, k) + D(i, l)) for every four leaves i, j, k, l. Furthermore, T is unique.
Such metrics are called tree metrics and many methods have been proposed for projecting dissimilarity maps (functions D : X × X → R with D(x, x) = 0 and D(x, y) = D(y, x)) to "nearby" tree metrics. The neighborjoining algorithm, introduced by [Saitou and Nei, 1987], is the most popular and widely used. It is particularly convenient for reconstructing phylogenetic trees when the size of X is large, in which case methods that require an exhaustive exploration of the space of trees are computationally prohibitive.
There are four parts to the neighbor-joining algorithm (see algorithm 1): 1. A procedure for estimating pairwise distances between elements of X.

A criterion for identifying neighboring pendant edges (cherries) in a
tree.

A branch length estimation formula.
The cherry picking criterion is based on the following theorem: Theorem 2 ( [Saitou andNei, 1987, Studier andKeppler, 1988]). If D is a tree metric and then the pair x, y that minimizes Q D (x, y) is a cherry in the tree.
Although the exact formula for Q may seem a bit mysterious at first, it is a very natural criterion. For example, the neighbor-joining algorithm which is based on it is consistent (i.e. if D is a tree metric then the algorithm returns the tree), the input order of the taxa does not change the outcome of the algorithm, and the criterion is a linear function of the distances. [Bryant, 2005] has recently shown that the neighbor-joining selection criterion Q(i, j) is the only one satisfying the properties above. Furthermore, [Gascuel, 1997b] has shown that the neighbor-joining criterion can be interpreted as greedily minimizing a balanced minimum evolution criterion which provides added understanding as to why it has been a very successful method.
The recursive reduction step and branch length estimation formula have been examined extensively and have resulted in a number of improvements to the basic neighbor-joining algorithm. For example, the reduction step has been extensively investigated and has been shown to be optimal when variances on the estimates are unknown, yet improvable when variance information is incorporated [Gascuel, 1994, Gascuel, 1997a, Gascuel, 1997b.

Algorithm 1: Neighbor-joining algorithm
Data : A set X together with sequences corresponding to the elements of X Result: Edge weighted phylogenetic X-tree T for i, j ∈ X 2 do Compute the maximum likelihood distance D(i, j) between taxa i and j; end end Choose a pair x, y ∈ X that minimizes Q D (x, y); Add a new element z |X| to the set X and remove x and y; Let u |X| = x and v |X| = y.; Nevertheless, the main problem with neighbor-joining scheme is that in the first step, the distances are estimated from noisy data and the resulting dissimilarity map is therefore very unlikely to be a tree metric. For biological sequences, the pairwise distance estimates are typically based on a probabilistic model of evolution such as the [Jukes and Cantor, 1969] model: given two sequences of length L with k differences between them, the distance is estimated as Notice that as p → 3 4 the variance approaches infinity, which reflects the fact that long branch lengths are difficult to resolve with finite sequences. This phenomenon exists whenever branch lengths are estimated using Markov models of evolution. Although the neighbor-joining algorithm is consistent, the fact that dissimilarity maps estimated from data are not tree metrics means that there is no guarantee that the algorithm produces the correct tree.
A number of attempts have been made to understand the good results obtained with the neighbor-joining algorithm, especially given the problems with the inference procedures used for estimating pairwise distances. One of the main results is the following: Theorem 3 ( [Atteson, 1999]). Neighbor-joining has l ∞ radius 1 2 .

6
This means that if the distance estimates are at most half the minimal edge length of the tree away from their true value then the neighbor-joining algorithm will reconstruct the correct tree. However, as we will see in section 4, this criteria is rarely attained even in cases where neighbor-joining has a high success rate.
Despite the unavailability of precise criteria for judging the success of neighbor-joining, there have been efforts aimed at improving the distance estimates which form the input to the algorithm. For example, the TRIPLEML method [Ranwez and Gascuel, 2002] improves on the pairwise distance estimates by adjusting them using additional taxa: for each pair of leaves, a third leaf is selected and an approximate (numerical) maximum likelihood estimate for the branch lengths of the three leaf subtree is computed from which the pairwise distance of the original leaves is estimated. In the WEIGHBOR algorithm [Bruno et al., 2000], the neighbor-joining criterion is replaced so as to weight long branch lengths. These methods, and others similar to them, have the drawback that either their performance remains limited by the inherent uncertainty in pairwise distance estimates, or else the simple, natural, and mathematically justified structure of the neighbor-joining algorithm is abandoned.
It was suggested in [Pachter and Speyer, 2004] that an alternative encoding of edge weighted phylogenetic X-trees may be used to improve phylogenetic reconstruction while preserving many of the properties of distance based methods. Let X m denote the mth Cartesian product of X and X m all the m element subsets of X. For a phylogenetic X-tree T with R ⊂ X let [R] denote the smallest subtree of T spanning R.
Theorem 4 ( [Pachter and Speyer, 2004]). Let T be a phylogenetic Xtree (|X| = n) and m ≥ 2 be an integer. Let n ≥ 2m−1, and let D : Instead of reconstructing trees from dissimilarity maps (m = 2), it was suggested that maximum likelihood methods could be used to more accurately estimate the phylogenetic diversity values D(R) [Faith, 1992]  . . , i m ) ∈ S m . The problem is then to develop consistent tree reconstruction algorithms that find a tree whose m-subtree weights are "close" to the m-dissimilarity map.
In this paper we propose a practical, efficient method for tree reconstruction based on m-dissimilarity maps. We begin by refining theorem 4 and show that even if n < 2m − 1 partial information about the tree is recoverable. We then describe a neighbor-joining algorithm whose cherry picking criterion makes use of m-subtree weights. The algorithm is a generalization of standard neighbor-joining (in the special case m = 2 the formulas in the algorithm simplify to neighbor-joining). It also satisfies many of the same properties: the method is consistent, the input order of the taxa does not change the outcome, and the cherry picking criterion is a linear function of the distances. In section 4 we argue that it is more accurate than neighborjoining, and the fact that it is polynomial in the number of taxa means that it is practical for the same kinds of large problems for which neighbor-joining is used. In fact, the running time for m = 3 is O(n 3 ), the same as for standard neighbor-joining (only with a higher time constant for the initial estimation of the weights).
Our main results depends on yet another encoding of phylogenetic Xtrees. Given four leaves i, j, k, l in a phylogenetic X-tree, we use the notation We say that (i, j; k, l) is a tree quartet if |(i, j; k, l)| = ∅. If q(T ) denotes the set of tree quartets then there is a partial order ≤ on all X-trees where Theorem 5 ([Buneman, 1971, Semple andSteel, 2003]). Let T and

Tree metrics from m-weights
Our main results about m-subtree weights are based on a mapping that associates to any m-dissimilarity map a 2-dissimilarity map which, for m-subtree weights from a tree, preserves a certain subforest. This subforest is characterized by containing those edges whose removal results in sufficiently small components in the tree. Specifically, for a tree T , the removal of any edges results in two components, and we denote by T ≤k the subforest of T whose edge set consists of edges whose removal results in one of the components having size at most k. For example T ≤1 consists of all the pendant edges (adjacent to leaves), and T ≤k = T for any k > n−1 2 because the removal of any edge in a tree leaves a component of size at most n−1 2 . For the tree T in figure 1 with 24 leaves, T = T ≤12 .
Theorem 6. Let D be an m-dissimilarity map on a set X of size n and define (1) and v S(a 1 ,a 4 )+S(a 2 ,a 3 ) = v S(a 1 ,a 3 )+S(a 2 ,a 4 ) Figure 2: A quartet (a 1 , a 2 ; a 3 , a 4 )

Proof:
We use the fact that v S(a 1 ,a 2 )+S(a 3 ,a 4 ) = v S(a 1 ,a 2 ) + v S(a 3 ,a 4 ) and apply the previous lemma. We also note that for e / ∈ [{a 1 , a 2 , a 3 , a 4 }], L a 1 (e) = L a i (e) for all i.
Corollary 9 implies that S satisfies the four-point condition (1), although it may be that v S(a 1 a 2 ;a 3 a 4 ) (e) = 0 which means that there are interior edges in T ′ which have been collapsed (with length equal to 0). Suppose, however, that (a 1 a 2 ; a 3 a 4 ) ∈ q(T ) and [{a 1 , a 2 , a 3 , a 4 }] is in a connected component of T ≤n−m (in other words the subtree spanning the quartet consists of edges whose removal leaves a small component). This means that if e ∈ P b 1 b 2 then either L a 1 (e) ≥ m or n − L a 1 (e) ≥ m and so S(a 1 , a 2 ; a 3 , a 4 ) < 0 which means that (a 1 , a 2 ; a 3 , a 4 ) ∈ q(T ′ ). Therefore q(T ′ ) ⊂ q(T ) and it follows in T ′ then where a is a leaf in one component of T − e and c a leaf in the other.
Proof: Since e is an internal edge, we may choose a, b, c and d such that e is the only edge on the splitting path of (a, b; c, d) (figure 3). Then Corollary 11.
Lemma 12. Denote the edges adjacent to the leaves by e 1 , . . . , e n (with corresponding edges in T ′ e ′ 1 , . . . , e ′ n ) and the set of internal (non-pendant) edges Figure 4: The leaf edge e i is incident on two other edges. We may choose leaves a and b such that P ia ∩ P ib = e i .
by int(E(T )). Let and let A be the matrix 2 n−3 m−2 I + n−3 m−3 J. Then The interior vertex of an edge e also adjacent to a leaf i is incident to two other edges. Choose a leaf a such that P ia intersects one of the edges, and b such that P ib intersects the other (figure 4). Then which after some algebra gives the above lemma.
In order to recover w T (e) for every edge, we start by calculating the interior edge weights, after which we can calculate the values C i . The matrix A is always invertible if m ≤ n − 1; however, calculating C i requires that 3 Neighbor-joining with subtree weights Theorem 6 forms the basis of the neighbor-joining algorithm with subtree weights. First, we need a generalization of the neighbor-joining criterion: Theorem 14 (Cherry Picking Theorem). Let T be an edge weighted phylogenetic X-tree with |X| = n let m be an integer satisfying 2 ≤ m ≤ n−1.
Let D : X m → R >0 be the m-dissimilarity map corresponding to the weights of the subtrees of size m in T . If Q D (x, y) is a minimal element of the matrix then x, y is a cherry in the tree T .
Note that when m = 2 this is exactly the neighbor-joining criterion (Qcriterion of theorem 2) as described by [Studier and Keppler, 1988].
. By theorem 6 we know that S is a tree metric. Observe that In other words, Q D (i, j) is just a scalar multiple of the neighbor-joining criterion for the tree metric S. By theorem 2 (m = 2) we know that the minimal element of Q S (i, j) is a cherry in T ′ (the tree corresponding to the tree metric S). Since m ≤ n − 1, we know that T ′ ≤1 is isomorphic to T ≤1 and therefore the minimal element of Q D (i, j) is a cherry.
It follows from theorem 6 that if m ≤ n+1 2 then the neighbor-joining algorithm applied directly to S is topologically consistent, i.e. will reconstruct the correct tree topology starting with the weights of all subtrees of size m.
The fact that there is an invertible linear map between for the edge weights, means that we can reconstruct T , thus leading to a consistent neighbor joining algorithm with subtree weights (algorithm 2).

Results
We have implemented the neighbor-joining algorithm for subtree weights in a program called MJOIN. The implementation incorporates the fastDNAml [Olsen et al., 1994] program for computing the subtree weights, and allows Algorithm 2: Neighbor-joining algorithm with subtree weights Data : A set X together with sequences corresponding to the elements of X Result: Edge weighted phylogenetic X-tree T for R ∈ X m do Estimate D(R) using a (numerical) maximum likelihood method; Apply algorithm 1 (neighbor-joining) to the "distances" S(i, j) resulting in tree T ′ ; Set T = T ′ ; Set w T (e) = ; the user to select the sizes of the subtrees to be used. We tested MJOIN with simulated data on the two parameter family of trees described by [Ota and Li, 2000]. These are trees for which neighbor-joining has difficulty in resolving the correct topology. We simulated 1000 data sets on each of the two tree shapes, T 1 and T 2 (Figures 2, 3) at the three edge length ratios, a/b = 0.01/0.07, 0.02/0.19, and 0.03/0.42. This was repeated twice for sequences of length 500 and 1000BP. We also repeated the runs with the Kimura 2-parameter model and obtained similar results (not shown).  (2) ). For the T1 tree, NJ (4) out-performs even fastDNAml. Figure 4 shows the standard deviation in the m-weights. We believe it is the relative improvement in the m-weight errors that is contributing to the improved performance of MJOIN as m increases. Checking the l ∞ distance of the 2-distance maps from the true tree metric, we find that even in cases where neighbor-joining has a high success rate, the number of distance maps that satisfy Atteson's condition is fewer than 1%. This suggests that the  success of neighbor joining is due to other favorable features of the projection, and we believe that a deeper understanding of neighbor joining is necessary in order to rigorously understand the reasons for the improvements with m-subtree weights. Figure 6: Standard Deviation as a percent of total weight. For the Jukes-Cantor method, sequence length of 500BP, m=2,3,4 and subtrees drawn from T 1 and T 2 .

Discussion
Theorem 6 establishes that pairwise distance based reconstruction methods can be used to reconstruct trees from m-subtree weights. This immediately suggests a number of potential improvements to the algorithm we have described. For example, by taking into account the variances of the S(i, j), it should be possible to improve on the neighbor-joining algorithm for subtree weights with better agglomeration (as is done in BIONJ).
In tests we performed with n = 10 taxa and m = 5 (results not reported) we observed a deterioration in the accuracy of the tree reconstruction algorithm, which we attribute to inaccuracies in the subtree weights estimated with fastDNAml. In fact, tests with fastDNaml on five taxa revealed that the algorithm fails to even reconstruct the correct tree topology a significant fraction of the time. Thus, we believe that until further improvements are made in ML estimation of trees, the best subtree weight size to use will be m = 4. We are encouraged by various efforts in this direction [Contois andLevy, 2005, Hoşten et al., 2005].
We have found subtree weight reconstruction to be practical and efficient for much larger examples than described here. We have run the algorithm with m = 3 on trees of up to 50 taxa on a standard PC, and it is worth noting that for larger problems it is trivial to parallelize the m-weight estimation.
Thus, we believe that our method is practical and recommended for large tree constructions that currently rely on either a pairwise distance method, or a 22 heuristic maximum likelihood search. Since the latter can fail with regularity on trees with only five taxa, it is unlikely to be accurate for large trees.
Our investigations have opened up a number of interesting questions. For example, it would be useful to obtain an analog of the four point condition that characterizes the space of m-dissimilarity maps arising from trees. It would also be of interest to develop a subtree-weight analog of the Neighbor-Net algorithm [Bryant and Moulton, 2004].
Finally, we point out that our results can be viewed as providing approximations to maximum-likelihood tree reconstruction by refining distancebased methods. We believe that a deeper understanding of m-dissimilarity maps should yield further results in this direction.

Acknowledgments
This work was partially funded by an NIH grant (R01HG2362). L.P. was also supported by a Sloan foundation fellowship. D.L. was also supported by NIH grant (GM68423).