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 -