Skip to Main content Skip to Navigation
Journal articles

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

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. B Leo van Iersel
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Celine Scornavacca <>
Submitted on : Wednesday, December 18, 2019 - 3:41:35 PM
Last modification on : Wednesday, October 14, 2020 - 4:13:25 AM
Long-term archiving on: : Thursday, March 19, 2020 - 9:52:43 PM


Publisher files allowed on an open archive




Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca, Taoyang Wu. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets. Algorithmica, Springer Verlag, 2017, 77 (1), pp.173-200. ⟨10.1007/s00453-015-0069-8⟩. ⟨hal-02154892⟩



Record views


Files downloads