Multiple UPGMA and Neighbor-joining Trees and the Performance of Some Computer Packages

TLDR

UPGMA and neighbor‑joining methods can generate multiple tree topologies from a single distance matrix because of ties, a phenomenon that is rarely addressed. The study presents examples of ties and demonstrates that multiple trees must be considered when analyzing molecular data, while also comparing the performance of 15 software packages on tie handling. The authors evaluated 15 programs, noting that five (PHYLIP, MVSP, SAS, SYN‑TAX, NTSYS) recognize ties but apply different strategies, and compared their efficiency in detecting ties. Ties, if ignored, can bias bootstrap and jackknife confidence estimates, and the analysis revealed that NTSYS, PHYLIP, MVSP87 differ in tie‑detection efficiency, with some tools like MEGA producing single alternative topologies due to rounding or tolerance settings.

Abstract

*Royal Belgian Institute of Natural Sciences, Brussels; and TDepartments of Biology and SBiochemistry, University of Antwerp Although the unweighted pair-group method using arithmetic averages (UPGMA) and neighbor-joining (NJ) algo- rithms are designed to produce single trees, they may derive more than one topology from a single matrix, depending on the order of data entry. This “chaotic” behavior is due to ties, the effects of which are rarely considered. Therefore we present examples of ties and show that multiple UPGMA and NJ trees cannot be neglected with molecular data based on allozyme distances or “binary” distances derived from random amplified polymorphic DNA, restriction fragments, DNA fingerprints, or general protein patterns. We also compare the performance of 15 computer packages with respect to ties. Five programs recognize the problem (PHYLIP MVSP SAS, SYN-TAX, and NTSYS) but deal with it in different ways. We further point out that if ties are not properly taken into account, they might affect bootstrap and jackknife confidence estimates. Finally, we observed that NTSYS, PHYLIP MVSP and MVSP87 have different efficiencies in finding ties, and that some programs, including MEGA, may produce single alternative UPGMA topologies, probably due to their different rounding precisions or tie tolerances.