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

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

[thumbnail of final]
PDF (final) - Accepted Version
Download (445kB) | Preview


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 (, 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: 21 Oct 2022 01:12
DOI: 10.1007/s00453-015-0069-8

Actions (login required)

View Item View Item