Ed's Big Plans

Brief: It’s been such a long time since I’ve actually implemented neighbor joining for any reason– The neighbor-joining method (Saitou N, Nei M. 1987) is used to create binary trees such that we iteratively merge pairs of most-similar points in a collection. Every merge results in the creation of a new node where it adopts the two merged nodes as its children. This occurs until there is only one node left. This single remaining node is the root of the tree. Here it is on wikipedia, wherein a transitional Q-Matrix is used to store intermediate values– and here it is care of Fred Opperdoes, explained using a net divergence array and a distance matrix. The algorithm described is identical, but Opperdose’s explanation is a lot faster to comprehend. … Incidentally, the wikipedia article doesn’t explain how to break the tie to decide which child node gets what value against their newly merged parent. In wikipedia’s formalization, one gets a pair of children of the same distance from the parent but one has a negative sign (this is incorrectly ambiguous); in both worked examples however, the actual (correct) score of one arbitrary child is equal to the difference between the score of the parent and the other child. In reality, the steps following treat the two children symmetrically anyway, so which one is one and which the other is trivial… there is no favourite child– and barring the above error, no negative child either.