Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Huber, Katharina, van Iersel, L., Moulton, Vincent, Scornavacca, Celine and Wu, Taoyang (2017) Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. Algorithmica, 77 (1). pp. 173-200. ISSN 0178-4617

[img]
Preview
PDF (final) - Submitted Version
Download (445kB) | Preview

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 T 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|)) 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 1 phylogenetic networks.

Item Type: Article
Additional Information: © The Author(s) 2015 This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Uncontrolled Keywords: phylogenetic tree,phylogenetic network,polynomial-time algorithm,exponential-time algorithm,np-hard,supernetwork,trinet
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: Pure Connector
Date Deposited: 19 Oct 2015 10:00
Last Modified: 22 Jul 2020 00:23
URI: https://ueaeprints.uea.ac.uk/id/eprint/54720
DOI: 10.1007/s00453-015-0069-8

Actions (login required)

View Item View Item