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

An exact algorithm for the geodesic distance between phylogenetic trees.

Anne Kupczok1, Arndt von Haeseler, Steffen Klaere

  • 1Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, Veterinary University of Vienna, Austria.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|July 18, 2008
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

Genus-wide Homologous Recombination of Tail Fibers Maintains Tailocin Diversity in Pectobacterium.

Genome biology and evolution·2026
Same author

Phylogenetic support of pebS as a phage-exclusive auxiliary metabolic gene.

FEMS microbiology letters·2026
Same author

Machine learning can distinguish orphans that have resulted from sequence divergence beyond recognition.

Bioinformatics advances·2026
Same author

Genomic GC bias correction improves species abundance estimation from metagenomic data.

Nature communications·2025
Same author

Advances and challenges in understanding evolution through genome comparison: meeting report of the European Molecular Biology Organization (EMBO) lecture course "Evolutionary and Comparative Genomics".

Bioinformatics advances·2025
Same author

GTestimate: improving relative gene expression estimation in scRNA-seq using the Good-Turing estimator.

GigaScience·2025
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

We developed an exact algorithm to compute the geodesic distance between phylogenetic trees. A fast linear-time approximation, the cone path, accurately estimates this distance for biological gene trees.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Bioinformatics

Background:

  • Phylogenetic trees represent evolutionary relationships.
  • Quantifying differences between trees is crucial for evolutionary studies.
  • The space of phylogenetic trees can be geometrically represented, implying metrics like geodesic distance.

Purpose of the Study:

  • To present an exact algorithm for computing the geodesic distance between weighted phylogenetic trees.
  • To evaluate the accuracy of a linear-time approximation (cone path) compared to the geodesic distance.
  • To provide a software implementation (GeoMeTree) for these computations.

Main Methods:

  • Developed an exact algorithm to compute the geodesic distance in the space of weighted phylogenetic trees.
Keywords:
Robinson-Foulds distancecone pathgeodesic pathphylogenytree space

Related Experiment Videos

  • Implemented the algorithm in Python (GeoMeTree).
  • Applied the algorithm and approximation to 118 metazoan gene trees.

    • Main Results:

    • The exact algorithm computes the geodesic distance, though with worst-case exponential time complexity.
    • For biologically relevant trees, computations are fast.
    • The cone path, computable in linear time, serves as a good approximation of the geodesic distance.

    Conclusions:

    • The geodesic distance provides a robust metric for comparing phylogenetic trees.
    • The cone path offers an efficient and accurate approximation for large-scale phylogenetic analyses.
    • GeoMeTree facilitates the computation and approximation of tree distances in evolutionary research.