一种新的分子二维子结构检索算法

A new algorithm for 2-dimentional molecular structure searching

本文针对分子二维子结构检索问题,比较分析图同构算法中具有代表性的VF2法和GMA法。VF2法的数据结构精巧,能有效降低内存开销,但其在图匹配时没有保存提问结构的偏序,造成大量重复计算,影响匹配效率。GMA法则利用偏序的不变性,预先计算并保存偏序,进而指导图匹配过程。本文将GMA法的偏序行走策略应用于VF2法,保留VF2法的遍历规则和数据结构,用标准C++语言改进的结构检索算法能提供正确的检索结果,效率更高。本文还通过实例说明了VF2法和GMA法各自偏序的计算过程,指出2种算法的图遍历规则的差异。

Two typical graph isomorphism algorithms VF2 and GMA are analyzed and discussed for 2-dimentional molecular structure search. VF2 has a very low memory requirement due to its specialized data structure, but there is still quite a lot of double counting for VF2 doesn＇t save the partial order obtained by traveling the query structure. GMA takes advantage of the invariance of partial order and applies a partial order pre-computing strategy to the graph matching. In this paper, standard C ＋ ＋ language is used to implement algorithms with the advantages of VF2 on traversal rules and data structure, and those of GMA on partial order walking strategy. The improved algorithms operate correctly and exhibit much higher retrieval efficiency. Traversal rules of VF2 and GMA are also compared by demonstrating the partial order computing process of VF2 and GMA.