Constructing the Simplest Possible Phylogenetic Network from Triplets

• DOI: 10.1007/s00453-009-9333-0
• Publication Date: 2009-07-06T14:45:11Z
• Authors: Leo van Iersel; Steven Kelk
• Keywords: Tree (set theory); Theory of computation

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 simplest possible consistent with input set T, where T contains at least one tree on three leaves (a triplet) for each combination taxa. To quantify complexity both total number and per biconnected component, called level network. We give polynomial-time algorithms constructing level-1 respectively level-2 minimum (if exists). In addition, show if precisely equal to triplets some network, then can construct smallest in time O(|T|k+1), k fixed upper bound