
Cam Thach Nguyen,
Nguyen Bao Nguyen and
WingKin Sung. Fast Algorithms for computing the Tripartitionbased Distance between Phylogenetic Networks. In JCO, Vol. 13(3), 2007. Keywords: distance between networks, phylogenetic network, phylogeny, tripartition distance. Note: http://dx.doi.org/10.1007/s1087800690255.
Toggle abstract
"Consider two phylogenetic networks N and N′ of size n. The tripartitionbased distance finds the proportion of tripartitions which are not shared by N and N′. This distance is proposed by Moret et al. (2004) and is a generalization of RobinsonFoulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an O(min {kn log n, n log n + hn} time algorithm to compute this distance, where h is the number of hybrid nodes in N and N′ while k is the maximum number of hybrid nodes among all biconnected components in N and N′. Note that k ≪ h ≪ n in a phylogenetic network. In addition, we propose algorithms for comparing galledtrees, which are an important, biological meaningful special case of phylogenetic network. We give an O(n)time algorithm for comparing two galledtrees. We also give an O(n + kh)time algorithm for comparing a galledtree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. © Springer Science+Business Media, LLC 2007."



Cam Thach Nguyen,
Nguyen Bao Nguyen,
WingKin Sung and
Louxin Zhang. Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem. In TCBB, Vol. 4(3):394402, 2007. Keywords: explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.pdf.



Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):10981121, 2006. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf.
Toggle 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 leaflabeled 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 NPhard 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 polynomialtime 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."





Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SODA05, Pages 349358, 2005. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://portal.acm.org/citation.cfm?id=1070481.



Trinh N. D. Huynh,
Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265280 of LNCS, springer, 2005. Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction. Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.





