Please use this identifier to cite or link to this item: https://doi.org/10.1137/S0097539704446529
Title: Algorithms for combining rooted triplets into a galled phylogenetic network
Authors: Jansson, J. 
Nguyen, N.B.
Sung, W.-K. 
Keywords: Algorithm
Galled network
NP-hardness
Phylogenetic network
Rooted triplet
SN-tree
Issue Date: 2006
Citation: Jansson, J., Nguyen, N.B., Sung, W.-K. (2006). Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM Journal on Computing 35 (5) : 1098-1121. ScholarBank@NUS Repository. https://doi.org/10.1137/S0097539704446529
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 Τ. © 2006 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/39305
ISSN: 00975397
DOI: 10.1137/S0097539704446529
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.