From chemistry-request@server.ccl.net Sun Oct 28 16:57:31 2001 Received: from VAX.PHR.UTEXAS.EDU ([128.83.164.1]) by server.ccl.net (8.11.6/8.11.0) with SMTP id f9SLvUB28688 for ; Sun, 28 Oct 2001 16:57:30 -0500 Received: by VAX.PHR.UTEXAS.EDU for chemistry@ccl.net; Sun, 28 Oct 2001 17:05:34 -0600 Date: Sun, 28 Oct 2001 17:05:34 -0600 From: PEARLMAN@VAX.PHR.UTEXAS.EDU To: chemistry@ccl.net CC: PEARLMAN@VAX.PHR.UTEXAS.EDU Message-Id: <011028170534.10540@VAX.PHR.UTEXAS.EDU> Subject: Re: CCL:Ring perception algorithm 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 balducci@naphthyl.phr.utexas.edu. 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) pearlman@naphthyl.phr.utexas.edu