ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 29 Sep 2022 21:16:56 GMT2022-09-29T21:16:56Z5011- Fast algorithms for computing the tripartition-based distance between phylogenetic networkshttps://scholarbank.nus.edu.sg/handle/10635/41502Title: Fast algorithms for computing the tripartition-based distance between phylogenetic networks
Authors: Nguyen, N.B.; Thach Nguyen, C.; Sung, W.-K.
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 < < in & 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-Verlag Berlin Heidelberg 2005.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/415022005-01-01T00:00:00Z