Generalizing Matrix Representations to Fully Heterochronous Ranked Tree Shapes

Phylogenetic tree shapes capture fundamental signatures of evolution. We consider "ranked" tree shapes, which are equipped with a total order on the internal nodes compatible with the tree graph. Recent work has established an elegant bijection between ranked tree shapes and a class of integer matrices, called F-matrices, defined by simple inequalities. This formulation is for isochronous ranked tree shapes, where all leaves share the same sampling time, such as in the study of ancient human demography from present-day individuals. However, branch lengths of phylogenetic trees can represent units other than calendar time, such as evolutionary distance. A tree equipped with branch lengths quantifying evolutionary distance, called a rooted phylogram, is output by popular maximum-likelihood methods. These trees are broadly relevant, such as to study the affinity maturation of B cells in the immune system. Discretizing time in a rooted phylogram gives a fully heterochronous ranked tree shape, where leaves are part of the total order. Here we extend the F-matrix framework to such fully heterochronous ranked tree shapes. We establish an explicit bijection between a class of F-matrices and the space of such tree shapes. The matrix representation has the key feature that the value at any entry is highly constrained by four previous entries, enabling straightforward enumeration of all valid tree shapes. We also use this framework to develop probabilistic models on ranked tree shapes. Our work extends understanding of combinatorial objects that have a rich history in the literature.