An unconstrained Euclidean parametrisation of phylogenetic tree space

Abstract

Phylogenetic trees combine a discrete topology with continuous branch lengths, which makes them difficult to work with. We introduce a recursive contour-grafting construction that encodes both components using unconstrained real-valued coordinates. After fixing an order of the leaves, each new leaf is attached at a point selected by a contour traversal of the tree constructed so far. Moving a graft coordinate continuously along the contour enables changes of topology when internal branches contract to zero. For trees with n labelled leaves, we apply the construction to rooted ultrametric trees, rooted trees with unrestricted branch lengths, and unrooted trees, obtaining parametrisations of dimensions n-1, 2n-2, and 2n-3, respectively. We show that the resulting construction functions are surjective and continuous onto the corresponding spaces of phylogenetic trees. We also determine the number of representations of a generic tree and calculate the Jacobian of each parametrisation. These results provide explicit change-of-variables formulae between Euclidean coordinates and the phylogenetic tree spaces, and we show how probability distributions on tree space can be sampled using generic algorithms that target unconstrained Euclidean coordinates. This approach paves the way for the development and application of new methodology in Bayesian phylogenetic inference.