  Given a set of species whose evolution is represented by a species tree, a
gene family is a group of genes having evolved from a single ancestral gene. A
gene family evolves along the branches of a species tree through various
mechanisms, including - but not limited to - speciation, gene duplication, gene
loss, horizontal gene transfer. The reconstruction of a gene tree representing
the evolution of a gene family constrained by a species tree is an important
problem in phylogenomics. However, unlike in the multispecies coalescent
evolutionary model, very little is known about the search space for gene family
histories accounting for gene duplication, gene loss and horizontal gene
transfer (the DLT-model). We introduce the notion of evolutionary histories
defined as a binary ordered rooted tree describing the evolution of a gene
family, constrained by a species tree in the DLT-model. We provide formal
grammars describing the set of all evolutionary histories that are compatible
with a given species tree, whether it is ranked or unranked. These grammars
allow us, using either analytic combinatorics or dynamic programming, to
efficiently compute the number of histories of a given size, and also to
generate random histories of a given size under the uniform distribution. We
apply these tools to obtain exact asymptotics for the number of gene family
histories for two species trees, the rooted caterpillar and the complete binary
tree, as well as estimates of the range of the exponential growth factor of the
number of histories for random species trees of size up to 25. Our results show
that including horizontal gene transfer induce a dramatic increase of the
number of evolutionary histories. We also show that, within ranked species
trees, the number of evolutionary histories in the DLT-model is almost
independent of the species tree topology.
