Algorithms for combining rooted triplets into a galled phylogenetic network

Jesper Andreas Jansson, Nguyen Bao Nguyen, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

8 Citations (Scopus)

Abstract

This paper considers the problem of determining whether a given set T of rooted triplets can be merged without conflicts into a galled phylogenetic network, and if so, constructing such a network. When the input T is dense, we solve the problem in O(|T|) time, which is optimal since the size of the input is Θ(|T|). In comparison, the previously fastest algorithm for this problem runs in O(|T|2) time. Next, we prove that the problem becomes NP-hard if extended to non-dense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set T of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883· |T| of the rooted triplets in T. 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 T.
Original languageEnglish
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)
Pages349-358
Number of pages10
Publication statusPublished - 1 Jul 2005
Externally publishedYes
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: 23 Jan 200525 Jan 2005

Conference

ConferenceSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period23/01/0525/01/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this