@inproceedings{7030ca6c3bd44ebcb7948fc0e805363d,
title = "Constructing the simplest possible phylogenetic network from triplets",
abstract = "A phylogenetic network is a directed acyclic graph that visualises an evolutionary history containing so-called reticulations such as recombinations, hybridisations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network, which minimises both the level and the total number of reticulations, in time O(|T|k+1), if k is a fixed upper bound on the level.",
author = "{Iersel, van}, L.J.J. and S.M. Kelk",
year = "2008",
doi = "10.1007/978-3-540-92182-0_43",
language = "English",
isbn = "978-3-540-92181-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "472--483",
editor = "S.H. Hong and H. Nagamochi and T. Fukunaga",
booktitle = "Algorithms and Computation (Proceedings 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008)",
address = "Germany",
}