Date: Fri, 11 Jun 1999 12:14:05 +0200 (CEST)
From: Jan Pedersen 
To: chemistry@ccl.net
Subject: CCL:maximum common substructure - the code
Parts/Attachments:
   1 Shown    63 lines  Text
   2          21 KB     Application, ""
----------------------------------------

Greetings,

Please find attached Graph.tar containing the necessary code for maximum
common sub-structure identification using Bron & Kerbosh.

Here is the Bron & Kerbosh code to do the job - we have used Ram's code
which is originally an implementation by Jean Francois Gibrat - then at
the NCBI. The code has been slightly modified and you have to be aware of
it's interpretation of a common sub-graph, that is: A maximally connected
subgraph does not imply a connected substructure. Second, you can only
compare molecules where all atoms are connected in a single graph, that is
you have to be careful with the treatment of salts. Anyhow, that aside it
is really fast and we use it routinely to evaluate large libraries of
structures against our own in-house screening library (currently 160,000
compounds).

Unfortunately I am unable to send the complete implementation at this
moment, but nimble (C-)fingers will make the following code work in a
jiffy.

The procedure is:

1) The routine BestFitSmall() compares two structures and returns the
largest Clique, that is the maximum common sub-graph.

2) The routine MakeGraph() makes the graphs for each of the two structures
to be compared. Once that is done a DockingGraph() can be made for
comparison.

3) FindCliques() then runs Extend() in a recursive branch and bound
fashion to find all the clicques.

4) The maximum common sub-graph is stored in external variables
declared in the include file GraphStatistics.h

All of this code comes ofcourse without any form of warranty and
``as-is'' we will ofcourse be interested in any extensions or interesting
science you manage to do with it. The code comes out of my own molecular
simulation program 'J' that is why the code may seem somwhat torn-out.

I have just tar-ed down everything in my ./Graph source directory, and
>./Types directory. If you need any further routines please let me know.

I hope I will be able to mail out a free standing version of the program
within the next month.

                        Regards and good luck

                                -- Jan

-----------------------------------------------------------
                        Dr. Jan T. Pedersen     
                        Head, Computational Chemistry and 
                              Chemical Informatics
                        Acadia Pharmaceuticals
                        Fabriksparken 58
                        2600 Glostrup, DENMARK
                        email : jan@Acadia-Pharm.com
                        phone : +45 43 29 30 05
                        FAX : +45 43 29 30 30
                        Lore : http://www.acadia-pharm.com
-----------------------------------------------------------