A Vectorial Tree Distance Measure

Abstract A vectorial distance measure for trees is presented. Given two trees, we align the trees from their centers outwards, starting from the root-branches, to make the next level as similar as possible. The algorithm is recursive; condition on the alignment of the root-branches we align the sub-branches, thereafter each alignment is conditioned on the previous one. We define a minimal alignment under a lexicographic order which follows the intuition that the differences between the two trees closer to their cores dominate their differences at a higher level. Given such a minimal alignment, the difference in the number of branches calculated at any level defines the entry of the distance vector at that level. We compare our algorithm to other well-known tree distance measures in the task of clustering sets of phylogenetic trees. We use the TreeSimGM simulator for generating stochastic phylogenetic trees. The vectorial tree distance can successfully separate symmetric from asymmetric trees, and hierarchical from non-hierarchical trees.