Skip to Main content Skip to Navigation
Conference papers

The Structure of Level-k Phylogenetic Networks

Philippe Gambette 1, * Vincent Berry 2 Christophe Paul 1
* Corresponding author
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Evolution is usually described as a phylogenetic tree, but due to some exchange of genetic material, it can be represented as a phylogenetic network which has an underlying tree structure. The notion of level was recently introduced as a parameter on realistic kinds of phylogenetic networks to express their complexity and tree-likeness. We study the structure of level-k networks, and how they can be decomposed into level-k generators. We also provide a polynomial time algorithm which takes as input the set of level-k generators and builds the set of level-(k+1) generators. Finally, with a simulation study, we evaluate the proportion of level-k phylogenetic networks among networks generated according to the coalescent model with recombination.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download
Contributor : Philippe Gambette <>
Submitted on : Saturday, March 28, 2009 - 9:12:11 AM
Last modification on : Tuesday, December 8, 2020 - 9:47:14 AM
Long-term archiving on: : Thursday, June 10, 2010 - 7:05:38 PM


Files produced by the author(s)




Philippe Gambette, Vincent Berry, Christophe Paul. The Structure of Level-k Phylogenetic Networks. CPM: Combinatorial Pattern Matching, Jun 2009, Lille, France. pp.289-300, ⟨10.1007/978-3-642-02441-2_26⟩. ⟨lirmm-00371485⟩



Record views


Files downloads