Over the weekend, I cobbled together some components that I've been developing for a while (the past four years in fact) to make a molecule structure generator. As described in recent posts, OMG is one new available solution; now here is a proof-of-concept for a quite similar one.
So what are the differences? Well, firstly OMG uses NautY to check candidates for canonicity while this implementation uses signatures, so is currently slower. The major difference, though is the algorithm. While OMG uses bond-augmentation of a parent structure to make children, this one uses atom-augmentation. Here is a small example (augmenting ethane):
Of course, these are only the immediate children of the C-C parent; for OMG the unique, canonical ones will themselves be augmented further until they are the right size and have the correct number of hydrogens. The atom-augmentation algorithm, by contrast, produces a next generation with exactly one new atom, but a different number of bonds.
The slightly tricky part was to generate all possible combinations of bonds to add. There might be many ways to do this, but the way I picked was this:
Here we are augmenting the C=C(O)C structure on the left to get a cyclobuten-1-ol on the right. First, the atoms that can be added to are calculated using the bond-order sum (bos) : only atoms that are 'undersaturated' can have new bonds. Then all possible multisets are generated, up to the max degree of the added atom (so: {{1,1,1,1}, {1, 1, 2}, {2, 2}...). Finally these multisets are converted to 'bond order arrays' which are just a list of bond orders to attach to each atom.
For the child-filtering approach used in OMG, the algorithm is much the same. For the alternative 'symmetry' approach, the automorphism group of the parent is used to select the bond order array that is minimal in its orbit. Either way, a set of non-redundant children is produced which can then be tested for canonicity.
At the moment, this implementation has had a small amount of testing on alkene (CnH2n) structures to check that it gets the numbers right, but more rigorous testing on different series is necessary. Then some optimisations could be tried to get the time closer to OMG (at least).
So what are the differences? Well, firstly OMG uses NautY to check candidates for canonicity while this implementation uses signatures, so is currently slower. The major difference, though is the algorithm. While OMG uses bond-augmentation of a parent structure to make children, this one uses atom-augmentation. Here is a small example (augmenting ethane):
The slightly tricky part was to generate all possible combinations of bonds to add. There might be many ways to do this, but the way I picked was this:
Here we are augmenting the C=C(O)C structure on the left to get a cyclobuten-1-ol on the right. First, the atoms that can be added to are calculated using the bond-order sum (bos) : only atoms that are 'undersaturated' can have new bonds. Then all possible multisets are generated, up to the max degree of the added atom (so: {{1,1,1,1}, {1, 1, 2}, {2, 2}...). Finally these multisets are converted to 'bond order arrays' which are just a list of bond orders to attach to each atom.
For the child-filtering approach used in OMG, the algorithm is much the same. For the alternative 'symmetry' approach, the automorphism group of the parent is used to select the bond order array that is minimal in its orbit. Either way, a set of non-redundant children is produced which can then be tested for canonicity.
At the moment, this implementation has had a small amount of testing on alkene (CnH2n) structures to check that it gets the numbers right, but more rigorous testing on different series is necessary. Then some optimisations could be tried to get the time closer to OMG (at least).
Comments
any chance of providing a compiled JAR file and readme.txt
with examples for the command line such as java -jar AMG.jar C6H6
Of course SDF file generation would be important, to validate
with INCHIKeys.
Cheers
Tobias
I'll give it a go, although at the moment the element handling is very limited, although there are no technical barriers to expanding it. It also could be better tested, and better optimized, and (as you rightly point out) better documented.
gilleain