Asymptotic Enumeration of Normal and Hybridization Networks via Tree Decoration

期刊论文
出版模式：

开放获取
发表日期：

2025年5月7日

查看全文

Michael Fuchs,
Mike Steel,
Qiang Zhang

摘要

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 $o(n^\frac{1}{3})$ $o (n^{\frac{1}{3}})$ ), 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.