| 一种新的分子二维子结构检索算法 |
| |
| 引用本文： | 孙婉怡,何险峰,温浩.一种新的分子二维子结构检索算法[J].计算机与应用化学,2009,26(12). |
| |
| 作者姓名： | 孙婉怡 何险峰 温浩 |
| |
| 作者单位： | 1. 中国科学院过程工程研究所多相复杂系统国家重点实验室,北京,100190;中国科学院研究生院,北京,100049
2. 中国科学院过程工程研究所多相复杂系统国家重点实验室,北京,100190 |
| |
| 摘 要： | 本文针对分子二维子结构检索问题,比较分析图同构算法中具有代表性的VF2法和GMA法。VF2法的数据结构精巧,能有效降低内存开销,但其在图匹配时没有保存提问结构的偏序,造成大量重复计算,影响匹配效率。GMA法则利用偏序的不变性,预先计算并保存偏序,进而指导图匹配过程。本文将GMA法的偏序行走策略应用于VF2法,保留VF2法的遍历规则和数据结构,用标准C++语言改进的结构检索算法能提供正确的检索结果,效率更高。本文还通过实例说明了VF2法和GMA法各自偏序的计算过程,指出2种算法的图遍历规则的差异。
|
| 关 键 词： | 分子结构检索 VF2 GMA 偏序 |
A new algorithm for 2-dimentional molecular structure searching |
| |
| Sun Wanyi,He Xianfeng,Wen Hao.A new algorithm for 2-dimentional molecular structure searching[J].Computers and Applied Chemistry,2009,26(12). |
| |
| Authors: | Sun Wanyi He Xianfeng Wen Hao |
| |
| Affiliation: | 1;2;1.State Key Laboratory of Multiphase Complex System;Institute of Process Engineering;Chinese Academy of Sciences;Beijing;100190;China;2.Graduate University of the Chinese Academy of Sciences;100049;China |
| |
| Abstract: | 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.CMA 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 imple... |
| |
| Keywords: | molecular structure searching VF2 GMA partial order |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
