1. Introduction
In mathematical phylogenetics, a coalescent history represents the paired list of coalescences in a gene tree together with their associated edges of a species tree. Consider two binary, rooted, leaf-labeled trees, G and S, with leaves labeled by the same label set X, such that each label in X is associated with exactly one leaf of G and exactly one leaf of S. We regard G as a gene tree representing the evolution of genealogical lineages in a group of species, and S as the species tree representing the evolutionary descent of the species themselves.
For a gene tree G evolving on a species tree S, a coalescent history is a mapping from the set of internal nodes of G to the set of internal edges of S, such that two rules are followed: (i) the image of an internal node v of G is ancestral in S to each leaf of S that shares a label with some leaf descended from v in G; (ii) the image of an internal node v of G is ancestral in S to the images of each of its descendant nodes. The biological interpretation of (i) is that a set of gene lineages can only find a common ancestor on a species tree edge that it is possible for them all to reach; the interpretation of (ii) is that the gene lineages descended from a descendant node coalesce at least as recently as do the gene lineages descended from its ancestral nodes. Note that we regard a node as trivially ancestral to and descended from itself. The coalescent histories for (G, S) can be viewed as describing a discrete class of evolutionary scenarios for the lineages of G on the edges of S.
A variety of studies have enumerated the coalescent histories for pairs (G, S), both by a recursive approach that applies for all (G, S), and by closed-form formulas and bijective constructions suited to particular families of trees. These enumeration studies, primarily considering matching gene trees and species trees with G = S and having particular emphasis on shapes such as caterpillars, 4-pseudocaterpillars, and caterpillar-like families (Fig. 1), have informally observed that in specified classes of trees, the largest number of coalescent histories tends to occur when the pair (G, S) has two features: multiple sequences exist in which the coalescences of G can be arranged, and many edges of S exist on which those coalescences can take place.
Rosenberg observed that for small trees with at most n = 9 leaves and G = S, the largest numbers of coalescent histories among tree pairs (G, G) with fixed n were seen for trees that had structure similar to caterpillar trees, but that unlike caterpillars, had more than one possible sequence of coalescences. Rosenberg and Disanto & Rosenberg examined tree families (G, G), with n growing arbitrarily large in specified caterpillar-like tree families. Beginning with a seed tree, these studies generated families of increasingly large trees by sequentially adding taxa so that the next tree in a family was formed by placing the current tree and a single leaf on opposite sides of a new root. They saw that across all seed trees of a fixed small size, as the number of leaves grew without bound, the largest numbers of coalescent histories were achieved when the seed tree had many different sequences in which its coalescences could be arranged. Disanto & Rosenberg constructed a tree family, the lodgepole family, that, unlike caterpillar families, grows so that as the number of leaves increases, trees accumulate both new sequences in which coalescences can be arranged and new places for them to occur. This family is the family of matching tree pairs (G, G) with the largest-known number of coalescent histories as n increases without bound.
Despite many observations suggesting that coalescent histories tend to increase in number when G has many sequences in which coalescences can be arranged and many edges on which those coalescences can occur, existing results in support of this view have focused on small trees and on informal interpretations of specific families with large limits as n → ∞; no result has formally demonstrated the observation in a class of trees for a fixed finite n of arbitrary size. We devise a scenario to formalize this idea characterizing cases with the largest numbers of coalescent histories. We fix the species tree S to be a caterpillar, and we consider a family of non-matching gene trees G, the p-pseudocaterpillars. We show that in this class of non-matching pairs (G,S) with fixed n, the largest number of coalescent histories is achieved precisely when G combines the two elements: many coalescence sequences, and many edges on which those coalescences can take place.
Our approach is one of relatively few to examine enumerations of coalescent histories in the case that G is not necessarily equal to S. The strategy employs a construction that enumerates coalescent histories for non-matching caterpillar trees. Generalizing a result of Degnan for enumeration of coalescent histories for matching caterpillar trees, Himwich & Rosenberg produced a bijection with monotonic paths for use in enumerating coalescent histories for non-matching caterpillar pairs (G,S). We use this monotonic-path construction to enumerate coalescent histories for the class of non-matching trees that considers a caterpillar species tree S and a p-pseudocaterpillar gene tree G.
Section 2 introduces definitions and notation. Section 3 gives an example that mo- tivates the general calculation. In Section 4, we enumerate coalescent histories in the general case. Section 5 gives special cases with specified values of p. Finally, in Section 6, for a specified caterpillar species tree S of fixed size n, considering all possible values of p, we obtain the maximal number of coalescent histories across all non-matching p-pseudocaterpillar trees G. Section 7 discusses a symmetry in p for fixed n, and we conclude with a discussion in Section 8. The computations illustrate how the monotonic path approach of Himwich & Rosenberg in the case of caterpillar species trees can be extended to enumerate coalescent histories in more cases beyond that of caterpillar gene trees.
2. Preliminaries
We formally define coalescent histories and p-pseudocaterpillars in Sections 2.1 and 2.2, and we introduce results concerning the Catalan numbers in Section 2.3. In Section 2.4, we describe the use of monotonic paths to enumerate coalescent histories for caterpillar tree pairs.
2.1. Coalescent histories
The definitions in this article closely follow Himwich & Rosenberg. Henceforth, we treat all "trees" as binary and rooted; trees are leaf-labeled, but the labels are sometimes omitted for convenience. The set of vertices or nodes of a tree can be divided into leaf nodes and non-leaf internal nodes. For tree G, we say that a node v1 is descended from a node v2 if the path from v1 to the root of G travels through v2; v2 is then ancestral to v1. Ancestor–descendant relationships also apply to edge–edge pairs and edge–node pairs. A node or edge is trivially descended from and ancestral to itself. Each internal node, including the root, possesses an associated internal edge immediately ancestral to it. Thus, viewed forward in time, the root—like other internal nodes—has in-degree 1 and out-degree 2.
We consider pairs (G,S) in which G represents a gene tree, describing the descent of a set of genealogical lineages, and S represents a species tree, describing the descent of a set of species. G and S are assumed to have the same number of leaves, n. We assume that the leaf set of G and the leaf set of S are labeled by the same label set X, and that each label in X is assigned to exactly one leaf of G and to exactly one leaf of S. This assumption corresponds to an assumption that exactly one gene lineage is sampled in each of the n species.
For the pair (G, S), we can formally define the functions known as coalescent histories.
Definition 1. Consider a pair of trees (G,S) that are binary, rooted, and leaf-labeled, with the labels in bijective correspondence. A coalescent history is a function α from the set of internal nodes of G to the set of internal edges of S, satisfying two conditions:
(a) For each internal node v in G, all labels for leaves descended from v in G label leaves descended from edge α(v) in S.
(b) For each pair of internal nodes v1 and v2 in G, if v2 is descended from v1, then α(v2) is descended from α(v1) in S.
In this definition, nodes of G represent coalescent events for the gene lineages, and edges of S represent species tree edges along which the gene lineages evolve. A coalescent history reflects the biological process of coalescence, in which descendants cannot coalesce farther back in time than their ancestors. Ancestor–descendant relations are preserved under the mapping α.
Informally, considering the biological process of coalescence, we often refer to internal nodes as coalescences. We refer to gene tree coalescences "happening," "occurring," or "taking place" on species tree edges. For example, a gene tree coalescence v in G "can occur" on a species tree edge w in S if and only if there exists a coalescent history α with α(v) = w.
2.2. Caterpillars and p-pseudocaterpillars
As our goal is to enumerate the coalescent histories in the case that G has a p- pseudocaterpillar topology and S has a caterpillar topology, we define caterpillar and p-pseudocaterpillar shapes for binary, rooted tree topologies.
Definition 2. A caterpillar tree is a binary, rooted tree that has an internal node that is descended from all other internal nodes.
In a caterpillar tree, each internal node has at least one leaf as an immediate descen- dant (Fig. 1A). Equivalently, a caterpillar tree is a tree that has only one cherry node: an internal node with exactly two descendant leaves. Rosenberg defined binary, rooted pseudocaterpillar trees with n ≥ 4 leaves as trees in which all internal nodes except one have at least one immediate leaf descendant. The node that provides the exception has two cherry nodes as its immediate descendants. We generalize the earlier definition of pseudocaterpillar trees to consider generalized pseudocaterpillar trees. To define this concept, we denote by vL and vR the left and right descendant nodes of an internal node v.
Definition 3. A generalized pseudocaterpillar tree is a binary, rooted tree that has at least four leaves and that satisfies two conditions. (i) The tree possesses exactly two cherry nodes. (ii) For each internal node v, at least one of vL,vR has no more than two descendant leaves.
In other words, a generalized pseudocaterpillar tree is formed from a caterpillar tree, replacing one of the leaves not descended from the unique cherry node by a second cherry node (Fig. 1B).
A generalized pseudocaterpillar can be described by two numbers: the total number of leaves n and the position p of the "second" cherry. To precisely identify p for a generalized pseudocaterpillar tree, we label the leaves by natural numbers starting from left to right, placing the "first" cherry—the one present in the caterpillar from which the generalized pseudocaterpillar has been generated—on the left. We define the position of the second cherry as the number corresponding to its second leaf from the left (Fig. 2A). A generalized pseudocaterpillar tree with a second cherry in position p, 4 ≤ p ≤ n, is termed a p-pseudocaterpillar tree. The pseudocaterpillar trees in the sense of Rosenberg are 4-pseudocaterpillars.
Note that for convenience, our description of the value of p in a p-pseudocaterpillar tree relies on a canonical orientation of the tree. This value of p can also be identified as the number of leaves in the smallest subtree that contains both cherries of the tree.
Our interest is in the case in which the gene tree has a p-pseudocaterpillar topology for some p, and the species tree has a caterpillar topology. A species tree with n leaves has n − 1 edges on which gene tree coalescences can happen; we also label these edges with natural numbers, following the order from Degnan & Salter (Fig. 2B).