Some Stuff

At the end of last year, I updated the metadata on some 175,000 or so items in the Cambridge DSpace repository . These were molecules that made up a copy of the ' WWMM ' (the  W orld W ide M olecular M atrix) and they had old 'IChI' identifiers rather than the newer InChI  and InChIKey identifiers. So now - after this update - you can use a search engine to google  … er, search for  compounds by their InChIKey. For example: YMSFBKYTOUKHOI-UHFFFAOYSA-N gives just two results, one of which is from PubChem , and the other is Cambridge Repository. Hilariously, the image from PubChem is this: when the formula is C32H60N4O4. I assume that the connectors in this cycle are just alkane chains, but the layout fails for this kind of 'cyclic lipid peptide' (or whatever it is called!).

So, a student asked me about a homework question that is a sub-problem of the structure generation problem . Basically, it was to count  the number of chemical structures with exactly one  cycle given the elemental formula. Of course, the best solution here is probably to use the Polyá Enumeration Theorem  since all that was asked for was a count (enumeration) of the structures. Naturally, I have a different way to do this - especially since I don't really understand the mathematics of PET enough to implement it. So: The image shows a rough overview of how I might list  all of the structures with a single cycle. It takes a number of necklaces (one shown), and a number of trees, and glues the one to the other in all possible ways. The word ' necklace ' here is specifically the combinatorial object; so  the cyclic sequence CNCNO is the same as CNOCN since you can rotate one to get the other. One tricky decision here is whether to add multiple bonds to the...

So recently I was asked about Király's method for generating all graphs from a degree sequence . While refactoring some of the code that I wrote to do this, I also made some tests. Specifically, coverage tests to check that the generation was actually exhaustive. I know it's redundant, but I have good tools to remove duplicate graphs - or I thought that I did… Here a rough flowchart of the procedure here, starting with a number ('n') that is passed to Dreadnaut (the interface to nAUTy ) to generate graphs: These graphs are grouped by degree sequence, and these degree sequences are fed into the KirályHHGenerator to reconstruct the set of graphs. I think that compare arrow is wrong, but never mind. The point is that the sets should be the same size. They are for n=5,6,7 but not for 8. Oddly enough, however, there are more  in the Király set than in the nAUTy set. The obvious conclusion would be that my duplicate detection is failing - in other words, I am failing...

EDIT : After some more tests, I now realise that this is not really as great a vertex label/descriptor as I thought it was. For example, see these four graphs on 7 vertices that fail to distinguish vertices properly: The first one should have a central vertex in a different class than the other blue vertices. The green class in the second graph should be split, and same for the third graph. And so on. So, in the last post I talked about the ideas of Randić et al for calculating the 'centrality' of vertices in a graph. Interestingly, the numbers calculated for each vertex act as a kind of equivalence class label or vertex invariant. This is similar in many ways to Morgan numbers  (sorry, Egon's post doesn't actually explain them, but they are the sum of degrees across extended neighbourhoods). For example, here is one of the examples from the previous post: With the centrality matrix in the middle, and the 'label' made by sorting the row eleme...

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 ...

There is an interesting book by W. T. Tutte  called ' Graph Theory as I have known it ' which is a cross between a normal mathematical text and a biography. So it's a description of the areas he was interested in, and his theorems. One thing that interested me was the use of a 'twist' operation on cubic graphs like so: Where for the edge between vertices x and y labelled 'A' we reconnect the surrounding edges to form the arrangement on the right hand side. So detach edge D from y and connect it to x, and vice versa with edge C. The lower part of the picture shows what happens for a loop-edge - it transforms to a multi-edge. This operation is used on a family of 'base' graphs looking like this: with the first in the list is a vertexless loop graph - that is, it has no vertices and a single edge. From these base graphs, the twist operation can form any cubic graph. Note that all of U n are cubic with 2n vertices. For example, from U 3 we ...

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...