Access Restriction

Author Kouri, Tina M. ♦ Mehta, Dinesh P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Cheminformatics ♦ Reaction mechanisms
Abstract Automated reaction mapping is an important tool in cheminformatics where it may be used to classify reactions or validate reaction mechanisms. The reaction mapping problem is known to be NP-Hard and may be formulated as an optimization problem. In this article, we present four algorithms that continue to obtain optimal solutions to this problem, but with significantly improved runtimes over the previous Constructive Count Vector (CCV) algorithm. Our algorithmic improvements include (i) the use of a fast (but not 100% accurate) canonical labeling algorithm, (ii) name reuse (i.e., storing intermediate results rather than recomputing), and (iii) an incremental approach to canonical name computation. The time to map the reactions from the Kegg/Ligand database previously took over 2 days using CCV, but now it takes fewer than 4 hours to complete. Experimental results on chemical reaction databases demonstrate our 2-CCV FDN MS algorithm usually performs over fifteen times faster than previous automated reaction mapping 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 2013-11-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 18
Page Count 32
Starting Page 2.1
Ending Page 2.32

Open content in new tab

   Open content in new tab
Source: ACM Digital Library