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:
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).
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?