Subject: CCL:maximum common substructure - the code

From: Jan Pedersen <[email-masked]>
Date: Fri, 11 Jun 1999 12:14:05 +0200 (CEST)

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 : [email-masked]
			phone : +45 43 29 30 05
			FAX : +45 43 29 30 30
			Lore : http://www.acadia-pharm.com
-----------------------------------------------------------

---

From: Andrew Dalke <[email-masked]>
Date: Fri, 11 Jun 1999 16:10:06 -0600

Jan Pedersen <[email-masked]>:
> Please find attached Graph.tar containing the necessary code
> for maximum common sub-structure identification using Bron &
> Kerbosh.

That reminded me, in addition to the graph search MCS info at
http://starship.python.net/crew/dalke/MCS/ I just released the
core library routines for both Bron-Kerbosch and the DIMACS
challenge at http://starship.python.net/crew/dalke/clique/ ,
licensed under the LGPL.  The B-K implementation is based
directly on the paper, and both algorithms have been changed
to be more "library-like", that is, pure functional and with
dynamic memory allocation, error checking and no use of global
variables.

Included in the code is a simple driver used to test that the
system compiles and works, but you'll have to write the adapter
code needed to make it useful.

I found the dfmax code was faster for what we needed than B-K,
partially because it doesn't try to find all of the cliques.
The only numbers I can find at the momement have it 3 times
faster, but that was for randomly generated graphs, and not
ones which derived from chemical structures.  I would be
interested to know if others (Jan?) find this to hold true.

Still, I don't think clique detection is the best way to find
the MCS between two compounds.  I've sent email to Jan Pedersen
to continue this discussion off CCL.

						Andrew Dalke
						[email-masked]