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. |
|Source:||Jansson, J.,Nguyen, N.B.,Sung, W.-K. (2005). Algorithms for combining rooted triplets into a galled phylogenetic network. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 349-358. ScholarBank@NUS Repository.|
|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.|
|Source Title:||Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 16, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.