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.
Document type :
Conference papers
CPM: Combinatorial Pattern Matching, Jun 2009, Lille, France. Springer Berlin / Heidelberg, 20th Annual Symposium on Combinatorial Pattern Matching, LNCS (5577), pp.289-300, 2009, <http://bioinfo.lifl.fr/cpm09/>. <10.1007/978-3-642-02441-2_26>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485
Contributor : Philippe Gambette <>
Submitted on : Saturday, March 28, 2009 - 9:12:11 AM
Last modification on : Wednesday, June 29, 2016 - 10:25:59 AM
Document(s) archivé(s) le : 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. Springer Berlin / Heidelberg, 20th Annual Symposium on Combinatorial Pattern Matching, LNCS (5577), pp.289-300, 2009, <http://bioinfo.lifl.fr/cpm09/>. <10.1007/978-3-642-02441-2_26>. <lirmm-00371485>

Share

Metrics

Record views

304

Document downloads

232