Re:What are some real world applications of graph algorithms?
by newpycai on Monday May 25, 2020 @06:19PM
(#23305536)
That sounds interesting. Have you published anything?
[ Parent
| on HN ]
Re:What are some real world applications of graph algorithms?
by dalke on Tuesday May 26, 2020 @12:10AM
(#23307332)
On 2D molecular similarity search, yes. https://jcheminf.biomedcentral.com/articles/10.1186/s13321-0... . The general approach reduces a 2D molecular graph into a 1D bitstring "fingerprint" which is representative of the graph, and such that bit-wise similarity (Jaccard-Tanimoto) of the fingerprint gives a useful proxy estimation of molecular similarity.
For the rest? No. I'm primarily a software developer, not paper author.
There's my co-authored paper at https://pubs.acs.org/doi/10.1021/acs.jcim.8b00173 , which depends a lot on (sub)graph canonicalization.
The maximum common substructure algorithm I developed, for a set of compounds, is part of the RDKit, "fmcs". The original pure-Python implementation is at https://bitbucket.org/dalke/fmcs/src . It's been rewritten since then in C++ for the RDKit.
The Python code is easier to understand.