Asymptotic Enumeration of Normal and Hybridization Networks via Tree Decoration

Phylogenetic networks provide a more general description of evolutionary relationships than rooted phylogenetic trees. One way to produce a phylogenetic network is to randomly place k arcs between the edges of a rooted binary phylogenetic tree with n leaves. The resulting directed graph may fail to be a phylogenetic network, and even when it is it may fail to be a tree-child or normal network. In this paper, we first show that if k is fixed, the proportion of arc placements that result in a normal network tends to 1 as n grows. From this result, the asymptotic enumeration of normal networks becomes straightforward and provides a transparent meaning to the combinatorial terms that arise. Moreover, the approach extends to allow k to grow with n (at the rate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:msup><mml:mi>n</mml:mi> <mml:mfrac><mml:mn>1</mml:mn> <mml:mn>3</mml:mn></mml:mfrac> </mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> ), which was not handled in earlier work. We also investigate a subclass of normal networks of particular relevance in biology (hybridization networks) and establish that the same asymptotic results apply.