Abstract
Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NPhard for trinets but polynomialtime solvable for binets. Moreover, we show that the problem is still polynomialtime 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)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted 1 phylogenetic networks.
Original language  English 

Pages (fromto)  173200 
Number of pages  28 
Journal  Algorithmica 
Volume  77 
Issue number  1 
Early online date  14 Sep 2015 
DOIs  
Publication status  Published  Jan 2017 
Keywords
 phylogenetic tree
 phylogenetic network
 polynomialtime algorithm
 exponentialtime algorithm
 NPhard
 supernetwork
 trinet
Profiles

Katharina Huber
 School of Computing Sciences  Associate Professor
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Norwich Epidemiology Centre  Member
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Taoyang Wu
 School of Computing Sciences  Lecturer in Computing Sciences
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research