Algorithms for combining rooted triplets into a galled phylogenetic network

Jesper Andreas Jansson, Nguyen Bao Nguyen, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

49 Citations (Scopus)

Abstract

This paper considers the problem of determining whether a given set Τ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input Τ is dense, we solve the problem in O(|Τ|) time, which is optimal since the size of the input is Θ(|Τ|). In comparison, the previously fastest algorithm for this problem runs in O(|Τ|2) time. We also develop an optimal O(|Τ|)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with Τ, where L is the set of leaf labels in Τ, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set Τ of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 ·|Τ| of the rooted triplets in Τ. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in Τ.
Original languageEnglish
Pages (from-to)1098-1121
Number of pages24
JournalSIAM Journal on Computing
Volume35
Issue number5
DOIs
Publication statusPublished - 25 Oct 2006
Externally publishedYes

Keywords

  • Algorithm
  • Galled network
  • NP-hardness
  • Phylogenetic network
  • Rooted triplet
  • SN-tree

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this