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. 
Nguyen, N.B.
Sung, W.-K. 
Keywords: Algorithm
Galled network
Phylogenetic network
Rooted triplet
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.
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
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.


checked on Sep 30, 2022


checked on Sep 30, 2022

Page view(s)

checked on Sep 22, 2022

Google ScholarTM



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