Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41177
Title: Algorithms for combining rooted triplets into a galled phylogenetic network
Authors: Jansson, J. 
Nguyen, N.B.
Sung, W.-K. 
Issue Date: 2005
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
URI: http://scholarbank.nus.edu.sg/handle/10635/41177
Appears in Collections:Staff Publications

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

Page view(s)

62
checked on Dec 16, 2017

Google ScholarTM

Check


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