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
Source: 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.

SCOPUSTM   
Citations

41
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

37
checked on Nov 18, 2017

Page view(s)

55
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


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