Subject: Re: CCL:W:Substructure matching

From: Christoph Steinbeck <c.steinbeck|at|uni-koeln.de>
Date: Sat, 23 Apr 2005 18:02:10 +0200

Hi  Brian,

check out our open source Java library "The Chemistry Development Kit 
(CDK)" [1]. It lives at http://cdk.sourceforge.net.

The class UniversalIsomorphismChecker can do full graph matching, 
subgraph searches and Maximum Common Subgraph (MCS) matching.
On demand, it provides you with a map of matching atoms or bonds in the 
two graphs under inspection.

The CDK comes with an extended set of unit tests which are good examples 
of how to do certain thing. Below, you also find a small code example 
> from the tests, showing how to get a subgraph atom map [2].

Cheers,

Chris

[1] Steinbeck, C.; Han, Y. Q.; Kuhn, S.; Horlacher, O.; Luttmann, E. et 
al. The Chemistry Development Kit (CDK): An open-source Java library for 
chemo- and bioinformatics. Journal of Chemical Information and Computer 
Sciences 2003, 43, 493-500. http://dx.doi.org/10.1021/ci025584y

[2] Example for getting a subgraph atom map. Note that this is a
test case. The test makes two molecules, indole and pyrrole, in a 
predefined way. The arrays result1 and result2 contain the expected 
(known) mapping of the atom numbers in pyrrole to the atom numbers in 
indole. The assertions at the end check if the test leads to the 
expected result.

public void testGetSubgraphAtomsMaps() throws java.lang.Exception
{
	int[] result1 = {6, 5, 7, 8, 0};
	int[] result2 = {3, 4, 2, 1, 0};
	
	AtomContainer mol = MoleculeFactory.makeIndole();
	AtomContainer frag1 = MoleculeFactory.makePyrrole();
	HueckelAromaticityDetector.detectAromaticity(mol);
	HueckelAromaticityDetector.detectAromaticity(frag1);
	List list = UniversalIsomorphismTester.getSubgraphAtomsMaps(mol, frag1);
	List first = (List)list.get(0);
	for (int i = 0; i < first.size(); i++) {
		RMap rmap = (RMap)first.get(i);
		assertEquals(rmap.getId1(), result1[i]);
		assertEquals(rmap.getId2(), result2[i]);
	}
}

-- 
Priv. Doz. Dr. Christoph Steinbeck (c.steinbeck|at|uni-koeln.de)
Head of the Research Group for Molecular Informatics
Cologne University BioInformatics Center (http://www.cubic.uni-koeln.de)
Z|lpicher Str. 47, 50674 Cologne
Tel: +49(0)221-470-7426   Fax: +49 (0) 221-470-7786

What is man but that lofty spirit - that sense of enterprise.
... Kirk, "I, Mudd," stardate 4513.3..

Sean, , OBrien wrote:
> I am searching for some software that will help me to identify the atoms within a molecule that match a query substructure. For example I wish to find which atoms belong to an imidazole ring. The aim is to extract the matching substructure while keeping the original atomic coordinates.
> 
> I know that several substructure matching routines exist, and some are even freely available but I haven't found any that return the identity of the matching atoms. Some return the whole molecule or a tally of how many times the substructure is present. They obviously "know" which atoms match but I am having difficulty identifying them. Similarly matching strings in SMILES doesn't return the initial atom ids.
> 
> I would be very grateful for any routines that do this, or that can be modified for this purpose,