Extension of Colijn-Plazotta tree shape distance metric to unrooted trees

Abstract

Colijn-Plazotta tree shape labeling scheme allows to describe an arbitrary phylogenetic tree topology by recursively labeling all nodes from tips to root with integers. The multisets of these labels can then be used to estimate the difference between topologies using eg Euclidean distance. In this work I propose an extension of the labeling scheme (and thus a distance metric) to unrooted trees, which is achieved by labeling all rooted subtrees within a given tree. To avoid exhaustively enumerating the subtrees, the labels are collected into a dependency graph and calculated in a single pass. A proof-of-concept implementation is available at https://github.com/synedraacus/metrics.