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

The agreement metric for labeled binary trees

W Goddard1, E Kubicka, G Kubicki

  • 1Department of Mathematics, University of Pennsylvania, Philadelphia.

Mathematical Biosciences
|October 1, 1994
PubMed
Summary

This study introduces a quadratic algorithm to find the optimal agreement tree between two binary trees by pruning the fewest leaves. This method defines new metrics for comparing tree structures.

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

Lysolecithin as feed additive enhances collagen expression and villus length in the jejunum of broiler chickens.

Poultry science·2017
Same author

Some axiomatic limitations for consensus and supertree functions on hierarchies.

Journal of theoretical biology·2016
Same author

Conservative supertrees.

Systematic biology·2011
Same author

Majority-rule (+) consensus trees.

Mathematical biosciences·2010
Same author

Constructing majority-rule supertrees.

Algorithms for molecular biology : AMB·2010
Same author

Explosions and hot spots in supertree methods.

Journal of theoretical biology·2008

Area of Science:

  • Computer Science
  • Algorithmic Theory
  • Data Structures

Background:

  • Binary trees are fundamental data structures.
  • Pruning involves removing leaves and simplifying tree structures.
  • Agreement trees represent common structures between two trees.

Purpose of the Study:

  • To develop an efficient algorithm for finding agreement trees.
  • To define novel metrics based on agreement trees for tree comparison.

Main Methods:

  • A quadratic algorithm is presented for computing the agreement tree.
  • The algorithm involves pruning leaves from two input binary trees.
  • The goal is to minimize the number of pruned leaves.

Main Results:

Related Experiment Videos

  • An efficient quadratic-time algorithm for agreement tree computation.
  • Definition of two new metrics derived from agreement trees.
  • Demonstration of the algorithm's effectiveness in finding optimal agreement trees.

Conclusions:

  • The proposed quadratic algorithm efficiently finds agreement trees.
  • The new metrics offer a novel way to quantify tree similarity.
  • This work contributes to the field of computational tree analysis.