Keywords and Synonyms
Comparison of phylogenies ; Network models of evolution
Problem Definition
In this chapter, the authors state results on some transformation based distances for evolutionary trees. Several distance models for evolutionary trees have been proposed in the literature. Among them, the best known is perhaps the nearest neighbor interchange (nni) distance introduced independently in [10] and [9]. The authors will focus on the nni distance and a closely related distance called the subtree-transfer distance originally introduced in [5,6]. Several papers that involved DasGupta, He, Jiang, Li, Tromp and Zhang essentially showed the following results:
-
A correspondence between the nni distance and the linear-cost subtree-transfer distance on unweighted trees;
-
Computing the nni distance is NP-hard, but admits a fixed-parameter tractability and a logarithmic ratio approximation algorithms;
-
A 2-approximation algorithm for the linear‐cost subtree‐transfer distance on weighted...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J.: On the linear-cost subtree-transfer distance. Algorithmica 25(2), 176–195 (1999)
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On distances between phylogenetic trees, 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 427–436 (1997)
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Wang, L., Zhang, L.: Computing Distances between Evolutionary Trees. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization. Kluwer Academic Publishers, Norwell, 2, 35–76 (1998)
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On Computing the Nearest Neighbor Interchange Distance. In: Du, D.Z., Pardalos, P.M., Wang, J. (eds.) Proceedings of the DIMACS Workshop on Discrete Problems with Medical Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Am. Math. Soc. 55, 125–143 (2000)
Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Math. Biosci. 98, 185–200 (1990)
Hein, J.: A heuristic method to reconstruct the history of sequences subject to recombination. J. Mol. Evol. 36, 396–405 (1993)
Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discret. Appl. Math. 71, 153–169 (1996)
Kuhner, M., Felsenstein, J.: A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol. Biol. Evol. 11(3), 459–468 (1994)
Moore, G.W., Goodman, M., Barnabas, J.: An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets. J. Theor. Biol. 38, 423–457 (1973)
Robinson, D.F.: Comparison of labeled trees with valency three. J Combinator. Theory Series B 11, 105–119 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L. (2008). Nearest Neighbor Interchange and Related Distances. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_256
Download citation
DOI: https://doi.org/10.1007/978-0-387-30162-4_256
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30770-1
Online ISBN: 978-0-387-30162-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering