# (Computationally) finding similarity between two organic compounds

I have been struggling to find an acceptable answer for this question for my purposes.

There are many ways to find similarity between two organic compounds - some of which are particularly popular in chemoinformatics. The seemingly most popular way is to use fingerprints of molecules, which then somehow correlates to the structure/function of various parts of the molecule. This approach seems very good when you're looking for general similarity between molecules. It also has the added benefit of making it fast to compare huge amounts of molecules, as each molecule can be encoded separately (so it's generally speaking $O(n)$), rather than comparing every pair of molecules (which would be $O(n^2)$).

However, for some purposes, this fingerprinting approach is not very good. I need a function of two molecules with the following properties:

• If $A$ and $B$ are two molecules, then $f(A, B) \in [0, \infty).$
• $f(A, A) = 0$
• $f(A,B) + f(B,C) \geq f(A,C)$

These are similar to the basic requirements for a metric space. (The big omission is that I don't necessarily need $f(A,B) = f(B,A),$ although this certainly couldn't hurt!)

The reason that I want such a function is because I'm designing a neural network that essentially outputs a molecule, and I want to have some sort of error on the output.

I have played around a bit with Python-RDKit, and its similarity module, but haven't really been able to form a good "error" function from the output.

I've also experimented a bit with an algorithm I created that looks for the largest identical connected subgraphs of two molecules, and essentially finds matches for each part of the query molecule. The final output is then how many different parts the molecule needs to be split into to find a match.

For instance, if the "true" molecule is ethylbenzene, while the query molecule is m-xylene, then the algorithm would find that the m-xylene needs to be broken into 3 parts for each part to find a perfect match: a benzyl group missing a hydrogen at the third carbon of the aromatic ring, the methyl group that was formerly attached at the third carbon, and the hydrogen that remains from the benzyl group.

However, this algorithm suffers from several problems:

1. If the query is a subset of the true answer, then the algorithm will always give the answer as 2 (one part is the subset, and the other part is the hydrogen that caps it - try seeing it with something like query - methane, true - acetic acid). This isn't that big of a concern, as you can simply run the algorithm twice - once comparing the query to the true molecule, and once in reverse. That way, if the two molecules are indeed far apart, it's not hard to see (the superset molecule may need to be broken into many pieces to be identical).

2. This algorithm is slow. Don't really see a way to speed it up. It searches for maps from subsets of the query molecule to the true molecule, then gradually builds up from there. It also can't pick maps randomly as being the best, then growing from there, as picking the wrong direction can easily make the "best" map drastically short. So it has to do all possible maps at the same time. Which is slow.

In short, this is a somewhat open-ended question that boils down to:

How can we put a (loose) metric on the set of organic molecules?

• Short answer: train a neural network to deal with organic molecules (starting with interpreting SMILES, then moving up to interpreting NMR spectra, then maybe if these ideas work, to designing drugs... but this is all far away) – kosyumote Jun 28 '16 at 22:06
• Longer: originally neural networks could only deal with fixed-length data. These days are gone, thanks to RNNs. This was the first step to realize that neural networks can deal with more complicated inputs. There's also been ideas to allow networks to have access to "external resources", in particular Turing Machines, leading to the innovation of an NTM. These networks performed amazingly on certain tasks that are suited to having an external memory. – kosyumote Jun 28 '16 at 22:09
• This got me to thinking that - when I draw a chemical structure, I usually use a representation of the molecule to think about it. Thus, I am coupling neural networks with some graph/molecule manipulation machinery and seeing what happens. However, even if these ideas don't work out, it seems like a useful idea to have a nice measurement of "distance" between two molecules, in a mathematical sense. Being able to embed the set of organic molecules into some mathematical space would probably help in designing algorithms that search for molecules, providing that the embedding is useful. – kosyumote Jun 28 '16 at 22:09
• You're not the first to have thought of this. ;-) en.wikipedia.org/wiki/… – Karl Jun 28 '16 at 22:13
• Define half-decent -- or give an example of one? – kosyumote Jun 28 '16 at 22:23