Please use this identifier to cite or link to this item:
Title: Fast algorithms for computing the tripartition-based distance between phylogenetic networks
Authors: Nguyen, N.B.
Nguyen, C.T.
Sung, W.-K. 
Keywords: Algorithm
Phylogenetic network
Tripartition-based distance
Issue Date: 2007
Citation: Nguyen, N.B., Nguyen, C.T., Sung, W.-K. (2007). Fast algorithms for computing the tripartition-based distance between phylogenetic networks. Journal of Combinatorial Optimization 13 (3) : 223-242. ScholarBank@NUS Repository.
Abstract: Consider two phylogenetic networks N and N′ of size n. The tripartition-based 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 Robinson-Foulds 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 galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an O(n)-time algorithm for comparing two galled-trees. We also give an O(n + kh)-time algorithm for comparing a galled-tree 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.
Source Title: Journal of Combinatorial Optimization
ISSN: 13826905
DOI: 10.1007/s10878-006-9025-5
Appears in Collections:Staff Publications

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


checked on Oct 26, 2020


checked on Oct 26, 2020

Page view(s)

checked on Oct 25, 2020

Google ScholarTM



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