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."
