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 -----------------------------------------------------------