Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets

Journal article (2015)

Authors

Katharina T Huber University of East Anglia
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
V.L. Moulton University of East Anglia
Celine Scornavacca Université de Montpellier
Taoyang Wu University of East Anglia
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Phylogenetic network Supernetwork NP-hard Trinet Phylogenetic tree Polynomial-time algorithm Exponential-time algorithm Aho algorithm
More Info
expand_more

Published Date

14-09-2015

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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 level-1 phylogenetic network displaying a given set TT of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time 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|))O(3|X|poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.