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

How many isomers of C4H11N are there?

One of the most popular queries that lands people at this blog is about the isomers of C4H11N - which I suspect may be some kind of organic chemistry question on student homework. In any case, this post will describe how to find all members of a small space like this by hand rather than using software.

Firstly, lets connect all the hydrogens to the heavy atoms (C and N, in this case). For example:


Now eleven hydrogens can be distributed among these five heavy atoms in various ways. In fact this is the problem of partitioning a number into a list of other numbers which I've talked about before. These partitions and (possible) fragment lists are shown here:


One thing to notice is that all partitions have to have 5 parts - even if one of those parts is 0. That's not strictly a partition anymore, but never mind. The other important point is that some of the partitions lead to multiple fragment lists - [3, 3, 2, 2, 1] could have a CH+NH2 or an NH+CH2.

The final step is to connect u…

Havel-Hakimi Algorithm for Generating Graphs from Degree Sequences

A degree sequence is an ordered list of degrees for the vertices of a graph. For example, here are some graphs and their degree sequences:



Clearly, each graph has only one degree sequence, but the reverse is not true - one degree sequence can correspond to many graphs. Finally, an ordered sequence of numbers (d1 >= d2 >= ... >= dn > 0) may not be the degree sequence of a graph - in other words, it is not graphical.

The Havel-Hakimi (HH) theorem gives us a way to test a degree sequence to see if it is graphical or not. As a side-effect, a graph is produced that realises the sequence. Note that it only produces one graph, not all of them. It proceeds by attaching the first vertex of highest degree to the next set of high-degree vertices. If there are none left to attach to, it has either used up all the sequence to produce a graph, or the sequence was not graphical.



The image above shows the HH algorithm at work on the sequence [3, 3, 2, 2, 1, 1]. Unfortunately, this produce…

Generating Trees

Tree generation is a well known (and solved!) problem in computer science. On the other hand, it's pretty important for various problems - in my case, making tree-like fusanes. I'll describe here the slightly tortuous route I took to make trees.

Firstly, there is a famous theorem due to Cayley that the number of (labelled) trees on n vertices is nn - 2 which can be proved by using Prüfer sequences. That's all very well, you might well say - but what does all this mean?

Well, it's not all that important, since there is a fundamental problem with this approach : the difference between a labelled tree and an unlabelled tree. There are many more labeled trees than unlabeled :


There is only one unlabeled tree on 3 vertices, but 3 labeled ones
this is easy to check using the two OEIS sequences for this : A000272 (labeled) and A000055 (unlabeled). For n ranging from 3 to 8 we have [3, 16, 125, 1296, 16807, 262144] labeled trees and [1, 2, 3, 6, 11, 23] unlabeled ones. Only 23 …