TY - JOUR
T1 - Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
AU - Huber, Katharina T
AU - van Iersel, Leo
AU - Moulton, Vincent Lynmore
AU - Scornavacca, Celine
AU - Wu, Taoyang
PY - 2015/9/14
Y1 - 2015/9/14
N2 - Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set TT of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3|X|poly(|X|))O(3|X|poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.
AB - Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set TT of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3|X|poly(|X|))O(3|X|poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.
KW - Phylogenetic tree
KW - Phylogenetic network
KW - Polynomial-time algorithm
KW - Exponential-time algorithm
KW - NP-hard
KW - Supernetwork
KW - Trinet
KW - Aho algorithm
UR - http://resolver.tudelft.nl/uuid:e38c8ed4-19e3-4dda-b984-f91f69a6df31
U2 - 10.1007/s00453-015-0069-8
DO - 10.1007/s00453-015-0069-8
M3 - Article
SN - 0178-4617
VL - 77
SP - 173
EP - 200
JO - Algorithmica: an international journal in computer science
JF - Algorithmica: an international journal in computer science
IS - 1
ER -