On the Nearest Neighbour Interchange Distance Between Evolutionary Trees

We present some new results on a well-known distance measure between evolutionary trees. The trees we consider are free 3-trees havingnleaves labeled 0,...,n- 1 (representing species), andn- 2 internal nodes of degree 3. The distance between two trees is the minimum number of nearest neighbour interchange (NNI) operations required to transform one into the other. First, we improve an upper bound on the nni-distance between two arbitraryn-node trees from 4nlogn(Culik & Wood, 1982,Inf. Pro. Letts.15,39–42) tonlogn. Second, we present a counterexample disproving theorems in (Waterman & Smith, 1978,J. theor. Biol.73,789–800). Roughly speaking, finding an equal partition between 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 lengthO(logn) times their distance. We also present some results of computations we performed on small size trees.