 
Leo van Iersel and
Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ALG, Vol. 60(2):207-235, 2011.
Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic.
Note: http://dx.doi.org/10.1007/s00453-009-9333-0.
Toggle abstract
"A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations 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 with smallest possible level in time O(|T| k+1), if k is a fixed upper bound on the level of the network. © 2009 The Author(s)."
@Article{IerselKelk2011b,
AUTHOR = {van Iersel, Leo and Kelk, Steven},
TITLE = {Constructing the Simplest Possible Phylogenetic Network from Triplets},
YEAR = {2011},
JOURNAL = {ALG},
VOLUME = {60},
NUMBER = {2},
PAGES = {207-235},
URL = {http://dx.doi.org/10.1007/s00453-009-9333-0},
NOTE = { http://dx.doi.org/10.1007/s00453-009-9333-0},
KEYWORDS = {explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic} } |
- forked on GitHub.