  
Cam Thach Nguyen,
Nguyen Bao Nguyen and
Wing-Kin Sung. Fast Algorithms for computing the Tripartition-based 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/s10878-006-9025-5.
Toggle 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."
@Article{NNS2007,
AUTHOR = {Nguyen, Cam Thach and Nguyen, Nguyen Bao and Sung, Wing-Kin},
TITLE = {Fast Algorithms for computing the Tripartition-based Distance between Phylogenetic Networks},
YEAR = {2007},
JOURNAL = {JCO},
VOLUME = {13},
NUMBER = {3},
URL = {http://dx.doi.org/10.1007/s10878-006-9025-5},
NOTE = { http://dx.doi.org/10.1007/s10878-006-9025-5},
ANNOTE = {BIBUPDATE : 20071118},
KEYWORDS = {distance between networks, phylogenetic network, phylogeny, tripartition distance} } |
- forked on GitHub.