Subject: Summary: Ring perception algorithms

From: "Simon Kilvington" <[email-masked]>
Date: Fri, 31 Mar 1995 13:59:47 +0100 (BST)

Here is a summary of the responses I received regarding ring perception
algorithms.

my original question:

        does anyone have any references to ring perception algorithms?
All I need to know is whether each bond in a molecule is either cyclic
or acyclic.  It's fairly easy to think of ways of doing it but I was
wondering if there are any cunning tricks that have been developed that
make it faster/use less memory etc.

in summary:

	it seems there are no cunning tricks - to tell whether each bond
is cyclic or acyclic you basically have to do a tree search and see which
bonds you end up visiting more than once. Edgardo Garcia mentions first
removing terminal atoms; this is the only optimisation that can be made.

	reviews of the subject including the more complicated smallest
set of smallest rings (SSSR) finding problem can be found in:

G.M.Downs, V.J.Gillet, J.D.Holliday, M.F.Lynch; J.CICS 29 (1989) 172-187
"Reviews of ring perception algorithms for chemical graphs"

and

G.M.Downs, V.J.Gillet, J.D.Holliday, M.F.Lynch; J.CICS 29 (1989) 187-206
"Theoretical aspects of ring perception and development of the extended
SSSR concept"

	a couple of newer methods not covered by the reviews are:

R.Balducci, R.S.Pearlman; J.CICS 34 (1994) 822-831
"Efficient exact solution of the ring perception problem"

and

B.T.Fan, A.Panaye, J.P.Doucet, A.Barbu; J.CICS 33 (1993) 657-662
"Ring perception - a new algorithm for directly finding the SSSR from a
connection table"

======

the full responses (slightly edited):

Andrew Leach ([email-masked]) wrote:

        There are masses of papers on ring perception. In particular,
Downes and Willett produced a series of about 6 papers in JCICS
about 1989. More recently, Bob Pearlman claims to have solved the
problem "unambiguously". If you just want to know whether a bond is in
a ring or not, then you can probably get there from the spanning tree.

======

Richard Bone ([email-masked]) wrote:

You should turn first to a review from Peter Willet's group:
J.C.I.C.S.  29, 172, (1989) and the paper immediately following it.

All the major references are in that.
The subject is quite big and, as you will see, which algorithm you
choose depends on what you actually want.

I have recently implemented 'ring-perception' in a computer program,
as a precursor to 'aromaticity perception'.  I had to hack some ideas 
together from several of the main algorithms out there.

My feeling is that Corey/Petersson and Wipke/Dyott  (the early ones) are
the most robust.  Subsequent attempts (Roos-Kozel/Jorgensen and
Gastegier/Jochum) are rather more complex, with a view to recognising
'chemistry' in preference to rigorous graph-constructs.   

======

David Clark ([email-masked]) wrote:

The definitive reference is

author = "Downs, G.M., Gillet, V.J., Holliday, J.D. and Lynch, M.F. ",
title  = "Review of Ring Perception Algorithms for Chemical Graphs ",
journal = "Journal of Chemical Information and Computer Sciences ",
year = "1989 ",
volume = "29 ",
pages = "172--187 ",

Which should at least give you a start.

I usually use a method which creates a breadth-first spanning tree
for the molecule thus locating the ring closure bonds. By backtracking
from these, the rings can be found. This works well for me except for
very complex ring systems.

======

Marvin Waldman ([email-masked]) wrote:

There are dozens (maybe hundreds) of papers in the chemical information
literature on this subject.  A recent paper on the topic with a
rather clever new algorithm for this problem is:

"Efficient Exact Solution of the Ring Perception Problem", R. Balducci
and R.S. Pearlman, J. Chem. Inf. Comput. Sci., pp. 822-831, vol. 34, (1994).

It has many references to earlier algorithms for dealing with ring
perception.  You will find that most of the effort in these algorithms
is devoted to finding what is known as the SSSR which stands for
Smallest Set of Smallest Rings.  The problem of finding whether or
not a bond is a ring bond is a much easier problem to solve which almost
all of these algorithms do as part of their approach to finding the
SSSR.  An algorithm I found reasonably straightforward to implement
and is also reasonably efficient with regard to locating all the
ring bonds in the molecule in one pass through the connectivity tree
is:

"An Algorithm for the Perception of Synthetically Important Rings",
J. Gasteiger and C. Jochum, J. Chem. Inf. Comput. Sci., pp. 43-48,
vol. 19, (1978).

======

Terence Wilson ([email-masked]) wrote:

Finding the cyclic/acyclic bonds in a graph can be done in polynomial time by
walking the graph to deduce a spanning tree which can then be used to create a
fundamental basis set of rings. Linear combinations of the basis set generate
all possible rings in the graph.

Downs et al. is the most comprehensive survey of ring perception algorithms:

'Review of Ring Perception Algorithms for Chemical Graphs'. Downs et al. JCICS
1989, 29, 172-187.

======

Edgardo Garcia ([email-masked]) wrote:

Yes, there are lots of ring-finding algortihms out there.
Have a look at J.Chem.Inf.Comp.Sci. and Thetraedron Comp. Methodol.
also at {Garcia E. & Reyes L.M.,J.Mol.Struct. Theochem, 282, 1993},
you will find an algorithm and references there.
A simple way of doing it is :
1. Use a recursive prunning algorithm that cuts all terminal bonds.
2. The structure that remains has only ring and ring bridging bonds.
3. To know if a bond is a ring bond remove it and see if the molecule
   doesn't divide in two subunits.
Now, depending on the complexity of your molecules, another way is
obtaining the smallest set of rings (SSR). All bonds that are in this
set are ring bonds.

======

Dave Cosgrove ([email-masked]) wrote:

        Try Fan et al, JCICS 33, 657-662 (1993).  It's actually a
paper on SSSR generation, but it tells you how to do things a bit more
efficiently generally.  I think (please let me know if someone tells
you otherwise!) that you basically have to do it by brute force.

======

	thanks to everyone who helped me.

	bye-fer-now,

	Si.

---
Simon Kilvington, [email-masked]