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

Recrafting the neighbor-joining method.

Thomas Mailund1, Gerth S Brodal, Rolf Fagerberg

  • 1Bioinformatics Research Center, University of Aarhus, Denmark. mailund@birc.dk

BMC Bioinformatics
|January 21, 2006
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

Finding Pathways in Reaction Networks Guided by Energy Barriers Using Integer Linear Programing.

Molecular informatics·2026
Same author

A Sensitivity Analysis Methodology for Rule-Based Stochastic Chemical Systems.

Journal of chemical information and modeling·2026
Same author

Computational approaches in chemical space exploration for carbon fixation pathways.

NPJ systems biology and applications·2026
Same author

SynKit: A Graph-Based Python Framework for Rule-Based Reaction Modeling and Analysis.

Journal of chemical information and modeling·2025
Same author

KGG: Knowledge-Guided Graph Self-Supervised Learning to Enhance Molecular Property Predictions.

Journal of chemical information and modeling·2025
Same author

Finding Thermodynamically Favorable Pathways in Chemical Reaction Networks Using Flows in Hypergraphs and Mixed-Integer Linear Programming.

Journal of chemical information and modeling·2025
Same journal

OpenIMC: an open-source platform for analyzing single-cell and spatial proteomics by imaging mass cytometry.

BMC bioinformatics·2026
Same journal

NAP: an open source pipeline for cross-domain microbiome profiling using Nanopore sequencing-derived amplicon data.

BMC bioinformatics·2026
Same journal

SurvGME: an R package for survival analysis with graphical and measurement error models.

BMC bioinformatics·2026
Same journal

SimMapNet: a Bayesian framework for gene regulatory network inference using gene ontology similarities as external hint.

BMC bioinformatics·2026
Same journal

Dual channel drug-drug interactions extraction based on cross attention.

BMC bioinformatics·2026
Same journal

FeSseqdb: a curated sequence-level database and interpretable machine learning framework for identifying iron-sulfur proteins.

BMC bioinformatics·2026
See all related articles

New algorithms accelerate phylogenetic tree construction using the neighbor-joining method. These optimized techniques achieve O(n2) performance, significantly speeding up analyses for medium-sized datasets.

Area of Science:

  • Computational Biology
  • Bioinformatics

Background:

  • The neighbor-joining method is a standard algorithm for phylogenetic tree construction.
  • Its canonical formulation results in a Theta(n3) time complexity.

Purpose of the Study:

  • To present novel techniques for accelerating the neighbor-joining method.
  • To develop algorithms that produce identical phylogenetic trees to the canonical method.

Main Methods:

  • Development of new algorithms for neighbor-joining.
  • Empirical evaluation on distance matrices from the Pfam alignment collection.
  • Comparison with the QuickTree tool.

Main Results:

  • The proposed algorithms achieve a best-case running time of O(n2), with a worst-case of O(n3).

Related Experiment Videos

  • Empirical results demonstrate Theta(n2) performance on the Pfam dataset.
  • Significant speed-up observed compared to the canonical neighbor-joining method and QuickTree.

    • Conclusions:

    • The developed algorithms offer substantial performance improvements for phylogenetic tree construction.
    • Speed-up is noticeable even for medium-sized biological datasets.