Combinatorial and stochastic properties of ranked tree‐child networks. Issue 4 (20th September 2021)

• Record Type: Journal Article
• Authors: Bienvenu, François; Lambert, Amaury; Steel, Mike
• Is Part Of: Random structures & algorithms. Volume 60:Issue 4(2022)
• Page Start: 653
• Page End: 689
• Publication Date: 2021-09-20
• Subjects: phylogenetic networks -- random graphs -- reticulate evolution; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21048
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Tree‐child networks are a class of directed acyclic graphs that have recently risen to prominence in phylogenetics. Although these networks have numerous, attractive mathematical properties, many combinatorial questions concerning them remain intractable. We show that endowing tree‐child networks with a biologically relevant ranking structure yields mathematically tractable objects, which we term ranked tree‐child networks (RTCNs). We derive explicit enumerative formulas and explain how to sample RTCNS uniformly at random. We study the properties of uniform RTCNs, including: lengths of random walks between root and leaves; distribution of number of cherries in the network; and sampling RTCNs conditional on displaying a given tree. We also formulate a conjecture regarding the scaling limit of the process counting the number of lineages in the ancestry of a leaf. The main idea in this paper, namely using ranking as a way to achieve combinatorial tractability, may also extend to other classes of networks.