CCL Home Page
Up Directory CCL README
Date: Fri, 11 Jun 1999 12:14:05 +0200 (CEST)
From: Jan Pedersen 
Subject: CCL:maximum common substructure - the code
   1 Shown    63 lines  Text
   2          21 KB     Application, ""


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

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

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

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 :
                        phone : +45 43 29 30 05
                        FAX : +45 43 29 30 30
                        Lore :
Modified: Fri Jun 25 15:38:34 1999 GMT
Page accessed 5309 times since Sun Jun 27 14:59:29 1999 GMT