Binets: Fundamental Building Blocks for Phylogenetic Networks

Leo van Iersel, Vincent Moulton, Eveline de Swart, Taoyang Wu

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)
25 Downloads (Pure)

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 3-leaved 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 specifically, we show that if a collection of level-1 binets is compatible with some binary network, then it is also compatible with a binary level-1 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 well-known graph isomorphism problem. However, if we restrict to level-1 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 find a network that displays a maximum number of the binets is NP-hard, but that there exists a simple polynomial-time 1/3-approximation 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 languageEnglish
Pages (from-to)1135-1154
Number of pages20
JournalBulletin of Mathematical Biology
Volume79
Issue number5
DOIs
Publication statusPublished - 6 Apr 2017

Keywords

  • Algorithm
  • Binet
  • Phylogenetic network
  • Reticulate evolution
  • Subnetwork

Fingerprint Dive into the research topics of 'Binets: Fundamental Building Blocks for Phylogenetic Networks'. Together they form a unique fingerprint.

Cite this