Distance MethodsBret LargetDepartments of Botany and of StatisticsUniversity of Wisconsin—MadisonSeptember 22, 2011Distance Methods 1 / 12UPGMAUPGMA is an acronym for Unweighted Pair-Group Method withArithmetic Mean.UPGMA produces an ultrametric tree from a symmetric distancematrix.The depth of each node is the average of all of the pairwise distancesbetween joined subtrees from the original distance matrix.The algorithm joins the pair with the smallest distance and thenrecomputes the distance from the new group to others.Continue until there is only one group.Distance Methods 2 / 12UPGMA Algorithm1Find the i and j with the smallest distance Dij.2Create a new group (ij) which has n(ij)= ni+ njmembers.3Connect i and j on the tree to a new node (ij). Give the edgesconnecting i to (ij) and j to (ij) each length so that the depth ofgroup (ij) is Dij/2.4Compute the distance between the new group and all other groupsexcept i and j by usingD(ij),k=nini+ njDik+njni+ njDjk5Delete columns and rows corresponding to i and j and add one for(ij). If there are two or more groups left, go back to the first step.Distance Methods 3 / 12ExampleDog Bear Raccoon WeaselDog 0 32 48 52Bear 32 0 26 34Raccoon 48 26 0 42Weasel 52 34 42 0Join Bear and Raccoon, depth is 26/2 = 13.Distance Methods 4 / 12ExampleDog B/R WeaselDog 0 40 52B/R 40 0 38Weasel 52 38 0Join B/R and Weasel, depth is 38/2 = 19.Distance Methods 5 / 12ExampleDog B/R/WDog 0 44B/R/W 44 0Join Dog and B/R/W, depth is 44/2 = 22.Distance Methods 6 / 12UPGMA TreeDistance Methods 7 / 12Neighbor-joiningNeighbor-Joining creates an unrooted tree which will be exact iforiginal distance matrix matches an additive tree.Choice of the selected pair to join depends on adjusting distances toaccount for possible unequal rates.The adjustments result in negative “distances”, and the smallest ofthese is selected.Once there are three remaining groups, the same tree resultsregardless which pair is selected to join next.UPGMA and Neighbor-joining can lead to different tree topologies.Distance Methods 8 / 12Neighbor-joining Algorithm1For each leaf, compute ui=Pj6=iDij/(n − 2).2Choose the i and j for which Dij− ui− ujis smallest.3Join i and j to a new node with lengths (Dij+ ui− uj)/2 to node iand (Dij+ uj− ui)/2 to node j.4Compute the distance to the new node (ij) and the other groups asD(ij),k=Dik+ Djk− Dij25Delete columns and rows corresponding to i and j and add one for(ij). If there are three or more groups left, go back to the first step.Otherwise, connect the two remaining nodes with their distance.Distance Methods 9 / 12ExampleD B R W uiDog 0 32 48 52 66Bear 32 0 26 34 46Raccoon 48 26 0 42 58Weasel 52 34 42 0 64uj66 46 58 64D B R WDog — −80 −76 −78Bear −80 — −78 −76Raccoon −76 −78 — −80Weasel −78 −76 −80 —Can choose to join eitherD/B or R/W because of tie.New edge to dog has length(32 + 66 − 46)/2 = 26.New edge to bear has length(32 + 46 − 66)/2 = 6.Note these edges sum to 32,but are not equal.Distance Methods 10 / 12ExampleD/B R W uiD/B 0 21 27 48Raccoon 21 0 42 63Weasel 27 42 0 69uj48 63 69D/B R WD/B — −90 −90Raccoon −90 — −90Weasel −90 −90 —For the last three, you canalways join any pair.Simply use the equationfrom step 4 of the algorthmfor the distances.Note that in computing ui,we now use n = 3 as thereare n groups now.Distance Methods 11 / 12Neighbor-Joining TreeDistance Methods 12 /