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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485
Contributor : Philippe Gambette <>
Submitted on : Saturday, March 28, 2009 - 9:12:11 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Thursday, June 10, 2010 - 7:05:38 PM

File

2009GambetteBerryPaulGenerator...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

720

Files downloads

590