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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.