Editing Neighbor joining

{{short description|Bottom-up clustering method for creating phylogenetic trees}}
In [[bioinformatics]], '''neighbor joining''' is a bottom-up (agglomerative) [[Cluster analysis|clustering]] method for the creation of [[phylogenetic trees]], created by Naruya Saitou and [[Masatoshi Nei]] in 1987.<ref>{{Cite journal|title=The neighbor-joining method: a new method for reconstructing phylogenetic trees.|first1=N.|last1=Saitou|first2=M.|last2=Nei|date=1 July 1987|journal=Molecular Biology and Evolution|volume=4|issue=4|pages=406–425|doi=10.1093/oxfordjournals.molbev.a040454|pmid=3447015|doi-access=free}}</ref> Usually based on [[DNA]] or [[protein]] [[primary structure|sequence]] data, the algorithm requires knowledge of the distance between each pair of [[taxa]] (e.g., species or sequences) to create the phylogenetic tree.<ref>
{{cite book
 | title = Bacterial Population Genetics in Infectious Disease
 |editor1=D. Ashley Robinson |editor2=Daniel Falush |editor3=Edward J. Feil | chapter = Sequence-Based Analysis of Bacterial Population Structures
 | author = Xavier Didelot
 | publisher = John Wiley and Sons
 | year = 2010
 | isbn = 978-0-470-42474-2
 | pages = 46–47
 | chapter-url = https://books.google.com/books?id=gPVjfsWnGCcC&pg=PA46
 }}</ref>

== The algorithm ==
[[File:Neighbor joining 7 taxa start to finish diagram.svg|thumb|right|400px|Starting with a star tree (A), the Q matrix is calculated and used to choose a pair of nodes for joining, in this case f and g. These are joined to a newly created node, u, as shown in (B). The part of the tree shown as solid lines is now fixed and will not be changed in subsequent joining steps. The distances from node u to the nodes a-e are computed from equation ({{EquationNote|3}}). This process is then repeated, using a matrix of just the distances between the nodes, a,b,c,d,e, and u, and a Q matrix derived from it. In this case u and e are joined to the newly created v, as shown in (C). Two more iterations lead first to (D), and then to (E), at which point the algorithm is done, as the tree is fully resolved.]]
Neighbor joining takes a [[distance matrix]], which specifies the distance between each pair of [[taxon|taxa]], as input.
The algorithm starts with a completely unresolved tree, whose topology corresponds to that of a [[star network]], and iterates over the following steps, until the tree is completely resolved, and all branch lengths are known:

# Based on the current distance matrix, calculate a matrix <math>Q</math> (defined below).
# Find the pair of distinct taxa i and j (i.e. with <math>i \neq j</math>) for which <math>Q(i,j)</math> is smallest. Make a new node that joins the taxa i and j, and connect the new node to the central node. For example, in part (B) of the figure at right, node u is created to join f and g.
# Calculate the distance from each of the taxa in the pair to this new node.
# Calculate the distance from each of the taxa outside of this pair to the new node.
# Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.

=== The Q-matrix ===
Based on a distance matrix relating the <math>n</math> taxa, calculate the <math>n</math> x <math>n</math> matrix <math>Q</math> as follows:

{{NumBlk|:| <math>Q(i,j)=(n-2)d(i,j)-\sum_{k=1}^n d(i,k) - \sum_{k=1}^n d(j,k)</math>|{{EquationRef|1}}}}

where <math>d(i,j)</math> is the distance between taxa <math>i</math> and <math>j</math>.

=== Distance from the pair members to the new node ===
For each of the taxa in the pair being joined, use the following formula to calculate the distance to the new node:

{{NumBlk|:| <math>\delta(f,u)=\frac{1}{2}d(f,g)+\frac{1}{2(n-2)} \left [ \sum_{k=1}^n d(f,k) - \sum_{k=1}^n d(g,k) \right ] \quad </math> |{{EquationRef|2}}}}
and:
: <math>\delta(g,u)=d(f,g)-\delta(f,u) \quad </math>

Taxa <math>f</math> and <math>g</math> are the paired taxa and <math>u</math> is the newly created node. The branches joining <math>f</math> and <math>u</math> and <math>g</math> and <math>u</math>, and their lengths, <math>\delta(f,u)</math> and <math>\delta(g,u)</math> are part of the tree which is gradually being created; they neither affect nor are affected by later neighbor-joining steps.

=== Distance of the other taxa from the new node ===
For each taxon not considered in the previous step, we calculate the distance to the new node as follows:

