# Neighbor Joining And Leaf Status

Mathias Weller

► To cite this version:

Mathias Weller. Neighbor Joining And Leaf Status. 2023. hal-04109091v2

HAL Id: hal-04109091

https://hal.science/hal-04109091v2

Preprint submitted on 30 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Neighbor Joining And Leaf Status

Mathias Weller<fnref n="1" />,<fnref n="2" />

**Correspondence:** mathias.weller@cnrs.fr

## Abstract

The Neighbor Joining Algorithm is among the most fundamental algorithmic results in computational biology. However, its definition and correctness proof are not straightforward. In particular, "the question "what does the NJ method seek to do?" has until recently proved somewhat elusive" [Gascuel & Steel, 2006]. While a rigorous mathematical analysis is now available, it is still considered somewhat hard to follow and its proof tedious at best.

In this work, we present an alternative interpretation of the goal of the Neighbor Joining algorithm by proving that it chooses to merge the two taxa *u* and *v* that maximize the "leaf-status", that is, the sum of distances of all leaves to the unique *u*-*v*-path.

**Keywords:** Neighbor Joining; status in graphs; Phylogenetic Tree Reconstruction

1

2

3

4

5

6

7

8

9

10

11

12

<footnote n="1">¹ TU Berlin, Germany</footnote>

<footnote n="2">² CNRS, LIGM, Université Gustave Eiffel, France</footnote>
# 1 Introduction and Preliminaries

**Neighbor Joining.** Given $n$ taxa, as well as pairwise distances<fnref n="1" /> $d(u, v)$, the Neighbor Joining algorithm finds an undirected edge-weighted tree $T$ whose leaves correspond to the $n$ taxa and such that each two taxa $u$ and $v$ have distance $d(u, v)$ in $T$, provided such a tree exists (the distances are called “additive” in this case). In this work, we call any such $T$ a representation of the distances $d$. To find a representation for the input distances, the Neighbor Joining algorithm finds a pair of taxa that are guaranteed to form a cherry in some representation $T$ of $d$. It then “merges” these two taxa into a new taxon corresponding to the mid-point of the cherry in $T$. Finally, the distances $d$ are updated and a tree representing these new distances is found recursively. See [FF04; Swo+96] for a more thorough explanation and examples for the Neighbor Joining algorithm.

A drawback of the algorithm is that finding a pair of taxa that form a cherry in a representation is a very opaque process, to the point where the technique has been called “obscure” or even “black magic” [CP13]. Efforts to render this important step more comprehensible and intuitive have been conducted [Att97; CHP93; Swo+96; VD91] (see the excellent collection by Bryant [Bry05], indicating why each of them is not fully satisfying). Gascuel and Steel [GS06] concluded that “NJ greedily optimizes a natural tree length estimate” by selecting “at each step as neighbors that pair of current taxa, which most decreases the whole tree length, as computed using the generalized Pauplin formula”. While this is a solid mathematical characterization, the “whole tree length” is hardly intuitive and proving that a pair that most decreases it should form a cherry in a representation of $d$ is lengthy and tedious. Neighbor Joining will produce a tree even for non-additive distances and it has been claimed that the algorithm does not explicitly optimize any criterion in this case [FF04; Gas00; Swo+96].

In this work, we follow a similar path as Vach and Degens [VD91], giving a simple and intuitive reformulation of the pair-selection criterion that allows easy verification of correctness for additive distances and hopefully helps teach this important algorithm in class. Indeed, it turns out that taxa $u$ and $v$ are selected to be merged if their hypothetical parent is furthest from the center of the representing tree, more precisely, it has maximum “leaf-status” (see below).

Let us have a closer look at the process of selecting taxa to be merged by the Neighbor Joining algorithm. From the distances $d(u, v)$, new quantities $q(u, v)$ are computed as follows.

$$q(u, v) := (n-2) \cdot d(u, v) - \sum_x d(u, x) - \sum_x d(v, x) \quad (1)$$

