Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study - Sorbonne Université
Article Dans Une Revue Advances in Applied Mathematics Année : 2022

Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study

Olivier Bodini
Antoine Genitrini
Cécile Mailler
Mehdi Naima
  • Fonction : Auteur

Résumé

In this paper we introduce three new models of labelled random trees that generalise the original unlabelled Schröder tree. Our new models can be seen as models for phylogenetic trees in which nodes represent species and labels encode the order of appearance of these species, and thus the chronology of evolution. One important feature of our trees is that they can be generated efficiently thanks to a dynamical, recursive construction. Our first model is an increasing tree in the classical sense (labels increase along each branch of the tree and each label appears only once). To better model phylogenetic trees, we relax the rules of labelling by, e.g., allowing repetitions in the two other models. For each of the three models, we provide asymptotic theorems for different characteristics of the tree (e.g. degree of the root, degree distribution, height, etc), thus giving extensive information about the typical shapes of these trees. We also provide efficient algorithms to generate large trees efficiently in the three models. The proofs are based on a combination of analytic combinatorics, probabilistic methods, and bijective methods (we exhibit bijections between our models and well-known models of the literature such as permutations and Stirling numbers of both kinds).
Fichier principal
Vignette du fichier
paper.pdf (3.21 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02865198 , version 1 (11-06-2020)
hal-02865198 , version 2 (08-10-2021)

Identifiants

Citer

Olivier Bodini, Antoine Genitrini, Cécile Mailler, Mehdi Naima. Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study. Advances in Applied Mathematics, 2022, 133, pp.102284. ⟨10.1016/j.aam.2021.102284⟩. ⟨hal-02865198v2⟩
669 Consultations
319 Téléchargements

Altmetric

Partager

More