Algorithms for Pairwise Comparison of Feature Trees

Once a Feature Tree can be created from a molecule, the question arises of how to compare two Feature Trees. Using Eq. (1), we are able to compare two individual Feature Tree nodes. Owing to the additivity of the features stored at a node, we can also compare two sets of Feature Tree nodes. This is done by adding the features over all nodes within a set and applying Eq. (1) again. Obviously, we can also compare two complete Feature Trees in this way we just add all features in the two trees and apply Eq. (1). We call such a comparison level-0, because no division of the tree into pieces has been performed. Level-0 comparisons closely resemble the way linear descriptors work. If we assume for a moment that all components of a linear descriptor are additive and can be computed for each building block individually (such as the volume descriptor), adding the feature values over all Feature Tree nodes will create the linear descriptor. 

Once a topology-maintaining matching M of subtrees has been calculated, an overall similarity value can be derived. For each match, we calculate the similarity value as already described above for a level-0 comparison. For the whole matching, a size-weighted average over all matches gives the final similarity value 

The parameter m allows the similarity value to be tuned towards global or partial similarity. To illustrate the effect, let us assume that molecule A might be fully contained in B and T=size(A) = size(B)/2 100% of molecule A will be matched to 50% of B with similarity value sim(m) = 1, resulting in a numerator T. If co= 1, the denominator is 2T resulting in an overall similarity value of 0.5. If, however, co=0, the denominator is T, resulting in an overall similarity value of 1.0. 

---