Then, the pair $(u, v)$ minimizing $q(u, v)$ is selected to be merged. Correctness is established by Studier and Keppler [SK88], who showed that this formulation is equivalent to the one used by Saitou and Nei [SN87]. Indeed, leaves $u$ and $v$ minimizing $q(u, v)$ form a cherry in the sought tree representing the distances $d$ [Att97; EL09].

**Theorem 1** (“Neighbor Joining Theorem”). Let $D$ be a distance matrix representable by a tree and let $u$ and $v$ be such that $q(u, v)$, as defined in (1), is minimum. Then, there is a tree $T$ representing $D$ in which $(u, v)$ is a cherry.

**Trees, Status and Leaf-Status.** Let $T$ be an undirected tree. We denote its nodes by $V(T)$, its edges by $E(T)$ and its leaves (nodes with degree one) by $L(T)$. Two leaves $u, v \in L(T)$ are said to form a cherry in $T$ if they are adjacent to the same node $x$ and $x$ is called the mid-point of the cherry. In this work, we will consider trees $T$ that do not contain nodes of degree two. Let the edges of $T$ be weighted by a function $\omega: E(T) \to \mathbb{N}^+$. The distance $d_T(u, v)$ between nodes $u, v \in V(T)$ is the weight of the unique $u-v$-path in $T$. For a $u-v$-path $p$ in $T$, we define the distance of a node $x$ to $p$ as the smallest distance of $x$ to any node on $p$, that is, $d_T(x, p) := \min_{u \in V(p)} d(u, x)$.

**Observation 1.** Let $u, v, x \in V(T)$. The distance of $x$ to the $u-v$-path $p$ is $d_T(x, p) = 1/2 (d(x, u) + d(x, v) - d(u, v))$.

<footnote n="1">¹The distances between taxa can be obtained in a variety of ways, for example by comparing their genomes.</footnote>
For any edge uv of T let $L_u^{uv}$ denote the set of leaves $x$ that are closer to $u$ than to $v$ in T, that is, $L_u^{uv} := \{x \in L(T) | d_T(x, u) < d_T(x, v)\}$. The status of $u \in V(T)$ in T is the sum of all distances from $u$, that is, $s_T(u) := \sum_{x \in V(T)} d(u, x)$. While the status has been researched in the past [EJS76; Lin+12; LS09; QZ20; SL11], we require a slight variation of the concept: The leaf-status of $u \in V(T)$ in T is the sum of distances of $u$ to all leaves, that is, $\ell_T(u) := \sum_{x \in L(T)} d(u, x)$. The leaf-status of a path $p$ of T is the sum of distances of all leaves to $p$, that is, $\ell_T(p) := \sum_{x \in L(T)} d(x, p)$. With Observation 1, we observe that the leaf-status of a path can be formulated in terms of the leaf-statuses of its endpoints. Note how closely this formulation resembles Equation (1).

**Observation 2.** Let $u, v \in V(T)$ and let $p$ be a u-v-path in T. Then, $\ell_T(p) = \frac{1}{2}(\ell_T(u) + \ell_T(v) - |L(T)| \cdot d(u, v))$.

In the following, we will omit the subscript if T is clear from the context.

**Working with Leaf-Statuses.** As a warm-up, we prove a version<fnref n="2" /> of [EJS76, Property 2.2] for the leaf-status.

**Lemma 1.** Let $uv \in E(T)$. Then, $\ell(u) - \ell(v) = \omega(uv) (|L_v^{uv}| - |L_u^{uv}|)$.

$$ \textbf{Proof.} \qquad \begin{aligned} \ell(u) &= \sum_{a \in L_u^{uv}} d(a, u) + \sum_{b \in L_u^{uv}} d(b, u) \\ &= \sum_{a \in L_u^{uv}} (d(a, u) + \omega(uv) - \omega(uv)) + \sum_{b \in L_u^{uv}} (d(b, u) - \omega(uv) + \omega(uv)) \\ &= \sum_{a \in L_u^{uv}} (d(a, v) - \omega(uv)) + \sum_{b \in L_u^{uv}} (d(b, v) + \omega(uv)) = \ell(v) + \omega(uv)(|L_v^{uv}| - |L_u^{uv}|) \quad \square \end{aligned} $$

