Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks
| dc.creator | van Iersel, Leo | |
| dc.creator | Kelk, Steven | |
| dc.creator | Mnich, Matthias | |
| dc.date | 2007-12-18 | |
| dc.date | 2008-07-21 | |
| dc.date.accessioned | 2026-07-07T09:51:29Z | |
| dc.date.available | 2026-07-07T09:51:29Z | |
| dc.description | Phylogenetic networks provide a way to describe and visualize evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridization or horizontal gene transfer. The level k of a network determines how non-treelike the evolution can be, with level-0 networks being trees. We study the problem of constructing level-k phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for each k, a level-k network that is uniquely defined by its triplets. We demonstrate the applicability of this result by using it to prove that (1) for all k of at least one it is NP-hard to construct a level-k network consistent with all input triplets, and (2) for all k it is NP-hard to construct a level-k network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability we give an exact algorithm for constructing level-1 networks consistent with a maximum number of input triplets. | |
| dc.identifier | https://arxiv.org/abs/0712.2932 | |
| dc.identifier | http://arxiv.org/abs/0712.2932 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/165267 | |
| dc.subject | Populations and Evolution | |
| dc.title | Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks | |
| dc.type | text |