Step-by-step calculation of all maximum common substructures through a constraint satisfaction based algorithm

被引：30

作者：

García, GC ^{[1
]}

Ruiz, IL ^{[1
]}

Gómez-Nieto, MA ^{[1
]}

机构：

[1] Univ Cordoba, Dept Comp & Numer Anal, E-14071 Cordoba, Spain

来源：

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES | 2004年 / 44卷 / 01期

关键词：

D O I：

10.1021/ci034167y

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

In this paper we propose a new algorithm for subgraph isomorphism based on the representation of molecular structures as colored graphs and the representation of these graphs as vectors in n-dimensional spaces. The presented process that obtains all maximum common substructures is based on the solution of a constraint satisfaction problem defined as the common m-dimensional space (m less than or equal to n) in which the vectors representing the matched graphs can be defined.

引用

页码：30 / 41

页数：12

共 22 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BUNKE H, 2002, LECT NOTES COMPUTER, V2396, P123, DOI DOI 10.1007/3-540-70659-3_12

[3] MCSS - A NEW ALGORITHM FOR PERCEPTION OF MAXIMAL COMMON SUBSTRUCTURES AND ITS APPLICATION TO NMR SPECTRAL STUDIES .2. APPLICATIONS [J].

CHEN, LG ;

ROBIEN, W .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1992, 32 (05) :507-510

[4] STRUCTURAL MATCHING IN COMPUTER VISION USING PROBABILISTIC RELAXATION [J].

CHRISTMAS, WJ ;

KITTLER, J ;

PETROU, M .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1995, 17 (08) :749-764

[5]

CTADELLA J, 2000, P 5 INT SEM REL METH, P72

[6]

DEJONG KA, 1989, GENETIC ALGORITHMS, P124

[7]

Durand PJ, 1999, INTERNET J CHEM, V2

[8]

EPPTEIN D, 1999, J GRAPH ALGORITHMS A, V3, P1

[9]

Garcia G. C., 2003, Proceedings of the International Conference of Computational Methods in Sciences and Engineering 2003 (ICCMSE 2003), P156

[10] INCREASING TREE-SEARCH EFFICIENCY FOR CONSTRAINT SATISFACTION PROBLEMS [J].

HARALICK, RM ;

ELLIOTT, GL .

ARTIFICIAL INTELLIGENCE, 1980, 14 (03) :263-313

← 1 2 3 →