Fischer J Robert, Rarey Matthias
Center for Bioinformatics Hamburg, University of Hamburg, Bundesstrasse 43, D-20146 Hamburg, Germany.
J Chem Inf Model. 2007 Jul-Aug;47(4):1341-53. doi: 10.1021/ci700007b. Epub 2007 Jun 14.
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.
简化的图描述符通过带节点标签的小图来表示分子。它们允许快速进行相似性计算，同时保留官能团的整体排列。作为这种描述符类型的一个示例，特征树通过一个带节点标签的无根树来抽象一个分子。一种用于成对特征树比较的可用算法是匹配搜索算法，该算法使两个特征树的子树相互匹配，从而创建一个比对。在这项工作中，我们记录了在整个特征树数据集的全局级别上重用部分结果的扩展，在该数据集中存在大量相同的子树。该方法基于对数据集中出现的所有子树进行索引。基于此索引，每个子树组合之间的相似性值只需计算一次。在计算相同的相似性时，这种方法可将运行时间大幅减少多达80%，并且可用于并行计算环境。为索引而构建的搜索树还可用于识别重复的特征树。
