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

Efficiently computing the Robinson-Foulds metric.

Nicholas D Pattengale1, Eric J Gottlieb, Bernard M E Moret

  • 1Department of Computer Science, University of New Mexico, Albuquerque, NM, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|August 19, 2007
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

Genomic and Synthetic Biology Digital Biosecurity.

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing·2021
Same author

Decentralized genomics audit logging via permissioned blockchain ledgering.

BMC medical genomics·2020
Same author

Sequence-Based Synteny Analysis of Multiple Large Genomes.

Methods in molecular biology (Clifton, N.J.)·2017
Same author

New Genome Similarity Measures based on Conserved Gene Adjacencies.

Journal of computational biology : a journal of computational molecular cell biology·2017
Same author

NEMo: An Evolutionary Model With Modularity for PPI Networks.

IEEE transactions on nanobioscience·2017
Same author

On Computing Breakpoint Distances for Genomes with Duplicate Genes.

Journal of computational biology : a journal of computational molecular cell biology·2016
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

This study introduces a fast, approximate method for comparing phylogenetic trees, significantly speeding up analyses. The new FastRF tool offers a scalable solution for large-scale phylogenetic comparisons.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Algorithm Design

Background:

  • The Robinson-Foulds (RF) metric is standard for phylogenetic tree comparison.
  • Linear time algorithms like Day's are too slow for large datasets.
  • Efficient tree comparison is crucial for evolutionary biology.

Purpose of the Study:

  • Develop a sublinear time approximation algorithm for the RF metric.
  • Improve the scalability of phylogenetic tree comparisons.
  • Provide an open-source tool for practical phylogenetic analysis.

Main Methods:

  • A randomized approximation scheme using sublinear-space tree embeddings.
  • Application of the Johnson-Lindenstrauss lemma for rapid vector norm approximation.
  • Development of an efficient tree embedding procedure.

Related Experiment Videos

Main Results:

  • A (1 + epsilon) approximation of the RF metric in sublinear time with high probability.
  • An efficient embedding procedure resolving an open research question.
  • Performance improvements to Day's exact algorithm via approximation techniques.

Conclusions:

  • The new randomized approach offers a significant speedup for large-scale phylogenetic tree comparisons.
  • FastRF provides a practical, open-source tool for researchers.
  • The study unifies edge-based tree algorithms and clarifies implementation tradeoffs.