On Distances between Phylogenetic Trees (Extended Abstract)

) B. DasGupta X. He y T. Jiang z M. Li x J. Tromp -- L. Zhang k Abstract Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [18] or from different genes [12] in the study of molecular evolution. Comparing these trees to find their similarities (e.g. agreement or consensus) and dissimilarities, i.e. distance, is thus an important issue in computational molecular biology. The nearest neighbor interchange (nni) distance [25, 24, 32, 4, 5, 3, 16, 17, 19, 29, 20, 21, 23] and the subtree-transfer distance [12, 13, 15] are two major distance metrics that have been proposed and extensively studied for different reasons. Despite their many appealing aspects such as simplicity and sensitivity to tree topologies, computing these distances has remained very challenging. This article studies the complexity and efficient approximation algorithms for computing the nni distance and a natural extension of..