Please use this identifier to cite or link to this item:
https://doi.org/10.1007/s10878-006-9025-5
DC Field | Value | |
---|---|---|
dc.title | Fast algorithms for computing the tripartition-based distance between phylogenetic networks | |
dc.contributor.author | Nguyen, N.B. | |
dc.contributor.author | Nguyen, C.T. | |
dc.contributor.author | Sung, W.-K. | |
dc.date.accessioned | 2013-07-04T07:42:34Z | |
dc.date.available | 2013-07-04T07:42:34Z | |
dc.date.issued | 2007 | |
dc.identifier.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. https://doi.org/10.1007/s10878-006-9025-5 | |
dc.identifier.issn | 13826905 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/39481 | |
dc.description.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. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/s10878-006-9025-5 | |
dc.source | Scopus | |
dc.subject | Algorithm | |
dc.subject | Phylogenetic network | |
dc.subject | Tripartition-based distance | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1007/s10878-006-9025-5 | |
dc.description.sourcetitle | Journal of Combinatorial Optimization | |
dc.description.volume | 13 | |
dc.description.issue | 3 | |
dc.description.page | 223-242 | |
dc.description.coden | JCOPF | |
dc.identifier.isiut | 000244645900004 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.