{{NumBlk|:|  <math>d(u,k)=\frac{1}{2} [d(f,k)+d(g,k)-d(f,g)]</math> |{{EquationRef|3}}}}

where <math>u</math> is the new node, <math>k</math> is the node which we want to calculate the distance to and <math>f</math> and <math>g</math> are the members of the pair just joined.

=== Complexity ===
Neighbor joining on a set of  <math>n</math> taxa requires <math>n-3</math> iterations.  At each step one has to build and search a <math>Q</math> matrix. Initially the <math>Q</math> matrix is size <math>n\times n</math>, then the next step it is <math>(n-1)\times(n-1)</math>, etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of <math>O(n^3)</math>;<ref>{{Cite journal|date=November 1988|title=A note on the neighbor-joining algorithm of Saitou and Nei.|url=https://academic.oup.com/mbe/article/5/6/729/1044339/A-note-on-the-neighborjoining-algorithm-of-Saitou|journal=Molecular Biology and Evolution|language=en|doi=10.1093/oxfordjournals.molbev.a040527|pmid=3221794|issn=1537-1719|last1=Studier|first1=J. A.|last2=Keppler|first2=K. J.|volume=5|issue=6|pages=729–31|doi-access=free}}</ref> implementations exist which use heuristics to do much better than this on average.<ref>{{Cite journal|last1=Mailund|first1=Thomas|last2=Brodal|first2=GerthS|last3=Fagerberg|first3=Rolf|last4=Pedersen|first4=ChristianNS|last5=Phillips|first5=Derek|date=2006|title=Recrafting the neighbor-joining method|url= |journal=BMC Bioinformatics|volume=7|issue=1|pages=29|doi=10.1186/1471-2105-7-29|pmc=3271233|pmid=16423304 |doi-access=free }}</ref>

== Example ==
[[File:Constructing phylogenetic tree using neighbor-joining 5 taxa improved.svg|thumb|right|360px|Neighbor joining with 5 taxa. In this case 2 neighbor joining steps give a tree with fully resolved topology. The branches of the resulting tree are labeled with their lengths.]]{{anchor|NJ_with_5_taxa}}
Let us assume that we have five taxa <math>(a,b,c,d,e)</math> and the following distance matrix <math>D</math>:

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | a
! style="width: 20px;" | b
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! a
| 0
| 5
| 9
| 9
| 8
|-
! b
| 5
| 0
| 10
| 10
| 9
|-
! c
| 9
| 10
| 0
| 8
| 7
|-
! d
| 9
| 10
| 8
| 0
| 3
|-
! e
| 8
| 9
| 7
| 3
| 0
|}

=== First step ===
====First joining====
We calculate the <math>Q_1</math> values by equation ({{EquationNote|1}}). For example:
:<math>Q_1(a,b) = (n-2)d(a,b) - \sum_{k=1}^5 d(a,k) - \sum_{k=1}^5 d(b,k)</math>
:<math>= (5-2) \times 5 - (5+9+9+8) - (5+10+10+9) = 15-31-34 = -50</math>

We obtain the following values for the <math>Q_1</math> matrix (the diagonal elements of the matrix are not used and are
omitted here):

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | a
! style="width: 20px;" | b
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! a
| 
| style=background:#ffffcc; | &minus;50
| &minus;38
| &minus;34
| &minus;34
|-
! b
| style=background:#ffffcc; | &minus;50
| 
| &minus;38
| &minus;34
| &minus;34
|-
! c
| &minus;38
| &minus;38
| 
| &minus;40
| &minus;40
|-
! d
| &minus;34
| &minus;34
| &minus;40
| 
| &minus;48
|-
! e
| &minus;34
| &minus;34
| &minus;40
| &minus;48
| 
|-
|}

In the example above, <math>Q_1(a,b)=-50</math>. This is the smallest value of <math>Q_1</math>, so we join elements <math>a</math> and <math>b</math>.

====First branch length estimation====
Let <math>u</math> denote the new node. By equation ({{EquationNote|2}}), above, the branches joining  <math>a</math> and <math>b</math> to <math>u</math> then have lengths:

:<math>\delta(a,u)=\frac{1}{2}d(a,b)+\frac{1}{2(5-2)} \left [ \sum_{k=1}^5 d(a,k) - \sum_{k=1}^5 d(b,k) \right ] \quad =\frac{5}{2} + \frac{31-34}{6} = 2</math>
:<math>\delta(b,u)=d(a,b)-\delta(a,u) \quad = 5-2 = 3</math>

