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

Comparison of additive trees using circular orders.

V Makarenkov1, B Leclerc

  • 1Département des Sciences Biologiques, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, Québec H3C 3J7, Canada. makarenv@magellan.umontreal.ca

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 12, 2001
PubMed
Summary

This study presents an optimal algorithm for comparing tree topologies using distance matrices. It efficiently calculates the Robinson and Foulds distance, a key measure of tree similarity.

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

Two-team management of vascular injuries concomitant with osteo-articular injuries in 36 patients over six years.

Orthopaedics & traumatology, surgery & research : OTSR·2018
Same author

Endovascular Repair with Cervical Access to Treat a Symptomatic Internal Carotid Artery Aneurysm in a Patient with Neurofibromatosis Type 1.

European journal of vascular and endovascular surgery : the official journal of the European Society for Vascular Surgery·2017
Same author

Melanopsin expression in dopamine-melatonin neurons of the premammillary nucleus of the hypothalamus and seasonal reproduction in birds.

Neuroscience·2010
Same author

Evaluation of a rotary tablet press simulator as a tool for the characterization of compaction properties of pharmaceutical products.

Journal of pharmaceutical sciences·2009
Same author

Photoperiodic modulation of clock gene expression in the avian premammillary nucleus.

Journal of neuroendocrinology·2009
Same author

Curing of aqueous polymeric film coatings: Importance of the coating level and type of plasticizer.

European journal of pharmaceutics and biopharmaceutics : official journal of Arbeitsgemeinschaft fur Pharmazeutische Verfahrenstechnik e.V·2009

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Algorithm Analysis

Background:

  • Species relationships are often modeled using additive tree structures.
  • Tree structures are represented by distance matrices, also known as tree metric matrices.
  • Comparing tree topologies is crucial for understanding evolutionary relationships.

Purpose of the Study:

  • To develop an optimal algorithm for comparing the topology of two trees using their distance matrices.
  • To compute the Robinson and Foulds topologic distance between trees efficiently.
  • To generalize the algorithm for constructing strict consensus trees.

Main Methods:

  • Utilizing circular orders to compare tree topologies represented by distance matrices.
  • Employing circular order tree reconstruction to generate ordered bipartition tables for tree edges.

Related Experiment Videos

  • Comparing bipartition tables to determine the Robinson and Foulds topologic distance.

    • Main Results:

    • An optimal algorithm with O(n^2) time complexity for comparing two n x n distance matrices was developed.
    • The algorithm accurately computes the Robinson and Foulds topologic distance.
    • A generalized algorithm for constructing strict consensus trees in O(kn^2) time was established.

    Conclusions:

    • The developed algorithm provides an efficient and optimal method for assessing tree similarity using distance matrices.
    • Circular order-based tree reconstruction is effective for topological comparisons.
    • The generalized algorithm offers a significant advancement for constructing strict consensus trees from multiple unrooted trees.