Comparing Trees with Pendant Vertices Labelled

Abstract

A significant problem in analysing the results from evolutionary tree building algorithms, and with comparing conflicting evolutionary hypotheses, has been to find a way to measure differences between trees whose pendant vertices (endpoints) are labelled. A number of different measures have been proposed, but none has been shown to be easy to calculate, biologically relevant and to have a known distribution. In this paper we analyse one measure of tree difference, show how it can be calculated easily, and indicate that it has biological relevance as it counts the different classes in the corresponding hierarchal systems. We then develop a distribution theory from which we calculate the probability of finding, from a specified set of trees, a pair of trees with a given difference value. A connection between this problem and an existing combinatorial problem is also given.