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

Huber, Katharina, van Iersel, Leo, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, Scornavacca, Celine and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2017) Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. Algorithmica, 77 (1). pp. 173-200. ISSN 0178-4617

Preview

PDF (final) - Accepted 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
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 > 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
Depositing User:	Pure Connector
Date Deposited:	19 Oct 2015 10:00
Last Modified:	09 Oct 2024 13:33
URI:	https://ueaeprints.uea.ac.uk/id/eprint/54720
DOI:	10.1007/s00453-015-0069-8

Downloads

Actions (login required)

View Item