title: Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks.
abstract: 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 > or = 1 it is NP-hard to construct a level-k network consistent with all input triplets, and (2) for all k > or = 0 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.
authors.affiliation: Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P O Box 513, 5600 MB Eindhoven, The Netherlands. l.j.j.v.iersel@tue.nl
authors.forename: Leo
authors.initials: L
authors.lastname: Van Iersel
authors.forename: Steven
authors.initials: S
authors.lastname: Kelk
authors.forename: Matthias
authors.initials: M
authors.lastname: Mnich
mesh_terms: D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D022761:Gene Transfer, Horizontal / Q000235:genetics*; D005828:Genetics, Population; D006801:Humans; D008957:Models, Genetic; D010375:Pedigree; D010802:Phylogeny