====First distance matrix update====
We then proceed to update the initial distance matrix <math>D</math> into a new distance matrix <math>D_1</math> (see below), reduced in size by one row and one column because of the joining of <math>a</math> with <math>b</math> into their neighbor <math>u</math>. Using equation ({{EquationNote|3}}) above, we compute the distance from <math>u</math> to each of the other nodes besides <math>a</math> and <math>b</math>. In this case, we obtain:

:<math>d(u,c)=\frac{1}{2} [d(a,c)+d(b,c)-d(a,b)] = \frac{9+10-5}{2} = 7</math>
:<math>d(u,d)=\frac{1}{2} [d(a,d)+d(b,d)-d(a,b)] = \frac{9+10-5}{2} = 7</math>
:<math>d(u,e)=\frac{1}{2} [d(a,e)+d(b,e)-d(a,b)] = \frac{8+9-5}{2} = 6</math>

The resulting distance matrix <math>D_1</math> is:

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | u
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! u
| 0
| '''7'''
| '''7'''
| '''6'''
|-
! c
| '''7'''
| 0
| ''8''
| ''7''
|-
! d
| '''7'''
| ''8''
| 0
| ''3''
|-
! e
| '''6'''
| ''7''
| ''3''
| 0
|-
|}

Bold values in <math>D_1</math> correspond to the newly calculated distances, whereas italicized values are not affected by the matrix update as they correspond to distances between elements not involved in the first joining of taxa.

=== Second step ===
====Second joining====
The corresponding <math>Q_2</math> matrix is:

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | u
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! u
| 
| style=background:#ffffcc; | &minus;28
| &minus;24
| &minus;24
|-
! c
| style=background:#ffffcc; | &minus;28
| 
| &minus;24
| &minus;24
|-
! d
| &minus;24
| &minus;24
| 
| style=background:#ffffcc; | &minus;28
|-
! e
| &minus;24
| &minus;24
| style=background:#ffffcc; | &minus;28
| 
|-
|}

We may choose either to join <math>u</math> and <math>c</math>, or to join <math>d</math> and <math>e</math>; both pairs have the minimal <math>Q_2</math> value of <math>-28</math>, and either choice leads to the same result. For concreteness, let us join <math>u</math> and <math>c</math> and call the new node <math>v</math>.

====Second branch length estimation====
The lengths of the branches joining  <math>u</math> and <math>c</math> to <math>v</math> can be calculated:

:<math>\delta(u,v)=\frac{1}{2}d(u,c)+\frac{1}{2(4-2)} \left [ \sum_{k=1}^4 d(u,k) - \sum_{k=1}^4 d(c,k) \right ] \quad =\frac{7}{2} + \frac{20-22}{4} = 3</math>
:<math>\delta(c,v)=d(u,c)-\delta(u,v) \quad = 7-3 = 4</math>

