A phylogenetic (i.e. evolutionary) tree is an unrooted binary tree T in which the leaves are in bijection with a set of labels X, where X represents a set of contemporary species. Here we present a number of enumeration results pertaining to convex characters: partitions of X in which the minimal spanning trees induced by the blocks of the partition, are vertex disjoint in T. Via a number of transformations we show that enumerating specially chosen subfamilies of convex characters is sufficient to give an algorithm with running time O*(1.6181^n) for computing the “2-state maximum parsimony distance” between two phylogenetic trees, where n=|X| and O*(.) suppresses polynomial factors – this distance is used to quantify how different two evolutionary histories are. Next, we show that one of these subfamilies of convex characters is actually in bijection with a constrained subfamily of matchings (i.e. disjoint sets of edges) defined over a secondary, auxiliary tree structure. By proving that there are at most O(1.5895^n) such constrained matchings, we obtain a faster algorithm for the aforementioned distance problem, and as a corollary obtain a tight upper bound on the number of matchings in general trees with certain degree restrictions, extending results from the matchings literature. For the O(1.5895^n) result we leverage recent techniques that have been developed for bounding the rate of growth of certain structured families of recurrences.
This is joint work with Ruben Meuwese (Maastricht) and Stephan Wagner (Uppsala).