Asymptotic Counting of Binary Phylogenetic Networks

Abstract

Phylogenetic networks provide a general framework for modeling reticulate evolutionary processes such as hybridization, recombination, and horizontal gene transfer. In this paper, we study the asymptotic counting of binary phylogenetic networks with $k$ reticulations on $n$ taxa, where $k$ is allowed to grow with $n$. Using edge insertion, we analyze the local structures that affect the number of possible constructions of such networks. By bounding the contribution of networks with exceptional local configurations and combining these bounds with known asymptotic formulas for tree-child networks, we show that, when $k=o(\sqrt{n})$, the number of binary phylogenetic networks with $k$ reticulations on $n$ taxa is asymptotic to \[ \binom{n}{k}2^{n+k-1/2}n^{n+k-1}e^{-n}. \]

24 pages, 7 figures