Search

Abstract In mathematical phylogenetics, given a rooted binary leaf-labeled gene tree topology G and a rooted binary leaf-labeled species tree topology S with the same leaf labels, a coalescent history represents a possible mapping of the list of gene tree coalescences to the associated branches of the species tree on which those coalescences take place. For certain families of ordered pairs (G , S) , the number of coalescent histories increases exponentially or even faster than exponentially with the number of leaves n. Other pairs have only a single coalescent history. We term a pair (G , S) lonely if it has only one coalescent history. Here, we characterize the set of all lonely pairs (G , S). Further, we characterize the set of pairs of rooted binary unlabeled tree shapes at least one of the labelings of which is lonely. We provide formulas for counting lonely pairs and pairs of unlabeled tree shapes with at least one lonely labeling. The lonely pairs provide a set of examples of pairs (G , S) for which the number of compact coalescent histories—which condense coalescent histories into a set of equivalence classes—is equal to the number of coalescent histories. Application of the condition that characterizes lonely pairs can also be used to reduce computation time for the enumeration of coalescent histories. [ABSTRACT FROM AUTHOR]

For a fixed set X containing n taxon labels, an ordered pair consisting of a gene tree topology G and a species tree topology S bijectively labeled with the labels of X possesses a set of coalescent histories—mappings from the set of internal nodes of G to the set of edges of S describing possible lists of edges in S on which the coalescences in G take place. Enumerations of coalescent histories for gene trees and species trees have produced suggestive results regarding the pairs (G , S) that, for a fixed n , have the largest number of coalescent histories. We define a class of 2-cherry binary tree topologies that we term p-pseudocaterpillars , examining coalescent histories for non-matching pairs (G , S) in the case in which S has a caterpillar shape and G has a p -pseudocaterpillar shape. Using a construction that associates coalescent histories for (G , S) with a class of "roadblocked" monotonic paths, we identify the p -pseudocaterpillar labeled gene tree topology that, for a fixed caterpillar labeled species tree topology, gives rise to the largest number of coalescent histories. The shape that maximizes the number of coalescent histories places the "second" cherry of the p -pseudocaterpillar equidistantly from the root of the "first" cherry and from the tree root. A symmetry in the numbers of coalescent histories for p -pseudocaterpillar gene trees and caterpillar species trees is seen to exist around the maximizing value of the parameter p. The results provide insight into the factors that influence the number of coalescent histories possible for a given gene tree and species tree. [ABSTRACT FROM AUTHOR]

Given a gene tree topology and a species tree topology, a coalescent history represents a possible mapping of the list of gene tree coalescences to associated branches of a species tree on which those coalescences take place. Enumerative properties of coalescent histories have been of interest in the analysis of relationships between gene trees and species trees. The simplest enumerative result identifies a bijection between coalescent histories for a matching caterpillar gene tree and species tree with monotonic paths that do not cross the diagonal of a square lattice, establishing that the associated number of coalescent histories for n -taxon matching caterpillar trees (n ⩾ 2) is the Catalan number C n − 1 = 1 n ( 2 n − 2 n − 1 ). Here, we show that a similar bijection applies for non-matching caterpillars, connecting coalescent histories for a non-matching caterpillar gene tree and species tree to a class of roadblocked monotonic paths. The result provides a simplified algorithm for enumerating coalescent histories in the non-matching caterpillar case. It enables a rapid proof of a known result that given a caterpillar species tree, no non-matching caterpillar gene tree has a number of coalescent histories exceeding that of the matching gene tree. Additional results on coalescent histories can be obtained by a bijection between permissible roadblocked monotonic paths and Dyck paths. We study the number of coalescent histories for non-matching caterpillar gene trees that differ from the species tree by nearest-neighbor-interchange and subtree-prune-and-regraft moves, characterizing the non-matching caterpillar with the largest number of coalescent histories. We discuss the implications of the results for the study of the combinatorics of gene trees and species trees. [ABSTRACT FROM AUTHOR]