Binets: fundamental building blocks for phylogenetic networks

Van Iersel, Leo, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, de Swart, Eveline and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2017) Binets: fundamental building blocks for phylogenetic networks. Bulletin of Mathematical Biology, 79 (5). 1135–1154. ISSN 0092-8240

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
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Related URLs:	https://arxiv.org/abs/1701.08995
Depositing User:	Pure Connector
Date Deposited:	16 Feb 2017 19:15
Last Modified:	10 Dec 2024 01:29
URI:	https://ueaeprints.uea.ac.uk/id/eprint/62639
DOI:	10.1007/s11538-017-0275-4

Downloads

Actions (login required)

View Item