I have been looking into how the neighbor joining algorithm works and I have two questions about the first step, i.e. computing the matrix Q using the following formula:
Q(i,j) = (n - 2)d(i,j) - Σd(i,k) - Σd(j,k)
Where both summations are from k = 1 to n, n is the number of taxons, d() is the distance between two elements and i and j are specific taxons.
From my understanding this formula creates a new matrix containing the distance between leaves i and j multiplied by (n-2). From this value we subtract the total distance from i to all other nodes and the total distance from j to all other nodes. This gives us a sense of how far away any given pair of nodes is from all other clusters.
I think we are using the term (n-2) as a scaling factor to ensure that the value calculated by the two sums does not dominate the result. If this is the case, why is it n-2 and not n-1 or just n?
Finally, I have also encountered the following formula for Q:
Q(i,j) = d(i,j) - 1/(n-2)Σd(i,k) - 1/(n-2)Σd(j,k)
Are these two formulas equivalent? If so why?
Thank you.
1 answer
All of my references have a different notation, but I will try to answer anyway.
If this is the case, why is it n-2 and not n-1 or just n?
You kind of answered the question yourself in the paragraph above. You want (try to) to fuse two nodes i and j into a new node p. By doing that you remove one edge from the tree, hence n-1. Knock off another -1 for each "self distance" i.e. value of 0 in the sum, thus n-2.
Are these two formulas equivalent? If so why?
They differ only by a factor of n-2. However, what it most important is to join the nodes with the minimum distance; and that doesn't change.
Log in to answer this question.
-
Problem in Python script of NJ
written by anasjamshed
-
Distance Matrix in R
written by vschultz •
-
Question regarding the neighbor-joining algorithm
written by psdanielxu •
-
Pairwise comparison of dataframe rows in R
written by OdongoR89 •
-
plotting problem with loop in R
written by smyiz •
-
goal of neighbour joining algorithm
written by mi.aghajohari •
-
Neural network and matrix
written by Billy •
-
How can i optimize distance Matrix that construct phylogenetic tree ??
written by eng_samar_zayed •
-
perl script for overlap algo
written by zunaira.ehsan21 •
-
On what condition(s) should a K-medoids algorithms stop when clustering organisms ?
written by nlehmann
This is not a scaling factor, it comes from doing the sum over all leaves except i and j.