ON THE NEAREST-NEIGHBOR INTERCHANGE DISTANCE BETWEEN EVOLUTIONARY TREES

We present some new results on a well-known distance measure between e volutionary trees. The trees we consider are free 3-trees having n lea ves labeled 0,..., n-1 (representing species), and n-2 internal nodes of degree 3. The distance between two trees is the minimum number of n earest neighbour interchange (NNI) operations required to transform on e into the other. First, we improve an upper bound on the nni-distance between two arbitrary n-node trees from 4n log n (Culik & Wood, 1982, Inf. Pro. Letts. 15, 39-42) to n log n. Second, we present a countere xample disproving several theorems in (Waterman & Smith, 1978, J. theo r. Biol. 73, 789-800). Roughly speaking, finding an equal partition be tween two trees does not imply decomposability of the distance finding problem. Third, we present a polynomial-time approximation algorithm that, given two trees, finds a transformation between them of length O (log n) times their distance. We also present some results of computat ions we performed on small size trees. (C) 1996 Elsevier Science Limit ed