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

Katharina Huber, L. van Iersel, Vincent Moulton, Celine Scornavacca, Taoyang Wu

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)
5 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)173-200
JournalAlgorithmica
Volume77
Issue number1
Early online date14 Sep 2015
DOIs
Publication statusPublished - Jan 2017

Keywords

  • phylogenetic tree
  • phylogenetic network
  • polynomial-time algorithm
  • exponential-time algorithm
  • NP-hard
  • supernetwork
  • trinet

Cite this