Print Email Facebook Twitter Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets Title Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets Author Huber, K.T. Van Iersel, L.J.J. Moulton, V. Scornavacca, C. Wu, T. Faculty Electrical Engineering, Mathematics and Computer Science Department Delft Institute of Applied Mathematics Date 2015-09-14 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 phylogenetic networks. Subject phylogenetic treephylogenetic networkpolynomial-time algorithmexponential-time algorithmNP-hardsupernetworktrinetaho algorithm To reference this document use: http://resolver.tudelft.nl/uuid:e38c8ed4-19e3-4dda-b984-f91f69a6df31 Publisher Springer ISSN 0178-4617 Source https://doi.org/10.1007/s00453-015-0069-8 Source Algorithmica, 2015 Part of collection Institutional Repository Document type journal article Rights © 2015 The Author(s)This article is published with open access at Springerlink.com Files PDF vanIersel_2015.pdf 839.2 KB Close viewer /islandora/object/uuid:e38c8ed4-19e3-4dda-b984-f91f69a6df31/datastream/OBJ/view