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

Katharina T Huber, Leo van Iersel, Vincent Lynmore Moulton, Celine Scornavacca, Taoyang Wu

Research output: Contribution to journalArticleScientificpeer-review

18 Citations (Scopus)

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 TT 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|))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.
Original languageEnglish
Pages (from-to)173-200
Number of pages28
JournalAlgorithmica: an international journal in computer science
Volume77
Issue number1
DOIs
Publication statusPublished - 14 Sep 2015

Keywords

  • Phylogenetic tree
  • Phylogenetic network
  • Polynomial-time algorithm
  • Exponential-time algorithm
  • NP-hard
  • Supernetwork
  • Trinet
  • Aho algorithm

Fingerprint

Dive into the research topics of 'Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets'. Together they form a unique fingerprint.

Cite this