Generating Normal Networks via Leaf Insertion and Nearest Neighbor Interchange
Galled trees are studied as a recombination model in theoretic population genetics. This class of phylogenetic networks has been generalized to tree-child networks, normal networks and tree-based networks by relaxing a structural condition. Although these networks are simple, their topological structures have yet to be fully understood. It is well-known that all phylogenetic trees on n taxa can be generated by the insertion of the n-th taxa to each edge of all the phylogenetic trees on n-1 taxa. We prove that all tree-child networks with k reticulate nodes on n taxa can be uniquely generated via three operations from all the tree-child networks with k-1 or k reticulate nodes on n-1 taxa . An application of this result is found in counting tree-child networks and normal networks. In particular, a simple formula is given for the number of rooted phylogenetic networks with one reticulate node.
READ FULL TEXT