A GENERAL-METHOD FOR TREE-COMPARISON BASED ON SUBTREE SIMILARITY AND ITS USE IN A TAXONOMIC DATABASE

A number of metrics for comparing the branching structure of trees hav e been used as important tools in the quantitative analysis of evoluti onary trees. Less attention has been paid to developing a general comp arison methodology for different leaf-labeled N-trees such as classifi cation trees and various types of dendrograms. In this paper a method for measuring overall similarity based on subtree similarity is propos ed. Association coefficients can be used to measure the similarity bet ween each pair of subtrees in two trees, and an algorithm called the ' webbing matrix method' is outlined in order to calculate the overall s imilarity in this method. In addition, the use of this method for tree searching and tree comparison in a taxonomic database is introduced. (C) 1997 Elsevier Science Ireland Ltd.