Binets: fundamental building blocks for phylogenetic networks

Van Iersel, Leo, Moulton, Vincent, de Swart, Eveline and Wu, Taoyang (2017) Binets: fundamental building blocks for phylogenetic networks. Bulletin of Mathematical Biology, 79 (5). 1135–1154. ISSN 0092-8240

[img]
Preview
PDF (Binets_BullMathBiol) - Published Version
Available under License Creative Commons Attribution.

Download (761kB) | Preview

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 speci_cally, 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 _nd 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.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Pure Connector
Date Deposited: 16 Feb 2017 19:15
Last Modified: 08 Nov 2020 00:46
URI: https://ueaeprints.uea.ac.uk/id/eprint/62639
DOI: 10.1007/s11538-017-0275-4

Actions (login required)

View Item View Item