2014/11/25 by Katharina Huber, Leo van Iersel, Huber, Katharina +7 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Populations and Evolution (q-bio.PE) #cs.DS #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1411.6804
arxiv created 2014/11/25 · arxiv updated 2014/11/26
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 set X of taxa, 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.