Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

On the nearest neighbour interchange distance between evolutionary trees

M Li1, J Tromp, L Zhang

  • 1Department of Computer Science, University of Waterloo, Ontario, Canada.

Journal of Theoretical Biology
|October 21, 1996
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Phenotyping patients with a low-flow, low-gradient aortic stenosis and a preserved ejection fraction undergoing TAVI.

ESC heart failure·2026
Same author

Towards personalised follow-up care in ovarian cancer using online remote PROMs monitoring: a study protocol of a feasibility trial.

BMJ open·2026
Same author

Hallmarks of cancer in patients with heart failure: data from BIOSTAT-CHF.

Cardio-oncology (London, England)·2024
Same author

SEIS: Insight's Seismic Experiment for Internal Structure of Mars.

Space science reviews·2019
Same author

Novel endotypes in heart failure: effects on guideline-directed medical therapy.

European heart journal·2018
Same author

Cardio-Oncology: Progress in Diagnosis and Treatment of Cardiac Dysfunction.

Clinical pharmacology and therapeutics·2017
Same journal

Evolution of quantitative traits: exploring the ecological, social and genetic bases of adaptive polymorphism.

Journal of theoretical biology·2026
Same journal

The male-biased sex ratio in humans and its role in the transition from promiscuity to pair bonding.

Journal of theoretical biology·2026
Same journal

Quantifying the counter-intuitive effects of vaccination by coupling the transmission dynamics of COVID-19 and the evolution of human behaviors.

Journal of theoretical biology·2026
Same journal

An integrative model of FGF2-induced signaling and muscle cell proliferation.

Journal of theoretical biology·2026
Same journal

A hybrid reaction-diffusion and mechanical stimulus model for mandibular bone remodeling under chewing and vibratory loading.

Journal of theoretical biology·2026
Same journal

Integrated tick management strategies in fragmented peridomestic environments.

Journal of theoretical biology·2026
See all related articles

We improved the upper bound for evolutionary tree distances using nearest neighbour interchange (NNI) operations. New findings also introduce an approximation algorithm for tree transformations and disprove prior theorems.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Graph Theory

Background:

  • Evolutionary trees model species relationships.
  • The Nearest Neighbour Interchange (NNI) distance quantifies differences between trees.
  • Previous bounds on NNI distance were less efficient.

Purpose of the Study:

  • Improve the upper bound for NNI distance calculation.
  • Disprove specific theorems related to tree distance decomposition.
  • Develop an efficient approximation algorithm for tree transformations.

Main Methods:

  • Analyzing free 3-trees with labeled leaves.
  • Applying mathematical proofs to derive new distance bounds.
  • Developing and testing a polynomial-time approximation algorithm.

Related Experiment Videos

Main Results:

  • Improved NNI distance upper bound from 4n log n to n log n.
  • Provided a counterexample to theorems suggesting decomposability of distance problems.
  • Developed an O(log n) approximation algorithm for tree transformations.

Conclusions:

  • The new upper bound offers a more efficient theoretical limit for NNI distance.
  • The decomposability of tree distance problems is more complex than previously thought.
  • The approximation algorithm provides a practical method for estimating tree transformation lengths.