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

作者：孙婉怡; 何险峰; 温浩

来源：计算机与应用化学, 2009, (12): 1539-1542.

DOI：10.16866/j.com.app.chem2009.12.004

• 分子结构检索
• VF2
• GMA
• 偏序 molecular structure searching
• partial order

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

• 单位
  中国科学院研究生院; 中国科学院过程工程研究所; 多相复杂系统国家重点实验室