1
$\begingroup$

Graph Theory isn't my strongest area in mathematics and I wish to implement it - so the simpler the description, the better. Thank you for any responses in advance.

The problem: I wish to compare chemical molecules or specifically reactive groups in a chemical molecule. These molecules are stored as adjacency lists of nodes and edges, however the ordering of the nodes is arbitrary, i.e. I must use the actual connectivity information itself. Nodes obviously also contain an atom type, e.g hydrogen, carbon, etc. - and edges can be single bonds, double bonds etc. - so effectively there is "type information" there too. (Writing an adjacency matrix does not work as nodes can be numbered differently in the two groups.)

So how can I compare two groups/graphs that are defined only by their adjacency list?

I tried searching for algorithms, but typical questions are "what is the shortest rout from A to B" or "how to visit all nodes" - or maybe I was using the wrong search terms... I can (with a lot of convoluted code) do a brute force comparison on one atom - but how would I then go on? Obviously using brute force is very expensive... (though potentially manageable in my case...)

Edit: Following the comments and searching around a bit, I believe this would be identifying an edge & vertex (node) induced subgraph. - I.e. what is the associated algorithm or a pointer at specific literature. (The simpler the better)

$\endgroup$
  • $\begingroup$ Perhaps I misunderstand but to me it seems that you need to test these molecules for isomorphism? Is this question of a theoretical nature or do you need to do this in practice? $\endgroup$ – Jernej Nov 26 '15 at 12:52
  • $\begingroup$ @Jernej That's pretty much it - and unfortunately it is something I want to implement. (Though optimisation isn't so important to me - making it work comes first.) $\endgroup$ – DetlevCM Nov 26 '15 at 13:04
  • 1
    $\begingroup$ Isomorphism software is already available in the form of libraries (nauty, bliss) and if you don't care about the interface I'd recommend using Sage. Implementing a good isomorphism tester from scratch might be overkill $\endgroup$ – Jernej Nov 26 '15 at 13:10
  • $\begingroup$ Sage isn't an option as I don't need a binary package - but libraries might be an option - I will have to read up on them and check. Thanks. $\endgroup$ – DetlevCM Nov 26 '15 at 13:43
  • 1
    $\begingroup$ Ok, understood. Well if you really want to DIY then the easiest algorithm to implement is probably VF2. The first thing I can find on it is this (jcheminf.com/content/4/1/13) but there are a ton of other things out there. $\endgroup$ – gilleain Nov 26 '15 at 14:53
1
$\begingroup$

Representation

From a graph theory perspective, chemicals can be usefully described as vertex- and edge- colored simple graphs. Atoms are usually represented as vertices with the element as an associated label. Bonds can be considered as multiedges, but edge colors are more usual since there is a small set of bond-orders (single, double, triple) - although for completeness we could include quadruple and quintuple, or other types of bond like hydrogen, dative, Cp-Metal interactions, etc.

Theoretical Problems

Chemistry and graph theory have a long and fruitful history, but the particular problems you ask about are graph isomorphism (GI) and/or subgraph isomorphism. There is a lot of information out there about GI as a problem, but the focus for computer scientists and mathematicians tends to be about the harder part of the problem. For example, the recent news about László Babai's result on the complexity of GI is fascinating but kindof irrelevant for chemistry.

Chemicals are usually quite 'simple' graphs, in some senses; often they have vertices with degree less than 5, certainly they are sparse, most of them are planar or nearly so. This makes them quite tractable for GI and similar algorithms. On the other hand, they can be quite large - fullerenes, large sugars, proteins.

Algorithms

So GI is simpler to describe than the subgraph isomorphism problem. To check that two graphs are isomorphic, it is enough to generate a canonical representation of both graphs and compare these. For example InChI or canonical-SMILES, or signatures. To actually get the mapping between atoms it is necessary to do something like subgraph isomorphism with the whole query graph.

So one way to get the mapping between a (sub)graph and another graph is to repeatedly search through both graphs, building up the mapping along the way. During the search, you either run out of vertices in the query graph (an isomorphism) or you reach a state where no further mapping can be done. In which case, the mapping is re-started at a different 'root' in the query, for as many vertices in the original query.

This process is described in various places, for example this paper comparing two substructure search algorithms. Of course, there are more sophisticated or specialised algorithms out there, but VF2 is pretty good, and quite simple to implement. Additionally, there is a lot of literature in the area of 'graph mining' that deals with subgraph isomorphism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.