**Corollary 1.** Let T be a tree with at least three leaves and let $x \in V(T)$ minimize $\ell(x)$. Then, $x$ is not a leaf.

A central theorem concerning the status is that, for any path $(v_0, v_1, \dots, v_k)$ in T originating in a node $v_0$ of minimum status in T, we have $s(v_0) \le s(v_1) < s(v_2) < \dots < s(v_k)$ [EJS76, Theorem 3.3]. Using Lemma 1, we show a similar version for the leaf-status of T even when edges are positively weighted.

**Lemma 2.** Let T be a tree with edge-weights $\omega: E(T) \to \mathbb{N}^+$ that is free of degree-2 nodes. Let $(v_0, v_1, \dots, v_k)$ be a path in T and let $v_0$ have minimum leaf-status in T. Then, $\ell(v_0) \le \ell(v_1) < \ell(v_2) < \dots < \ell(v_k)$.

**Proof.** For all $i$, we abbreviate $L_i^{\leftarrow} := L_{v_i}^{v_i v_{i+1}}$, that is, $L_i^{\leftarrow}$ is the set of leaves that are closer to $v_i$ than to $v_{i+1}$, and $L_i^{\rightarrow} := L_{v_{i+1}}^{v_i v_{i+1}}$. Note that, as T is a tree without degree-2 nodes, we have $L_i^{\leftarrow} \subset L_{i+1}^{\leftarrow}$ and $L_i^{\rightarrow} \supset L_{i+1}^{\rightarrow}$, implying $|L_i^{\leftarrow}| < |L_{i+1}^{\leftarrow}|$ and $|L_i^{\rightarrow}| > |L_{i+1}^{\rightarrow}|$. Further, for all $i$, as $\omega(v_iv_{i+1}) > 0$, we have

$$ \ell(v_i) \le \ell(v_{i+1}) \quad \text{Lemma 1} \quad |L_i^{\leftarrow}| \ge |L_i^{\rightarrow}| \quad \text{and} \quad \ell(v_i) = \ell(v_{i+1}) \quad \text{Lemma 1} \quad |L_i^{\leftarrow}| = |L_i^{\rightarrow}| \quad (2) $$

We prove the lemma by induction on $i$. For $i = 0$, $\ell(v_i) \le \ell(v_{i+1})$ by definition of $v_0$. Otherwise, $\ell(v_{i-1}) \le \ell(v_i)$ by induction hypothesis, implying $|L_i^{\leftarrow}| > |L_{i-1}^{\leftarrow}| \ge |L_{i-1}^{\rightarrow}| > |L_i^{\rightarrow}|$ by (2). But then, $\ell(v_i) < \ell(v_{i+1})$ by (2). □

Lemma 2 implies that, in analogy to the status, the nodes $v$ minimizing the leaf-status are "in the center" of T and that $\ell(v)$ is a measure of "elongation from the center" of T.

## 2 Results

Instead of minimizing the "ominous" values $q(u, v)$, we propose to maximize the leaf-status of the u-v-path $p$ in the target tree T, augmented by the length $d(u, v)$ of $p$:

$$ z(u, v) := d(u, v) + \ell(p) = d(u, v) + \sum_{x \in L(T)} d(x, p) \quad \text{Observation 1} \quad d(u, v) + \frac{1}{2} \sum_{x \in L(T)} (d(u, x) + d(v, x) - d(u, v)) \quad (3) $$

Indeed, $q(u, v) = -2z(u, v)$ can be easily verified for all taxa $u$ and $v$ and, thus, maximizing $z(u, v)$ is equivalent to minimizing $q(u, v)$. The following key property connects $z(u, v)$ to the leaf-status in a representation T for $d$.

