Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10878-006-9025-5
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
Source: 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. https://doi.org/10.1007/s10878-006-9025-5
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39481
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.

SCOPUSTM   
Citations

3
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

3
checked on Dec 11, 2017

Page view(s)

63
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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