Counting phylogenetic networks of level 1 and 2
- PDF / 609,647 Bytes
- 39 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 178 Views
Mathematical Biology
Counting phylogenetic networks of level 1 and 2 Mathilde Bouvel1 · Philippe Gambette2
· Marefatollah Mansouri3
Received: 22 October 2019 / Revised: 29 August 2020 / Accepted: 13 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Phylogenetic networks generalize phylogenetic trees, and have been introduced in order to describe evolution in the case of transfer of genetic material between coexisting species. There are many classes of phylogenetic networks, which can all be modeled as families of graphs with labeled leaves. In this paper, we focus on rooted and unrooted level-k networks and provide enumeration formulas (exact and asymptotic) for rooted and unrooted level-1 and level-2 phylogenetic networks with a given number of leaves. We also prove that the distribution of some parameters of these networks (such as their number of cycles) are asymptotically normally distributed. These results are obtained by first providing a recursive description (also called combinatorial specification) of our networks, and by next applying classical methods of enumerative, symbolic and analytic combinatorics. Keywords Phylogenetic networks · Level · Galled trees · Counting · Combinatorial specification · Generating function · Asymptotic normal distribution Mathematics Subject Classification 05A15 · 05A16 · 92D15
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s00285020-01543-5) contains supplementary material, which is available to authorized users.
B
Philippe Gambette [email protected] Mathilde Bouvel [email protected] Marefatollah Mansouri [email protected]
1
Institut für Mathematik, Universität Zürich, Winterthurerstr. 190, 8057 Zurich, Switzerland
2
LIGM, Univ Gustave Eiffel, CNRS, ESIEE Paris, 77454 Marne-la-Vallée, France
3
Department of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstraße 8-10/104, 1040 Vienna, Austria
123
M. Bouvel et al.
1 Introduction Phylogenetic networks generalize phylogenetic trees introducing reticulation vertices, which have two parents, and represent ancestral species resulting from the transfer of genetic material between coexisting species, through biological processes such as lateral gene transfer, hybridization or recombination. More precisely, binary phylogenetic networks are usually defined as rooted directed acyclic graphs with exactly one root, tree vertices having one parent and 2 children, reticulation vertices having 2 parents and one child, and labeled leaves. The leaves are bijectively labeled by a set of taxa, which correspond to currently living species. As for trees, phylogenetic networks can be rooted or unrooted. Ideally, phylogenetic networks should be rooted, the root representing the common ancestor of all taxa labeling the leaves. But several methods which reconstruct phylogenetic networks, such as combinatorial (Huber et al. 2018; van Iersel and Moulton 2018), distancebased (Boc et al.
Data Loading...
