Editing Neighbor joining (section)

== 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.