Abstract
Phylogenetic networks are a generalization of evolutionary trees that are used by biologists to represent the evolution of organisms which have undergone reticulate evolution. Essentially, a phylogenetic network is a directed acyclic graph having a unique root in which the leaves are labelled by a given set of species. Recently, some approaches have been developed to construct phylogenetic networks from collections of networks on 2 and 3leaved networks, which are known as binets and trinets, respectively. Here we study in more depth properties of collections of binets, one of the simplest possible types of networks into which a phylogenetic network can be decomposed. More speci_cally, we show that if a collection of level1 binets is compatible with some binary network, then it is also compatible with a binary level1 network. Our proofs are based on useful structural results concerning lowest stable ancestors in networks. In addition, we show that, although the binets do not determine the topology of the network, they do determine the number of reticulations in the network, which is one of its most important parameters. We also consider algorithmic questions concerning binets. We show that deciding whether an arbitrary set of binets is compatible with some network is at least as hard as the wellknown Graph Isomorphism problem. However, if we restrict to level1 binets, it is possible to decide in polynomial time whether there exists a binary network that displays all the binets. We also show that to _nd a network that displays a maximum number of the binets is NPhard, but that there exists a simple polynomialtime 1/3approximation algorithm for this problem. It is hoped that these results will eventually assist in the development of new methods for constructing phylogenetic networks from collections of smaller networks.
Original language  English 

Pages (fromto)  1135–1154 
Number of pages  20 
Journal  Bulletin of Mathematical Biology 
Volume  79 
Issue number  5 
Early online date  6 Apr 2017 
DOIs  
Publication status  Published  May 2017 
Profiles

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
 Centre for Ecology, Evolution and Conservation  Member
 Computational Biology  Member
Person: Research Group Member, Research Centre Member, Academic, Teaching & Research