Matchings and phylogenetic trees

Abstract

This paper presents a natural coordinate system for phylogenetic trees using a correspondence with the set of perfect matchings in the complete graph. This correspondence produces a distance between phylogenetic trees, and a way of enumerating all trees in a minimal step order. It is useful in randomized algorithms because it enables moves on the space of trees that make random optimization strategies "mix" quickly. It also promises a generalization to intermediary trees when data are not decisive as to their choice of tree, and a new way of constructing Bayesian priors on tree space.

Figure 1

These two trees are considered identical.

Figure 2

An initial phylogenetic tree with the leaves relabeled as numbers. Here there are 6 = m + 1 leaves.

Figure 3

The tree of Fig. 2 with internal nodes labeled.

Figure 4

The graph of all matchings on 6 points.