project-gemmi / gemmi

macromolecular crystallography library and utilities
https://project-gemmi.github.io/
Mozilla Public License 2.0
231 stars 46 forks source link

Uses of graph isomorphism and pynauty? #296

Closed j2kun closed 9 months ago

j2kun commented 9 months ago

Hello, I'm doing background research for a book and was browsing projects that relate to graph isomorphism. I've interviewed a bunch of computational chemists about this already (e.g., the developers of RDKit), and from that I've come to believe that most uses of graph isomorphism are actually subgraph isomorphism for substructure search and multiple common substructure (MCS).

So I was curious to see the mention of nauty and pynauty in the docs here. However, it's not clear to me what value a chemist might get from counting the automorphisms of a chemical graph. Could someone familiar with this (perhaps who wrote that doc) explain this to me, if it's not too much trouble?

wojdyr commented 9 months ago

Hi, I wrote these docs (BTW, the rendered version is here).

I tested building a graph in nauty with two potential uses in mind:

  1. Calculating RMSD, as described in in this post and discussed in #43.
  2. A colleague was interested in using nauty for small molecules, but I don't remember what for.

I don't think that anyone used it so far, and I don't know how practical would it be to use it for 1.

j2kun commented 9 months ago

Thanks!