一种新的分子二维子结构检索算法
A new algorithm for 2-dimentional molecular structure searching
查看参考文献22篇
|
文摘
|
本文针对分子二维子结构检索问题,比较分析图同构算法中具有代表性的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. |
|
来源
|
计算机与应用化学
,2009,26(12):1539-1542 【核心库】
|
|
关键词
|
分子结构检索
;
VF2
;
GMA
;
偏序
|
|
地址
|
中国科学院过程工程研究所, 多相复杂系统国家重点实验室, 北京, 100190
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1001-4160 |
|
学科
|
化学;化学工业 |
|
文献收藏号
|
CSCD:3803718
|
参考文献 共
22
共2页
|
|
1.
Cvetkovic D M.
Spectra of Graph:Theory and Applications（3rdedition）,1995
|
被引
1
次
|
|
|
|
|
2.
Garey M R.
Computers and Intraetability:A Guide to the Theory of NP-Completeness,1979
|
被引
1
次
|
|
|
|
|
3.
Ullmann J R. An algorithm for subgraph isomorphism.
J Assoc Comput Machin,1976,23:31-42
|
被引
97
次
|
|
|
|
|
4.
Xu J. GMA:A generic match algorithm for structural homomorphism,isomorphism,and maximal common substructure match and its application.
J Chem lnf Comput Sei,1996,36:25-34
|
被引
19
次
|
|
|
|
|
5.
Wang T. EMCSS:A new method for maximal common substructure search.
Journal of Chemical Information and Computer Sciences,1997,37:828-834
|
被引
6
次
|
|
|
|
|
6.
Wang T. 3DFS:A new 3D flexible searching system for use in drug design.
J Chem lnf Comput Sci,1998,37:71-77
|
被引
6
次
|
|
|
|
|
7.
Robert D B. A hyperstructure model for chemical structure handling:generation and atom-by-atom searching of hyperstructures.
J Chem Info Comput Sci,1992,32:522-531
|
被引
1
次
|
|
|
|
|
8.
Brown D R. Matching two-dimensional chemical graphs using genetic algorithms.
J Chem lnf Comput Sci,1994(34):63-70
|
被引
1
次
|
|
|
|
|
9.
Cordelia L P. An Efficient Algorithm for the Inexact Matching of ARG Graphs Using a Contextual Transformational Model.
Proc 13th ICPR,1996:180-184
|
被引
1
次
|
|
|
|
|
10.
Foggia P. Introducing generalized attributed relational graphs(GARG's) as prototypes of ARG's.
Proc.2nd IAPR Workshop on Graph-based Representations,1999
|
被引
2
次
|
|
|
|
|
11.
Cordelia L P. Graph matching:A fast algorithm and its evaluation.
Proc,of the 14th International Conference on Pattern Recognition,1998
|
被引
1
次
|
|
|
|
|
12.
Cordelia L P. Subgraph transformations for the inexact matching of attributed relational graphs.
COMPUTING,1998,12:43-52
|
被引
1
次
|
|
|
|
|
13.
Cordella L P. Performance evaluation of the VF graph matching algnrithm.
Proc,10th ICIAP,1999
|
被引
1
次
|
|
|
|
|
14.
Foggia P. An improved algorithm for matching large grapgs.
Proc of the 3rd IAPR-TC-15 International Workshop on Graph-baaed Representations,2001
|
被引
1
次
|
|
|
|
|
15.
Foggia P. A database of graphs for isomorphism and sub-graph isomorphism benchmarking.
Proc,of the 3rd IAPR-TC-15 International Workshop on Graph-basod Representations,2001
|
被引
1
次
|
|
|
|
|
16.
Foggia P. A performance comparison of five algorithms.
Graph-based Representation in Pattern Recognition,2001:176-188
|
被引
1
次
|
|
|
|
|
17.
MDL Information Systems Inc.
http://www.mdli.com/
|
被引
2
次
|
|
|
|
|
18.
.
MDL CTfile formats
|
被引
1
次
|
|
|
|
|
19.
王亭. 受指导的二维结构搜索算法.
计算机与应用化学,1997,14(1):23-26
|
被引
5
次
|
|
|
|
|
20.
李欣. 基于VF2算法的分子二维子结构检索.
计算机与应用化学,2007,24(11):1551-1554
|
被引
5
次
|
|
|
|
|
了解气象卫星更多信息，请访问