 |
 |
|
|
| HAL: lirmm-00371485, version 1 |
| DOI: 10.1007/978-3-642-02441-2_26 |
| Detailed view |  Export this paper |
|
|
| CPM'09: 20th Annual Symposium on Combinatorial Pattern Matching, Lille, France : (2009) |
|
|
|
|
| The Structure of Level-k Phylogenetic Networks |
|
|
Philippe Gambette 1Vincent Berry 1 |
|
|
| (2009-06-22) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1: | Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) |
|
|
|
CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc |
|
|
|
|
|
|
|
|
|
| [INFO/ALGCO] |
|
|
|
|
| Subject | : | Computer Science/Bioinformatics Life Sciences/Quantitative Methods Computer Science/Discrete Mathematics |
|
|
| Combinatorics – phylogenetic networks – decomposition – directed graphs – level-k networks |
|
|
|
| Attached file list to this document: | |||||
|
|||||
|
|
|
| lirmm-00371485, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00371485 | |
| From: Algo Ligm | |
| Submitted on: Saturday, 28 March 2009 09:12:11 | |
| Updated on: Wednesday, 1 July 2009 11:24:23 | |
