So much to do, so little time

Trying to squeeze sense out of chemical data

Archive for the ‘Ullman’ tag

Faster Substructure Search in the CDK

with 8 comments

The CDK uses the UniversalIsomorphismTester to perform graph and subgraph isomorphism. However it’s not very efficient and this shows when performing substructure searches over large collections. A quick test where I compared the CDK code to OpenBabel’s obgrep showed that the CDK is nearly forty times slower than OpenBabel. Improvements in this code will enhance SMARTS matching, pharmacophore searching, fingerprinting and descriptors.

The Ullman algorithm is a well known method to perform subgraph isomorphism and even though more than thirty years old, is still used in many applications. I implemented this algorithm, based on the C++ implementation in VFLib, to see whether it’d do better than the method currently used in the CDK.

Read the rest of this entry »

Written by Rajarshi Guha

September 19th, 2008 at 4:12 am