Asymptotic Enumeration of Normal and Hybridization Networks via Tree Decoration

Area of Science:

• Evolutionary biology
• Computational phylogenetics
• Graph theory

Background:

• Phylogenetic trees represent evolutionary history but have limitations.
• Phylogenetic networks offer a more general framework for evolutionary relationships.
• Constructing and analyzing phylogenetic networks is an active research area.

Purpose of the Study:

• To investigate the properties of randomly generated phylogenetic networks.
• To determine conditions under which random arc placements yield valid normal networks.
• To develop methods for the asymptotic enumeration of normal and hybridization networks.

Main Methods:

• Randomly adding k arcs to rooted binary phylogenetic trees with n leaves.
• Analyzing the resulting directed graphs for network properties (normal, tree-child).
• Employing combinatorial methods for asymptotic enumeration.

Main Results:

• For fixed k, the proportion of valid normal networks approaches 1 as n increases.
• The asymptotic enumeration of normal networks becomes tractable.
• The methods extend to cases where k grows with n (o(n^(1/3))).
• Asymptotic results also apply to hybridization networks, a biologically relevant subclass.

Conclusions:

• Random arc insertion is a viable method for generating normal phylogenetic networks.
• This approach simplifies the combinatorial analysis of these networks.
• The findings have implications for understanding complex evolutionary histories and developing new phylogenetic network models.