Answers.Body: <p>Let's look at the components of the equation one by one first since it is easier to describe each part on its own. We can do this because they are added together in computing <span class="math-container">$Q_{ij}$</span>. Component1, <span class="math-container">$(m-2)d_{ij}$</span> is saying that we want a quantity which would be the total penalization, if every distance for <span class="math-container">$m$</span> sequences was <span class="math-container">$d_{ij}$</span> excluding the 2 distances between themselves (it's a direct proportionality so that the <span class="math-container">$Q_{ij} \propto (m-2)d_{ij}$</span>). Component2,
  <span class="math-container">$\left(\sum_{k\neq i}d_{ik}\right)$</span>, says that we look at the sum of the distances sequence <span class="math-container">$i$</span> has against all other sequences excluding itself
  (it's an inverse proportionality so that the <span class="math-container">$Q_{ij} \propto \left(\sum_{k\neq i}d_{ik}\right)^{-1}$</span>), and <span class="math-container">$\left(\sum_{k\neq j}d_{jk}\right)$</span> as component3 is analogous.</p>
  <p><em>non-direct neighbours</em> means that on the phylogenetic tree, 2 extant sequences (sequences in the alignment) have another sequence set that can link them together. If two sequences are definitely related to each other then on the phylogenetic tree they will produce a bifurcation and the smallest distance between themselves as being <em>directly</em> related, <span class="math-container">$(m-2)d_{ij} &lt; \left(\sum_{k\neq i}d_{ik} + \sum_{k\neq j}d_{jk}\right)$</span>, eg. the <span class="math-container">$d_{ij}=1$</span> and the rest are all greater than 1 gives us a low number. If <span class="math-container">$f_{max_{i,j}}(d_{ij})$</span> is used we'd be using the maximum distance for component1 so the overall measure would be positive and as large as possible.</p>
  <p>In summary it provides a measure for placing the sequences together with the closest distance. You may say that this is 'overkill' as we can just search the <span class="math-container">$m^2/2-m$</span> set of distances and choose the minimum. In the goal for producing the tree, things get more interesting. Let's say look at 3 sequences <span class="math-container">$i,j,k$</span> of a larger set <span class="math-container">$m$</span>, and see that sequences together have the same distance between them <span class="math-container">$d_{ij}=d_{ik}$</span> in respect to <span class="math-container">$i$</span>. <span class="math-container">$d_{ij}=d_{j*}$</span> would mean that <span class="math-container">$j$</span> is equally distance to all other sequences as it is to <span class="math-container">$i$</span> and let's say <span class="math-container">$d_{kz}=max \land d_{ky,y\neq z}=d_{ij}$</span> (the sequence <span class="math-container">$k$</span> is equidistance to all sequences except to a particular sequence <span class="math-container">$z$</span> and can happen in some region in the alignment). Which do we join with <span class="math-container">$i$</span>? According to the formula we choose <span class="math-container">$k$</span> over <span class="math-container">$j$</span> because <span class="math-container">$k$</span> is more distant from other sequence(s) as it would provide a more negative number (lower values cause of the 2nd and 3rd components although component1 is the same in both cases). Effectively we want the minimum distance to <span class="math-container">$i$</span> and simultaneously the maximal distance from other sequences (penalize sequences which could be closely related to the other sequences helps produce an overall better tree).</p>
  <p><em>Anders Gorm Pedersen (of DTU)</em> in his <a href="https://www.youtube.com/watch?v=ro2MFmVZypQ&amp;list=PLXwjzs_mabFrlRF7uALEomfGGckG0sG5y&amp;index=17" rel="nofollow noreferrer">coursera videos (also on YT)</a> provides some numerical examples to see how the numbers are produced on an example tree.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-02T18:46:55.387Z
Answers.LastActivityDate: 2020-10-02T18:46:55.387Z
Answers.UserDisplayName: Vass
Answers.Body: <p>NJ as with all clustering methods there isn't an explanation, It is a hierarchical clustering method but there are many algorithms to cluster a distance matrix. NJ is closely associated with the concept behind UPGMA (unweighted pair group mean algorithm)</p>
  
  <p>The key difference with UPGMA is that after joining two taxa by NJ the reconstructed genetic distance between the node and one taxa versus the other taxa is not assumed to be equal, i.e. the rate of mutation is heterogeneous. All other clustering algorithms I know assume a "global molecular clock" if that makes any sense, the mutation is constant against time. NJ removes that assumption and thats why we like it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-31T23:29:38.453Z
Answers.Text: So there is no motivation behind the formula other than 'it just works'?
Answers.UserDisplayName: Gogis
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-31T23:37:46.500Z
Answers.Text: Well, clustering is not statistically cool no how you look at it. HOWEVER, NJ allows the calculation of a additive tree  (phylogram) rather than an ultrametric tree (cladogram) and that is very useful.
Answers.UserDisplayName: M__
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-30T18:13:44.320Z
Answers.LastActivityDate: 2020-05-30T18:13:44.320Z
Answers.UserDisplayName: M__
Body: <p>In each iteration of the neighbour-joining method of phylogenetic trees construction, after joining the nearest neighbours the (additive) distance matrix <span class="math-container">$D_{m \times m}$</span> is recomputed as</p>
  <p><span class="math-container">$$Q_{ij} = (m-2)d_{ij} - \Bigg( \sum_{k \neq i} d_{ik} \Bigg) - \Bigg( \sum_{k \neq j} d_{jk} \Bigg)$$</span></p>
  <p>As is stated in numerous sourced that I found, it prevents the joining of non-direct neighbours, but am looking for a more detailed explanation and motivation.</p>
  <p>Sources: <a href="https://en.wikipedia.org/wiki/Neighbor_joining" rel="nofollow noreferrer">Wikipedia</a></p>
  
Tags: <phylogenetics><phylogeny><sequence-analysis><matrix>
Title: Motivation behind the neighbor-joining distance matrix recomputation
ThreadText: # Motivation behind the neighbor-joining distance matrix recomputation
  
  (Asked by: username_0 on 2020-05-30)
  
  In each iteration of the neighbour-joining method of phylogenetic trees construction, after joining the nearest neighbours the (additive) distance matrix $D\_{m \times m}$ is recomputed as
  
  $$Q\_{ij} = (m-2)d\_{ij} - \Bigg( \sum\_{k \neq i} d\_{ik} \Bigg) - \Bigg( \sum\_{k \neq j} d\_{jk} \Bigg)$$
  
  As is stated in numerous sourced that I found, it prevents the joining of non-direct neighbours, but am looking for a more detailed explanation and motivation.
  
  Sources: [Wikipedia](https://en.wikipedia.org/wiki/Neighbor_joining)
  
  **Tags:** phylogenetics, phylogeny, sequence-analysis, matrix
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-10-02. Score: 2 | Accepted answer
  
  Let's look at the components of the equation one by one first since it is easier to describe each part on its own. We can do this because they are added together in computing $Q\_{ij}$. Component1, $(m-2)d\_{ij}$ is saying that we want a quantity which would be the total penalization, if every distance for $m$ sequences was $d\_{ij}$ excluding the 2 distances between themselves (it's a direct proportionality so that the $Q\_{ij} \propto (m-2)d\_{ij}$). Component2,
  $\left(\sum\_{k\neq i}d\_{ik}\right)$, says that we look at the sum of the distances sequence $i$ has against all other sequences excluding itself
  (it's an inverse proportionality so that the $Q\_{ij} \propto \left(\sum\_{k\neq i}d\_{ik}\right)^{-1}$), and $\left(\sum\_{k\neq j}d\_{jk}\right)$ as component3 is analogous.
  
  *non-direct neighbours* means that on the phylogenetic tree, 2 extant sequences (sequences in the alignment) have another sequence set that can link them together. If two sequences are definitely related to each other then on the phylogenetic tree they will produce a bifurcation and the smallest distance between themselves as being *directly* related, $(m-2)d\_{ij} < \left(\sum\_{k\neq i}d\_{ik} + \sum\_{k\neq j}d\_{jk}\right)$, eg. the $d\_{ij}=1$ and the rest are all greater than 1 gives us a low number. If $f\_{max\_{i,j}}(d\_{ij})$ is used we'd be using the maximum distance for component1 so the overall measure would be positive and as large as possible.
  
  In summary it provides a measure for placing the sequences together with the closest distance. You may say that this is 'overkill' as we can just search the $m^2/2-m$ set of distances and choose the minimum. In the goal for producing the tree, things get more interesting. Let's say look at 3 sequences $i,j,k$ of a larger set $m$, and see that sequences together have the same distance between them $d\_{ij}=d\_{ik}$ in respect to $i$. $d\_{ij}=d\_{j\*}$ would mean that $j$ is equally distance to all other sequences as it is to $i$ and let's say $d\_{kz}=max \land d\_{ky,y\neq z}=d\_{ij}$ (the sequence $k$ is equidistance to all sequences except to a particular sequence $z$ and can happen in some region in the alignment). Which do we join with $i$? According to the formula we choose $k$ over $j$ because $k$ is more distant from other sequence(s) as it would provide a more negative number (lower values cause of the 2nd and 3rd components although component1 is the same in both cases). Effectively we want the minimum distance to $i$ and simultaneously the maximal distance from other sequences (penalize sequences which could be closely related to the other sequences helps produce an overall better tree).
  
  *Anders Gorm Pedersen (of DTU)* in his [coursera videos (also on YT)](https://www.youtube.com/watch?v=ro2MFmVZypQ&list=PLXwjzs_mabFrlRF7uALEomfGGckG0sG5y&index=17) provides some numerical examples to see how the numbers are produced on an example tree.
  
  
  ---
  
  ### Answer by username_2 on 2020-05-30. Score: 2
  
  NJ as with all clustering methods there isn't an explanation, It is a hierarchical clustering method but there are many algorithms to cluster a distance matrix. NJ is closely associated with the concept behind UPGMA (unweighted pair group mean algorithm)
  
  The key difference with UPGMA is that after joining two taxa by NJ the reconstructed genetic distance between the node and one taxa versus the other taxa is not assumed to be equal, i.e. the rate of mutation is heterogeneous. All other clustering algorithms I know assume a "global molecular clock" if that makes any sense, the mutation is constant against time. NJ removes that assumption and thats why we like it.
  
  > **Comments:**
  > **username_0**: So there is no motivation behind the formula other than 'it just works'?  
  > **username_2**: Well, clustering is not statistically cool no how you look at it. HOWEVER, NJ allows the calculation of a additive tree  (phylogram) rather than an ultrametric tree (cladogram) and that is very useful.  
  
  ---
  
  