SwiFT: an index structure for reduced graph descriptors in virtual screening and clustering.

A reduced graph descriptor represents molecules by small node-labeled graphs. They allow fast similarity calculation, while retaining the overall arrangement of functional groups. The feature tree as an example of this descriptor type abstracts a molecule by a node-labeled, unrooted tree. One available algorithm for pairwise feature tree comparison is the match-search algorithm, which matches the subtrees of two feature trees on each other and therefore creates an alignment. In this work, we document the extension to reuse partial results on the global level of the whole feature tree data set where a high number of identical subtrees exists. The method is based on indexing all occurring subtrees in a data set. On the basis of this index, the similarity value between every subtree combination has to be computed only once. While calculating identical similarities, this approach leads to a substantial reduction in run time by up to 80% and can be used in a parallel computation environment. The search tree built for indexing can also be used to identify duplicated feature trees.