Subject: maximum common substructure

From: Andrew Dalke <[email-masked]>
Date: Fri, 11 Jun 1999 02:07:38 -0600

Hello,

  Some time back I asked about available software or methods to find
the 2D maximum common substructure (MCS) between a set of compounds.
Here are the belated results of that query.

  I started off looking for clique based solutions, as suggested in
http://baker.mcs.kent.edu/paper/ECCC5.html.  It turns out that those
solutions are not very useful for cyclical structures because the
correspondence graph becomes very dense, and hence very hard to use.

  (BTW, if anyone is interested in clique detection codes, the
Bron-Kerbosch is available on-line from netlib at
http://www.netlib.org/tomspdf/457.pdf and Ram Samudrala has converted
the code into C as part of RAMBIN, at
http://www.twisted-helices.com/computing/rambin/rambin.html .  There
are also some newer public domain algorithms available at
ftp://dimacs.rutgers.edu/pub/challenge/graph/solvers/ which are
somewhat faster than Bron-Kerbosch for the graphs we were testing.)

  I received several relevent responses from my CCL query.  Yvonne
Martin <[email-masked]> pointed out that DISCO uses a
clique based solution pharmacophore mapping in multiple molecules,
and mentioned that clique solutions are not used for 2D MCSes.

  Wally Reiher <[email-masked]> suggested contacting Peter Willett
about the subject because of his previous work in the matter.

  David Wild <[email-masked]> also corrected my misunderstanding
that clique codes were used for 2D MCS searches.  He pointed out some
other people who may have worked on the multiple-compound MCS problem, 
saying:
> Peter Johnson's group in Leeds may have done some kind of
> muliple-MCS that was never published, and perhaps someone in Johann
> Gasteiger's group too, although I don't think there were any
> publications from that either.

  Finally, David Lowis <[email-masked]> pointed out that
> Tripos has a piece of code (mcs.exe) which given a set of molecules
> will determine the maximum common substructure (MCS) amongst them.

However, it turns out that is part of the HQSAR package for which we
don't have a license and which costs too much for our needs.

  From this response I started digging some more.  I would like to
point out a very complete bibliography of subgraph isomorphism papaers
exists at http://www.ics.uci.edu/~eppstein/bibs/subiso.bib .  By
searching that list and with private email to Peter Willett I only
found one paper which seems applicable to the 2D multiple compound MCS
problem, which is:

@article{BaySimJoh-CICS-92,
  title = {{An algorithm for the multiple common subgraph problem}},
  author = {D. M. Bayada and R. W. Simpson and A. P. Johnson and C. Laurenco},
  journal = {J. Chemical Information and Computer Sciences},
  volume = {32},
  pages = {680--685},
  year = {1992},
  abstract = {The multiple largest common subgraph (MLCS) problem is
presented, ....}
}

  That paper describes both a pairwise MCS algorithm and the extension
of the pairwise solution to a set of compounds.

  While waiting to get that paper we started a pairwise implementation
using a graph search with backtracking implementation based on the
general ideas described in:
   Backtrack Search Algorithms and the Maximal Common Subgraph Problem
   James J. McGregor, Software-Practice and Experience, vol. 12, 23-34
   (1982).

For those interested, a description of our algorithm and a reference
implementation in Python is available from
 http://starship.python.net/crew/dalke/MCS/
Some of the compounds used in the testing of the code are proprietary
in nature so parts of the test code and documentation have been
removed.  My apologies for a possibly more confusing distribution.

The general form of our method is similar to that given in the Johnson
paper, since their algorithm also comes from McGregor.  However, I
believe we provide a better description of the algorithm details and
our code can be used to generate all unique maximal mappings directly;
which isn't apparent from the Johnson paper description.  On the other
hand, they describe some optimization techniques which we don't (yet)
use.

                                                Andrew Dalke
                                                [email-masked]