Non-shared edges and nearest neighbor interchanges revisited
The number of non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogemes. 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(n log n). Based on this result, we can speed up the existing approximation algorithm for the NNI distance from O(n(2)) time to O(n log n) time. (C) 2004 Elsevier B.V. All rights reserved.
non-shared edge distance algorithms nni distance phylogenetic tree