Generation of Binary Tree-Child phylogenetic networks

Abstract : Phylogenetic networks generalize phylogenetic trees by allowing the modelization of events of reticulate evolution. Among the different kinds of phylogenetic networks that have been proposed in the literature, the subclass of binary tree-child networks is one of the most studied ones. However, very little is known about the combinatorial structure of these networks. In this paper we address the problem of generating all possible binary tree-child (BTC) networks with a given number of leaves in an efficient way via reduction/augmentation operations that extend and generalize analogous operations for phylogenetic trees, and are biologically relevant. Since our solution is recursive, this also provides us with a recurrence relation giving an upper bound on the number of such networks. We also show how the operations introduced in this paper can be employed to extend the evolutive history of a set of sequences, represented by a BTC network, to include a new sequence. An implementation in python of the algorithms described in this paper, along with some computational experiments, can be downloaded from https://github.com/bielcardona/TCGenerators. Author summary Phylogenetic networks are widely used to represent evolutionary scenarios with reticulated events, and among them, the class of binary tree-child (BTC for short) networks is one of the most studied ones. Despite its importance, BTC networks, as mathematical objects, are not yet fully understood. In this paper we introduce two operations (reduction and augmentation) on the set of BTC networks that generalize well known operations on phylogenetic trees, and show how they can be used to analyze and synthesize any BTC network. Apart from the mathematical formulation of the problem, we exhibit how these operations can be used in biological applications to add a new sequence to a given BTC network. This can be useful, for instance, to update the network without redoing the whole search, or in a phylogenetic placement perspective. We also obtain a recursive formula for a bound on the number of such networks. We have implemented the algorithms in this paper, made them available on a public repository, and used this implementation to perform some computational simulations.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.umontpellier.fr/hal-02417275
Contributeur : Odile Hennaut <>
Soumis le : mercredi 18 décembre 2019 - 10:12:38
Dernière modification le : mardi 11 février 2020 - 10:10:14

Fichier

Scornavacca_22.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02417275, version 1

Collections

Citation

Gabriel Cardona, Joan Carles Pons, Celine Scornavacca. Generation of Binary Tree-Child phylogenetic networks. 2019. ⟨hal-02417275⟩

Partager

Métriques

Consultations de la notice

25

Téléchargements de fichiers

37