Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ipl.2004.04.003
Title: Non-shared edges and nearest neighbor interchanges revisited
Authors: Hon, W.-K.
Kao, M.-Y.
Lam, T.-W.
Sung, W.-K. 
Yiu, S.-M.
Keywords: Algorithms
NNI distance
Non-shared edge distance
Phylogenetic tree
Issue Date: 2004
Citation: Hon, W.-K., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M. (2004). Non-shared edges and nearest neighbor interchanges revisited. Information Processing Letters 91 (3) : 129-134. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ipl.2004.04.003
Abstract: The number of non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edge distance is also a building block for approximating a more sophisticated measure called the nearest neighbor interchange (NNI) distance. In this paper, we give the first sub-quadratic time algorithm for computing the non-shared edge distance, whose running time is O(nlogn). Based on this result, we can speed up the existing approximation algorithm for the NNI distance from O(n2) time to O(nlogn) time. © 2004 Elsevier B.V. All rights reserved.
Source Title: Information Processing Letters
URI: http://scholarbank.nus.edu.sg/handle/10635/39214
ISSN: 00200190
DOI: 10.1016/j.ipl.2004.04.003
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


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