<footnote n="2">²The original property is proved for the status in unweighted graphs, while ours is for the leaf-status in edge-weighted trees.</footnote>
**Lemma 3.** Let $T$ be a tree with positive edge-weights without degree-2 nodes and let $u, v \in L(T)$. Let $w$ be an inner node of the unique $u-v$-path $p$ in $T$. Then, $z(u, v) \le \ell(w)$ and equality holds if and only if $p = (u, w, v)$.

*Proof.* By definition, for all $x \in L(T)$, we have $d(x, p) \le d(x, w)$ and, as $T$ is free of degree-2 nodes and its edge-weights are positive, equality holds if and only if the $x-w$-path avoids all edges of $p$. Since $d(u, v) = d(u, w) + d(w, v)$, we conclude

$$z(u, v) \stackrel{(3)}{=} d(u, v) + \sum_{x \in L(T)} d(x, p) = d(u, v) + \sum_{x \in L(T) \setminus \{u, v\}} d(x, p) \le d(u, w) + d(v, w) + \sum_{x \in L(T) \setminus \{u, v\}} d(x, w) = \sum_{x \in L(T)} d(x, w) = \ell(w),$$

and equality holds if and only if all paths from leaves $x \in L(T) \setminus \{u, v\}$ to $w$ are edge-disjoint to $p$ or, equivalently, all edges in $p$ are incident with either $u$ or $v$, that is, $p = (u, w, v)$. □

As the main contribution, the following theorem establishes the connection of $z(u, v)$ to the leaf-status, thereby giving a simple, intuitive explanation of the correctness of the Neighbor Joining algorithm: it merges leaves $u$ and $v$ that, in each representation $T$ for $d$, form a cherry whose mid-point has maximum leaf-status and, by Lemma 2, maximum elongation from the center of $T$.

**Theorem 2.** Let $d$ be distances for at least three taxa, representable by a tree $T$ and let $u, v \in L(T)$ such that $z(u, v)$ is maximum. Then, $u$ and $v$ form a cherry in $T$ and $\ell(w) = z(u, v)$ for its mid-point $w$.

*Proof.* Assume towards a contradiction that $u$ and $v$ do not form a cherry in $T$. Let $c$ be a node of minimum leaf-status in $T$ and let $p$ be the unique $c-u$-path in $T$. By Corollary 1, $c$ is not a leaf and the predecessor $x$ of $u$ in $p$ is not a leaf either.

By Lemma 3 and the assumption that $u$ and $v$ are not a cherry, $z(u, v) < \ell(x)$. Since $x$ does not have degree two in $T$, we know that $x$ has distinct neighbors $s$ and $t$, none of which is $u$ or $v$. Without loss of generality, let $\ell(s) \ge \ell(t)$. If $s$ is a leaf in $T$, then $z(u, s) = \ell(x) > z(u, v)$ by Lemma 3, contradicting maximality of $z(u, v)$. Thus, suppose that $s$ is not a leaf in $T$. Clearly, Lemma 2 forbids $\ell(s)$, $\ell(t) \le \ell(x)$ and, thus, $\ell(s) > \ell(x)$. Of the two connected components of the result of removing the edge $xs$ from $T$, let $T_s$ be the one containing $s$. Note that (a) $u, c \notin V(T_s)$ and (b) $\ell(y) > \ell(x)$ for all $y \in V(T_s)$ by Lemma 2. Since $s$ is not a leaf in $T$, there is a cherry in $T_s$ that is also a cherry in $T$ and, by Lemma 3, this cherry contradicts maximality of $z(u, v)$. Thus, $u$ and $v$ form a cherry in $T$ and, by Lemma 3, $\ell(x) = z(u, v)$. □

# 3 Conclusion and Discussion

We presented a new, intuitive point of view onto the well-known Neighbor Joining algorithm. We show that finding the minimum in a matrix of "obscure" entries can be interpreted as finding the internal node $w$ maximizing the "leaf-status", that is, the sum of distances to $w$ in the target tree $T$. While the proof of the Neighbor Joining Theorem is usually skipped in class due to its complexity, our simplified explanation and proof can be taught to undergraduate students with reasonable effort.

