Thumbnail
Access Restriction
Subscribed

Author Crabtree, John D. ♦ Mehta, Dinesh P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Cheminformatics ♦ Mechanisms
Abstract Automated reaction mapping is a fundamental first step in the analysis of chemical reactions and opens the door to the development of sophisticated chemical kinetic tools. This article formulates the reaction mapping problem as an optimization problem. The problem is shown to be NP-Complete for general graphs. Five algorithms based on canonical graph naming and enumerative combinatoric techniques are developed to solve the problem. Unlike previous formulations based on limited configurations or classifications, our algorithms are uniquely capable of mapping any reaction that can be represented as a set of chemical graphs optimally. This is due to the direct use of Graph Isomorphism as the basis for these algorithms as opposed to the more commonly used Maximum Common Subgraph. Experimental results on chemical and biological reaction databases demonstrate the efficiency of our algorithms.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-02-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 13
Page Count 15
Starting Page 1.15
Ending Page 1.29


Open content in new tab

   Open content in new tab
Source: ACM Digital Library