A general method for tree-comparison based on subtree similarity and its use in a taxonomic database

Area of Science:

• Computational Biology
• Data Science
• Phylogenetics

Background:

• Quantitative analysis of evolutionary trees relies on branching structure metrics.
• A general comparison methodology for diverse leaf-labeled N-trees (e.g., classification trees, dendrograms) is lacking.
• Existing methods primarily focus on evolutionary trees, neglecting broader applications.

Purpose of the Study:

• To propose a general method for measuring overall similarity between different types of leaf-labeled N-trees.
• To introduce a novel approach based on subtree similarity for tree comparison.
• To demonstrate the utility of this method in tree searching and comparison within taxonomic databases.

Main Methods:

• The proposed method measures overall tree similarity by assessing pairwise subtree similarities.
• Association coefficients are employed to quantify the similarity between corresponding subtrees.
• The 'webbing matrix method' algorithm is outlined for calculating overall tree similarity.

Main Results:

• The study presents a quantitative method for comparing diverse N-tree structures.
• The webbing matrix method provides a systematic way to calculate overall tree similarity.
• The proposed methodology is applicable to tree searching and comparison in taxonomic databases.

Conclusions:

• A general and effective method for comparing various leaf-labeled N-trees has been developed.
• The subtree similarity approach, utilizing association coefficients and the webbing matrix method, offers a robust solution.
• This methodology has practical implications for organizing and querying taxonomic data.