The joining of the elements and the branch length calculation help drawing the neighbor joining tree [[#NJ_with_5_taxa|as shown in the figure]].

====Second distance matrix update====
The updated distance matrix <math>D_2</math> for the remaining 3 nodes, <math>v</math>, <math>d</math>, and <math>e</math>, is now computed:

:<math>d(v,d)=\frac{1}{2} [d(u,d)+d(c,d)-d(u,c)] = \frac{7+8-7}{2} = 4</math>
:<math>d(v,e)=\frac{1}{2} [d(u,e)+d(c,e)-d(u,c)] = \frac{6+7-7}{2} = 3</math>

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | v
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! v
| 0
| '''4'''
| '''3'''
|-
! d
| '''4'''
| 0
| ''3''
|-
! e
| '''3'''
| ''3''
| 0
|-
|}

=== Final step ===
The tree topology is fully resolved at this point. However, for clarity, we can calculate the <math>Q_3</math> matrix. For example:

:<math>Q_3(v,e) = (3-2)d(v,e) - \sum_{k=1}^3 d(v,k) - \sum_{k=1}^3 d(e,k) = 3-7-6  = -10</math>

{| class="wikitable" style="text-align: center"
|-
! style="width: 20px;" | 
! style="width: 20px;" | v
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! v
| 
| style=background:#ffffcc; | &minus;10
| style=background:#ffffcc; | &minus;10
|-
! d
| style=background:#ffffcc; | &minus;10
| 
| style=background:#ffffcc; | &minus;10
|-
! e
| style=background:#ffffcc; | &minus;10
| style=background:#ffffcc; | &minus;10
| 
|-
|}

For concreteness, let us join <math>v</math> and <math>d</math> and call the last node <math>w</math>. The lengths of the three remaining branches can be calculated:

:<math>\delta(v,w)=\frac{1}{2}d(v,d)+\frac{1}{2(3-2)} \left [ \sum_{k=1}^3 d(v,k) - \sum_{k=1}^3 d(d,k) \right ] \quad =\frac{4}{2} + \frac{7-7}{2} = 2</math>
:<math>\delta(w,d)=d(v,d)-\delta(v,w) = 4-2 = 2</math>
:<math>\delta(w,e)=d(v,e)-\delta(v,w) = 3-2 = 1</math>

The neighbor joining tree is now complete, [[#NJ_with_5_taxa|as shown in the figure]].

=== Conclusion: additive distances ===
This example represents an idealized case: note that if we move from any taxon to any other along the branches of the tree, and sum the lengths of the branches traversed, 
the result is equal to the distance between those taxa in the input distance matrix. For example, going from <math>d</math> to <math>b</math> we have <math>2+2+3+3=10</math>. A distance matrix whose distances agree in this way with some tree is said to be 'additive', a property which is rare in practice. Nonetheless it is important to note that, given an additive distance matrix as input, neighbor joining is guaranteed to find the tree whose distances between taxa agree with it.

== Neighbor joining as minimum evolution ==
Neighbor joining may be viewed as a [[greedy algorithm|greedy heuristic]] for the [[minimum evolution|balanced minimum evolution]]<ref name="gascuel">{{cite journal |author=Gascuel O, [[Mike Steel (mathematician)|Steel M]] |title=Neighbor-joining revealed |journal=Mol Biol Evol |volume=23 |issue=11 |pages=1997–2000 |year=2006 |doi=10.1093/molbev/msl072 |pmid=16877499|url=https://hal-lirmm.ccsd.cnrs.fr/lirmm-00136653/document |doi-access=free }}</ref> (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. NJ at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure does not guarantee to find the optimum for the BME criterion, although it often does and is usually quite close.<ref name="gascuel"/>

== Advantages and disadvantages ==

The main virtue of NJ is that it is fast{{r|Kuhner1994|page1=466}} as compared to [[Computational phylogenetics#Fitch-Margoliash method|least squares]], [[maximum parsimony]] and [[Computational phylogenetics#Maximum likelihood|maximum likelihood]] methods.<ref name="Kuhner1994">{{Cite journal|last1=Kuhner|first1=M. K.|last2=Felsenstein|first2=J.|date=1994-05-01|title=A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates.|journal=Molecular Biology and Evolution|language=en|volume=11|issue=3|pages=459–468|issn=0737-4038|pmid=8015439|doi=10.1093/oxfordjournals.molbev.a040126|doi-access=free}}</ref>
This makes it practical for analyzing large data sets (hundreds or thousands of taxa) and for [[bootstrapping (statistics)|bootstrapping]], for which purposes other means of analysis (e.g. [[maximum parsimony]], [[maximum likelihood]]) may be [[computation]]ally prohibitive.

Neighbor joining has the property that if the input distance matrix is correct, then the output tree will be correct.
Furthermore, the correctness of the output tree topology is guaranteed as long as the distance matrix is 'nearly additive', specifically if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree.<ref>Atteson K (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp.&nbsp;101&ndash;110. ''In'' Jiang, T., and Lee, D., eds., ''Lecture Notes in Computer Science, 1276'', Springer-Verlag, Berlin. COCOON '97.</ref>
In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway.<ref name="levy">{{cite journal |author=Mihaescu R, Levy D, [[Lior Pachter|Pachter L]] |title=Why neighbor-joining works |journal=Algorithmica |volume=54 |issue=1| pages=1–24 |year=2009 | doi=10.1007/s00453-007-9116-4|arxiv=cs/0602041 |s2cid=2462145 }}</ref> The correctness of neighbor joining for nearly additive distance matrices implies that it is [[statistical consistency|statistically consistent]] under many models of evolution; given data of sufficient length, neighbor joining will reconstruct the true tree with high probability.
Compared with [[UPGMA]] and [[WPGMA]], neighbor joining has the advantage that it does not assume all lineages evolve at the same rate ([[molecular clock hypothesis]]). 
 
Nevertheless, neighbor joining has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions.{{citation needed|date=November 2012}} Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.

==Implementations and variants==
There are many programs available implementing neighbor joining. Among implementations of ''canonical'' NJ (i.e. using the classical NJ optimisation criteria, therefore giving the same results), RapidNJ (started 2003, major update in 2011, still updated in 2023)<ref>{{cite web |title=RapidNJ |url=http://birc.au.dk/Software/RapidNJ/ |website=birc.au.dk |language=en}}</ref> and NINJA (started 2009, last update 2013)<ref>{{cite web |title=NINJA: a tool for large-scale neighbor-joining phylogeny inference - Home |url=http://wheelerlab.org/software/ninja/index.html |website=wheelerlab.org}}</ref> are considered state-of-the-art. They have  typical run times proportional to approximately the square of the number of taxa.

Variants that deviate from canonical include:
* BIONJ (1997)<ref>{{cite web |title=ATGC: BioNJ |url=http://www.atgc-montpellier.fr/bionj/ |website=www.atgc-montpellier.fr}}</ref> and Weighbor (2000),<ref>{{cite web |title=WEIGHBOR Homepage |url=http://www.t6.lanl.gov/billb/weighbor/ |date=5 March 2015|archive-url=https://web.archive.org/web/20150305041147/http://www.t6.lanl.gov/billb/weighbor/ |archive-date=2015-03-05 }}</ref> improving on the accuracy by making use of the fact that the shorter distances in the distance matrix are generally better known than the longer distances. The two methods have been extended to run on incomplete distance matrices.<ref>{{cite journal |last1=Criscuolo |first1=Alexis |last2=Gascuel |first2=Olivier |title=Fast NJ-like algorithms to deal with incomplete distance matrices |journal=BMC Bioinformatics |date=December 2008 |volume=9 |issue=1 |page=166 |doi=10.1186/1471-2105-9-166 |pmid=18366787 |pmc=2335114 |doi-access=free }}</ref>
* "Fast NJ" remembers the best node and is O(n^2) always; "relax NJ" performs a hill-climbing search and retains the worst-case complexity of O(n^3). Rapid NJ is faster than plain relaxed NJ.<ref>{{cite book |last1=Simonsen |first1=Martin |last2=Mailund |first2=Thomas |last3=Pedersen |first3=Christian N. S. |chapter=Rapid Neighbour-Joining |title=Algorithms in Bioinformatics |series=Lecture Notes in Computer Science |date=2008 |volume=5251 |pages=113–122 |doi=10.1007/978-3-540-87361-7_10 |isbn=978-3-540-87360-0 |chapter-url=https://users-birc.au.dk/cstorm/software/rapidnj/papers/SimonsenOthers2008_WABI.pdf}}</ref>
* FastME is an implementation of the closely related ''balanced [[minimum evolution]]'' (BME) method (see {{section link||Neighbor joining as minimum evolution}}). It is about as fast as and more accurate than NJ. It starts with a rough tree then improves it using a set of topological moves such as Nearest Neighbor Interchanges (NNI).<ref>{{cite web |title=ATGC: FastME |url=http://www.atgc-montpellier.fr/fastme/ |website=www.atgc-montpellier.fr}}</ref> FastTree is a related method. It works on sequence "profiles" instead of a matrix. It starts with an approximately NJ tree, rearranges it into BME, then rearranges it into approximate maximum-likelihood.<ref>{{cite web |title=FastTree 2.1: Approximately-Maximum-Likelihood Trees for Large Alignments |url=http://www.microbesonline.org/fasttree/ |website=www.microbesonline.org}}</ref>

==See also==
*[[Nearest neighbor search]]
*[[UPGMA]] and [[WPGMA]]
*[[Minimum Evolution]]

== References ==
{{Reflist}}

===Other sources===
{{refbegin}}
* {{cite journal |vauthors=Studier JA, Keppler KJ |title=A note on the Neighbor-Joining algorithm of Saitou and Nei |journal=Mol Biol Evol |volume=5 |issue=6 |pages=729–731 |year=1988 |pmid=3221794 |doi=10.1093/oxfordjournals.molbev.a040527 |doi-access=free }}
* {{cite book |author1=Martin Simonsen |author2=Thomas Mailund |author3=Christian N. S. Pedersen |title=Algorithms in Bioinformatics |chapter=Rapid Neighbour-Joining |year=2008 |doi=10.1007/978-3-540-87361-7_10 |volume=5251 |pages=113–122 |series=Lecture Notes in Computer Science |isbn=978-3-540-87360-0 |citeseerx=10.1.1.218.2078 }}
{{refend}}

==External links==
*[http://www.deduveinstitute.be/~opperd/private/neighbor.html The Neighbor-Joining Method] &mdash; a tutorial

{{Phylogenetics}}

{{DEFAULTSORT:Neighbor-Joining}}
[[Category:Bioinformatics algorithms]]
[[Category:Phylogenetics]]
[[Category:Computational phylogenetics]]
[[Category:Cluster analysis algorithms]]