Please use this identifier to cite or link to this item:
|Title:||Algorithms for combining rooted triplets into a galled phylogenetic network||Authors:||Jansson, J.
|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.