Skip to main content

CDK Signature implementation now in review

What is it?

I have written about them quite a bit, but here is a quick summary : signatures are a little like SMILES, but also somewhat like HOSE codes. They are a description of the connectivity of a molecule, or an atom in the molecule. A more detailed description can be found in these papers by Faulon et al: [1], [3] or in this blog post by me.

The java implementation of this algorithm is a collaboration between Lars Carlsson (who wrote a C++ version) and me (who ported this version to java). However, I was also influenced by my previous attempt at a port from the c implementation by Faulon's group. There is an online service for using their program called "sscan" here. It also deals with stereochemistry.

What is it used for?

So, what can be done with all this new code? Here are some possibilities:
  • Smiles-like canonical strings that represent molecules. Note that signatures are considerably longer than smiles, but are guaranteed to work for cuneane, and indeed a broad range of graphs.
  • As with HOSE-codes (which can describe molecule connectivity up to different 'spheres') signatures can vary in height. Practically, this means an atom's environment can be described with different levels of detail.
  • Due to the canonisation of the structure, the core algorithm can be used to give a canonical labelling of the structure, which can be useful for atom-atom mapping of isomorphic structures.
  • Calculating signatures for all atoms of a molecule produces a partition of the atoms into sets of equivalent positions. This is useful for a variety of analyses of a molecule's graph structure.
Obviously, there are advantages and disadvantages of using signatures for these applications, compared to existing techniques. I am not sure, for example, of speed differences in using signatures to get a canonical representation.

How do you use it?

The MoleculeSignature class is a wrapper around an instance of an IMolecule and provides several useful methods, many of them from the base class AbstractGraphSignature. For example:
IMolecule thiazole = MoleculeFactory.makeThiazole();
MoleculeSignature moleculeSignature = new MoleculeSignature(thiazole);
System.out.println(moleculeSignature.toCanonicalString());
// Result = "[C](=[C]([N](=[C,0]))[S]([C,0]))"

This is the canonical signature for the whole molecule. To get this, canonical signatures are made for each atom, and the canonical one from the list is returned. To get all the signatures - rather, the equivalance classes (or 'orbits') - use the calculateOrbits method like this:

MoleculeSignature moleculeSignature = new MoleculeSignature(MoleculeFactory.makeQuinone());
for (Orbit orbit : moleculeSignature.calculateOrbits()) {
System.out.println(orbit);
}
which gives this output (the 'makeQuinone' method makes 1,4-benzoquinone:

[O](=[C]([C](=[C]([C,0](=[O])))[C](=[C]([C,0])))) [0, 7]
[C]([C](=[C]([C,0](=[O])))[C](=[C]([C,0]))=[O]) [1, 4]
[C](=[C]([C]([C,0]=[O]))[C]([C](=[C,0])=[O])) [2, 3, 5, 6]
which tells us that the two oxygen atoms ([0, 7]) are in the same orbit, as are the carbons attached to them, and that the other four are in another orbit. I have written about more complex examples of orbits : in C60 or in other fullerenes or in some other regular graphs. In practice, most chemicals will have automorphism partitions that are (nearly) discrete.

So, finally, an example of how to get the canonical labelling of a graph:
MoleculeSignature moleculeSignature =
new MoleculeSignature(MoleculeFactory.makeCyclobutadiene());
System.out.println(Arrays.toString(moleculeSignature.getCanonicalLabels()));
which gives "[0, 3, 2, 1]" - essentially this is the permutation which gives a canonical arrangement of atoms.

Non-CDK implementations?

There are other chemistry projects other than the CDK, and it should be fairly easy to make a mychemlib.MoleculeSignature by subclassing signature.AbstractGraphSignature (and similarly for AtomSignature/AbstractVertexSignature). All the concrete classes need do is tell its superclass about the underlying molecule graph - getVertexCount, getConnected - and the MoleculeSignature has to act as a factory for the concrete AtomSignature instances via getSignatureForVertex.

The signature project is on github and has some of the maven machinery for building/testing/packaging. There are a couple of 'toy' implementations for chemicals and simple (mathematical) graphs.

Any feedback, suggestions, and so on are welcome. I am also happy to help with other people's implementations in the form of code or just hints. Enjoy!

Comments

Asad said…
Hi Egon, this looks very interesting. I would like to test this with some more examples at my end :-)

Popular posts from this blog

Common Vertex Matrices of Graphs

There is an interesting set of papers out this year by Milan Randic et al (sorry about the accents - blogger seems to have a problem with accented 'c'...). I've looked at his work before here.

[1] Common vertex matrix: A novel characterization of molecular graphs by counting
[2] On the centrality of vertices of molecular graphs

and one still in publication to do with fullerenes. The central idea here (ho ho) is a graph descriptor a bit like path lengths called 'centrality'. Briefly, it is the count of neighbourhood intersections between pairs of vertices. Roughly this is illustrated here:


For the selected pair of vertices, the common vertices are those at the same distance from each - one at a distance of two and one at a distance of three. The matrix element for this pair will be the sum - 2 - and this is repeated for all pairs in the graph. Naturally, this is symmetric:


At the right of the matrix is the row sum (∑) which can be ordered to provide a graph invarian…

Generating Dungeons With BSP Trees or Sliceable Rectangles

So, I admit that the original reason for looking at sliceable rectangles was because of this gaming stackoverflow question about generating dungeon maps. The approach described there uses something called a binary split partition tree (BSP Tree) that's usually used in the context of 3D - notably in the rendering engine of the game Doom. Here is a BSP tree, as an example:



In the image, we have a sliced rectangle on the left, with the final rectangles labelled with letters (A-E) and the slices with numbers (1-4). The corresponding tree is on the right, with the slices as internal nodes labelled with 'h' for horizontal and 'v' for vertical. Naturally, only the leaves correspond to rectangles, and each internal node has two children - it's a binary tree.

So what is the connection between such trees and the sliceable dual graphs? Well, the rectangles are related in exactly the expected way:


Here, the same BSP tree is on the left (without some labels), and the slicea…

Signatures with user-defined edge colors

A bug in the CDK implementation of my signature library turned out to be due to the fact that the bond colors were hard coded to just recognise the labels {"-", "=", "#" }. The relevant code section even had an XXX above it!

Poor show, but it's finally fixed now. So that means I can handle user-defined edge colors/labels - consider the complete graph (K5) below:

So the red/blue colors here are simply those of a chessboard imposed on top of the adjacency matrix - shown here on the right. You might expect there to be at least two vertex signature classes here : {0, 2, 4} and {1, 3} where the first class has vertices with two blue and two red edges, and the second has three blue and two red.

Indeed, here's what happens for K4 to K7:

Clearly even-numbered complete graphs have just one vertex class, while odd-numbered ones have two (at least?). There is a similar situation for complete bipartite graphs:

Although I haven't explored any more of these…