From chemistry-request@www.ccl.net  Tue Apr 13 00:02:55 1999
Received: from gateway.bioreason.com (bioreason.trail.com [209.194.109.237])
        by www.ccl.net (8.8.3/8.8.6/OSC/CCL 1.0) with ESMTP id AAA20194
        Tue, 13 Apr 1999 00:02:52 -0400 (EDT)
Received: from bioreason.com (bioreason8 [192.168.1.8])
	by gateway.bioreason.com (8.9.3/8.9.3) with ESMTP id WAA03785
	for <chemistry@www.ccl.net>; Mon, 12 Apr 1999 22:01:41 -0600
Sender: dalke@bioreason.com
Message-ID: <3712C189.17D32229@bioreason.com>
Date: Mon, 12 Apr 1999 21:01:13 -0700
From: Andrew Dalke <dalke@bioreason.com>
Organization: Bioreason, Inc.
X-Mailer: Mozilla 4.05 [en] (X11; U; IRIX 6.2 IP22)
MIME-Version: 1.0
To: chemistry@www.ccl.net
Subject: maximum common substructure
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit


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
						dalke@bioreason.com