A computationally efficient approximation to the nearest neighbor interchange metric
type: Item
instance of: scholarly article
title: A computationally efficient approximation to the nearest neighbor interchange metric
zbMATH Open document ID: 0563.62033
DOI: 10.1007/BF01890118
author: Edward K. Brown
author: W. H. E. Day
published in: Journal of Classification
publication date: 1984-01-01T00:00:00Z
review text: The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in terms of a simple transformation of binary trees, but its use in nontrivial problems is usually prevented by the absence of a computationally efficient algorithm. Since recent attempts to discover such an algorithm continue to be unsuccessful, we address the complementary problem of designing an approximation to the nni metric. Such an approximation should be well-defined, efficient to compute comprehensible to users, relevant to applications, and a close fit to the nni metric; the challenge, of course, is to compromise these objectives in such a way that the final design is acceptable to users with practical and theoretical orientations. We describe an approximation algorithm that appears to satisfy adequately these objectives.
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 62-04
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3898029
zbMATH Keywords: computationally efficient approximation
zbMATH Keywords: nearest neighbor interchange metric
zbMATH Keywords: algorithm design
zbMATH Keywords: crossover metric
zbMATH Keywords: hierarchical classification
zbMATH Keywords: distance measure
zbMATH Keywords: measure of dissimilarity
zbMATH Keywords: unrooted binary trees
zbMATH Keywords: labeled leaves
MaRDI profile type: Publication
cites work: Q4091421
cites work: Approximating minimum-length-sequence metrics: A cautionary note
cites work: Metrics on spaces of finite trees
cites work: A note on some tree similarity measures
cites work: The complexity of computing metric distances between partitions
cites work: Q5516565
cites work: Q4198056
cites work: Counterexamples in measuring the distance between binary trees
cites work: An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
cites work: A metric and an ordering on sets
cites work: Comparison of phylogenetic trees
cites work: Q4509227
cites work: Q4142698
full work available at URL: https://doi.org/10.1007/bf01890118
OpenAlex ID: W2050297726
description: scientific article; zbMATH DE number 3898029