Subject: maximum common substructure

From: Andrew Dalke <[email-masked]>
Date: Mon, 12 Apr 1999 21:01:13 -0700

Hello,

  I am looking for unix software for finding the maximum common
substructure (MCS) of a set of molecules; represented as a graph with
typed nodes and edges.  My searches so far have come up with:

TOPSOM -- TOPological SIMilarity
  http://baker.mcs.kent.edu/paper/ECCC5.html

ToSiM  -- Topological Similarities of Molecules.
  http://echm10.tuwien.ac.at/inst/vk/  (MS Windows?)

but I have no other information about ther usefulness of those programs.

  The examples I've seen, like TOPSOM, convert the problem into a
maximum clique detection program.  However, they only find the MCS
of two molecules and we would like the MCS of a set of molecules.
The obvious extension is to compose the compatibility graph (using
the TOPSOM nomenclature) with each new molecule's relational line graph,
but I worry that the full compatibility graph becomes exponentially
large with the number of molecules.  Does anyone have advice along
these lines?

  I will summarize the responses,

						Andrew Dalke
						[email-masked]