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 :-)
23 June 2010 at 12:38
Post a Comment

Popular posts from this blog

Adamantane, Diamantane, Twistane

After cubane, the thought occurred to look at other regular hydrocarbons. If only there was some sort of classification of chemicals that I could use look up similar structures. Oh wate, there is . Anyway, adamantane is not as regular as cubane, but it is highly symmetrical, looking like three cyclohexanes fused together. The vertices fall into two different types when colored by signature: The carbons with three carbon neighbours (degree-3, in the simple graph) have signature (a) and the degree-2 carbons have signature (b). Atoms of one type are only connected to atoms of another - the graph is bipartite . Adamantane connects together to form diamondoids (or, rather, this class have adamantane as a repeating subunit). One such is diamantane , which is no longer bipartite when colored by signature: It has three classes of vertex in the simple graph (a and b), as the set with degree-3 has been split in two. The tree for signature (c) is not shown. The graph is still bipartite accordin
2 comments
Read more

Király's Method for Generating All Graphs from a Degree Sequence

After posting about the Hakimi-Havel  theorem, I received a nice email suggesting various relevant papers. One of these was by Zoltán Király  called " Recognizing Graphic Degree Sequences and Generating All Realizations ". I have now implemented a sketch of the main idea of the paper, which seems to work reasonably well, so I thought I would describe it. See the paper for details, of course. One focus of Király's method is to generate graphs efficiently , by which I mean that it has polynomial delay. In turn, an algorithm with 'polynomial delay' takes a polynomial amount of time between outputs (and to produce the first output). So - roughly - it doesn't take 1s to produce the first graph, 10s for the second, 2s for the third, 300s for the fourth, and so on. Central to the method is the tree that is traversed during the search for graphs that satisfy the input degree sequence. It's a little tricky to draw, but looks something like this: At the top
5 comments
Read more

General Graph Layout : Putting the Parts Together

An essential tool for graph generation is surely the ability to draw graphs. There are, of course, many methods for doing so along with many implementations of them. This post describes one more (or perhaps an existing method - I haven't checked). Firstly, lets divide a graph up into two parts; a) the blocks, also known as ' biconnected components ', and b) trees connecting those blocks. This is illustrated in the following set of examples on 6 vertices: Trees are circled in green, and blocks in red; the vertices in the overlap between two circles are articulation points. Since all trees are planar, a graph need only have planar blocks to be planar overall. The layout then just needs to do a tree layout  on the tree bits and some other layout on the embedding of the blocks. One slight wrinkle is shown by the last example in the image above. There are three parts - two blocks and a tree - just like the one to its left, but sharing a single articulation point. I had
2 comments
Read more