The proof that we present here relies on the edge-weights in the target tree $T$ being positive. Indeed, upon closer inspection, the proof only requires the edge-weights of all internal edges of $T$ to be positive. Thus, our results are applicable to a modification of the Neighbor Joining algorithm that constructs the result of contracting all weight-zero edges between internal nodes of $T$. One can realize that, in presence of zero-weight internal edges in $T$, the Neighbor Joining algorithm returns an arbitrary binary tree $T'$ such that contracting all zero-weight internal edges in $T$ and in $T'$ results in the same tree.

# Funding

The author received no external funding.
**Conflict of Interest Disclosure**

The author declares no conflict of interest.

**Data, script, code, and supplementary information availability**

Not applicable.

**References**

[Att97] Atteson K. The performance of the neighbor-joining method of phylogeny reconstruction. *Mathematical hierarchies and biology*. DIMACS Series of Discrete Mathematics and Theoretical Computer Science 37 (1997), 133–147.

[Bry05] Bryant D. On the uniqueness of the selection criterion in neighbor-joining. *Journal of Classification* 22 (2005), 3–15.

[CHP93] Charleston MA, Hendy MD, and Penny D. Neighbor-Joining Uses the Optimal Weight for Net Divergence. *Molecular Phylogenetics and Evolution* 2 (1993), 6–12. ISSN: 1055-7903.

[CP13] Compeau P and Pevzner P. *Bioinformatics Algorithms: An Active Learning Approach – The Neighbor-Joining Algorithm*. Youtube. 2013. URL: https://youtu.be/Y0QWFFWQzds?t=118.

[EJS76] Entringer RC, Jackson DE, and Snyder D. Distance in graphs. *Czechoslovak Mathematical Journal* 26 (1976), 283–296.

[EL09] Elias I and Lagergren J. Fast neighbor joining. *Theoretical Computer Science* 410 (2009), 1993–2000. ISSN: 0304-3975. https://doi.org/https://doi.org/10.1016/j.tcs.2008.12.040.

[FF04] Felsenstein J and Felsenstein J. *Inferring phylogenies*. Vol. 2. Sinauer associates Sunderland, MA, 2004.

[Gas00] Gascuel O. Data model and classification by trees: the minimum variance reduction (MVR) method. *Journal of classification* 17 (2000), 67–99.

[GS06] Gascuel O and Steel M. Neighbor-Joining Revealed. *Molecular Biology and Evolution* 23 (July 2006), 1997–2000. ISSN: 0737-4038.

[Lin+12] Lin C, Tsai WH, Shang JL, and Zhang YJ. Minimum statuses of connected graphs with fixed maximum degree and order. *Journal of combinatorial optimization* 24 (2012), 147–161.

[LS09] Lin C and Shang JL. Statuses and branch-weights of weighted trees. *Czechoslovak mathematical journal* 59 (2009), 1019.

[QZ20] Qiao P and Zhan X. Pairs of a tree and a nontree graph with the same status sequence. *Discrete Mathematics* 343 (2020), 111662.

[SK88] Studier JA and Keppler KJ. A note on the neighbor-joining algorithm of Saitou and Nei. *Molecular Biology and Evolution* 5 (Nov. 1988), 729–731. ISSN: 0737-4038. https://doi.org/10.1093/oxfordjournals.molbev.a040527.

[SL11] Shang JL and Lin C. Spiders are status unique in trees. *Discrete Mathematics* 311 (2011), 785–791. ISSN: 0012-365X.

[SN87] Saitou N and Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. *Molecular Biology and Evolution* 4 (July 1987), 406–425. ISSN: 0737-4038.

[Swo+96] Swofford D, Olsen G, Waddell P, and Hillis D. Phylogenetic Inference. In: *Molecular Systematics*. 2nd. Sinauer Associates, 1996, pp. 407–514.

[VD91] Vach W and Degens P. Least-squares approximation of additive trees to dissimilarities-characterizations and algorithms. *Computational Statistics Quarterly* 3 (1991), 203–218.