A novel method for optimizing subgraph isomorphism algorithms such that 2-D stereochemical descriptors are efficiently processed in a molecule or reaction retrieval system


Anthony P Cook1, A Peter Johnson1, and Daniel G Thomas2. (1) School of Chemistry, University of Leeds, Leeds LS2 9JT, United Kingdom, (2) BCI Ltd, 46 Uppergate Rd, Stannington, Sheffield S6 6BX, United Kingdom
Subgraph isomorphism algorithms are an essential part of molecule and reaction retrieval systems. As well as solving queries that express molecular constitution, an additional requirement is that the absolute or relative configuration of stereocentres expressed in the query must also be considered when determining a graph match. In the algorithms we present in this paper, this problem has been addressed in three ways: a) the development of a useful and generic stereochemical descriptor that simplifies the comparison of most types of stereochemical geometry; b) the incorporation of the comparison of the stereochemical descriptor step directly into the graph isomorphism algorithm; c) a new feature that uses a “best first” planning algorithm that dynamically determines the most efficient order that query atoms and stereo descriptors are tried in the subgraph isomorphism algorithm.

Herman Skolnik Award Symposium
8:15 AM-11:45 AM, Tuesday, August 24, 2004 Pennsylvania Convention Center -- 110A&B, Oral

Division of Chemical Information

The 228th ACS National Meeting, in Philadelphia, PA, August 22-26, 2004