Subject: Re: CCL:Ring perception algorithm

From: [email-masked]
Date: Sun, 28 Oct 2001 17:05:34 -0600

Hello --

I am woefully behind with respect to e-mail and, consequently, I just saw the
message which Mark Thompson posted on at Fri, 19 Oct 2001 11:43:29 -0700:

> I would like to hear from anyone who has implemented the ring perception
> algorithm of Balducci and Pearlman (1994).  I have some interesting
> questions and observations to share.

11 minutes and 27 seconds earlier (i.e., at Fri, 19 Oct 2001 11:32:02 -0700),
Mark sent the following message directly to me.  It includes the questions
to which he alluded in his CCL posting.  I suspect that the answer to his
questions might be of interest to anyone else interested in ring perception
and, hence, I'm responding to Mark's questions now:

> Dear Prof. Pearlman,
>
> I have had great fun implementing and using the algorithm from Balducci 
> & Pearlman J. Chem. Imf. Comput. Sci. 1994, 34, 822-831.
>
> I was hoping I could bother you with two questions.
>
> 1.  I am interested in finding out contact information for Dr. Balducci, 
> if it is available.
>
> 2.  I have had some difficulty with certain classes of molecules and the 
> algorithm in the above paper: specifically, fullerenes like buckyball.
> Generally, all, but 1 of the rings are found.  So for buckyball the
> formula in your paper gives 31 rings (R = E - N + 1 = 31) when there
> are 32 rings in this structure (at least to a chemist, but perhaps not
> to a mathematical topologist).  The math in the algorithm appears to be
> straightforward and I've rechecked everything many times by hand.  Has
> this issue ever cropped up in your use of the method?  I think zeolites
> and other clathrate type molecules would present problems as well.
>
> Sincerely,
> Mark Thompson

Answers:

1. Renzo Balducci was my grad student when we developed the algorithm to
which Mark refers.  He remained in my Lab as a postdoc while waiting for 
his wife to complete her Ph.D..  When his wife then chose to take a 
postdoctoral position near Austin, Renzo decided to remain in my Lab as 
a permanent Research Associate and he remains a highly valued member of
our group.  You can reach him at [email-masked].

2. Although we developed a novel derivation of the "R = E - N + 1"
equation which is the central point of Mark's question, that equation is
the well-known Euler's Theorem first derived by Leonhard Euler over 250 
years ago. 

Our algorithm identifies the smallest set of smallest rings (SSSR) of a 
molecular connection table (or any other topological graph of nodes and
edges).  This is a classic problem in graph-theory and, prior to the 
publication of our algorithm and associated proof, it was thought to be
a member of a class of "NP-complete" problems.  Previously, SSSR perception
programs either implemented exact solutions which required cpu-times
which increased exponentially with the size of the ringsystem or they
implemented faster but non-exact solutions which could easily miss finding
the true SSSR.  Our solution was based on a novel "chain-message" algorithm
which we proved provides an exact solution of polynomial (roughly N*logN)
order.  Significantly, our contribution was to discover a new algorithm
to identify *which* rings comprise the SSSR but the *number* of rings in
the SSSR is determined by Euler's Theorem.

The SSSR is comprised of the set of smallest linearly independent -- i.e.,
*non-redundant* --  rings.  Mark Thompson deserves credit for wondering if 
the answer to his question (about 31 vs 32 rings in "buckyball") might be 
found in the difference between a typical chemist's perception of "caged"
ringsystems and the undeniably correct topological representation of such
structures.

Although *exactly* the same explanation would apply in the case of any
other "caged" structure (such as Mark's buckyball), the explanation is
easiest to make and understand if we simply talk about cubane.  The eight
carbon atoms of cubane form a cube with six faces.  Hence, most chemists 
would, at first, say that cubane consists of six 4-membered rings.  But
it is easy to see that, once five sides of the "box" have been defined,
the sixth side is also defined!  (That is, all four atoms and all four
bonds between the atoms of the sixth side have already been defined and
used when constructing other sides of the cube.)  Note that Euler's
Theorem yields R = 12 - 8 + 1 = 5 rings for cubane (just as our algorithm
would find and report).

Lastly, I can not resist pointing out that structures which chemists
justifyably regard as "cages" (such as cubane or buckyball) can and, in
some respects, should be regarded as planar fused ringsystems. Imagine 
drawing the "front" face of a cube as a large dark square, drawing the
"back" face as a smaller lightly-drawn square centered inside the first
square, and drawing the other faces by making tapered connections from
the corners of the outer square to the corners of the inner square.  Now,
replace all of the dark, light, and tapered "bonds" (edges) with lines of
uniform width and intensity and note that the resulting planar fused
ringsystem is topologically equivalent to the cube.  Hence, neither our
ring perception algorithm nor Euler's Theorem see fullerenes or any other
"caged" ringsystems as particularly "tricky" problems because, in fact,
they are no different than non-tricky ringsystems.

I hope that my comments have been of interest to some of you.  Also, 
if anyone else has questions or has encountered any difficulty when 
implementing our "chain message" algorithm, please don't hesitate to 
contact me.

Best wishes,

  -- Bob Pearlman

Robert S. Pearlman, Ph.D
Coulter R. Sublett Regents Chair in Pharmacy and
Director, Laboratory for the Development of
  Computer-Assisted Drug Discovery Software
College of Pharmacy
University of Texas
Austin, Texas 78712
512-471-3383 (voice)
512-471-7474 (FAX)
[email-masked]