Counting and enumerating tree-child networks and their subclasses

摘要

Galled trees are studied as a recombination model in population genetics. This class of phylogenetic networks is generalized into tree-child and galled network classes by relaxing a structural condition imposed on galled trees. We provide a solution to an open problem that is how to count and enumerate tree-child networks with fixed number of leaves and reticulations. Explicit counting formulas are also given for galled trees through their relationship to ordered trees and phylogenetic networks in which the child of each reticulation is a leaf.