Subject: perception algorithms for aromaticity etc.

From: [email-masked] (Martin Badertscher)
Date: Wed, 12 Feb 1997 17:30:55 +0100

Dimitris K. Agrafiotis wrote:

> We are trying to find some good algorithms for perceiving aromaticity,
> tautomerism and stereochemistry (RS, cis/trans) from a connection
> table, and algorithms for canonicalizing molecular graphs.

1. Canonicalizing molecular graphs
A molecular graph, or "constitution", can be coded as a connection table in
more than one way. To prove that two connection tables code the same
constitution is called the isomorphism problem. To solve the problem is
notoriously expensive. One possible solution is to assign a canonical name
(or canonical connection table) to the constitutions. If two such names are
the same, the constitutions are too. This involves the perception of
topological symmetry. Many algorithms have been proposed, e.g., the famous
Morgan algorithm:

H. L. Morgan, J. Chem. Doc., Vol. 5 (1965) p. 107

Most of them, including the Morgan algorithm, suffer from the fact that
they are not rigorous. Shelley has published an "almost rigorous"
algorithm:

C. A. Shelley et al., J. Chem. Inf. Comput. Sci., Vol. 17, No. 2 (1977) p. 110

Ray Carhart, the wizzard, has found a counterexample (by summoning lower gods?):

R. E. Carhart, J. Chem. Inf. Comput. Sci., Vol. 18, No. 2 (1978) p. 108

As a reaction Shelley placed a brute force algorithm on top of his former
one. The resulting construct is rigorous:

C. A. Shelley et al., J. Chem. Inf. Comput. Sci., Vol. 19, No. 4 (1979) p. 247

Due to Carhart's punishment the authors were too careful in writing their
text. So the scientific community missed the fact that the problem was
solved for almost 10 years. Chemists normally don't read mathematical
journals where such problems are addressed in much more cryptic ways.

I can dig out the FORTRAN77 code of the complete algorithm to canonicalize
a connection table. It could certainly be translated easily into a more
appropriate language. The copyright is with Morton E. Munk, Prof. of
Chemistry at Arizona State University. He is surely willing to share the
code with you. Contact me if you are interested.

======

2. Perceiving stereochemistry
This is a much more complicated problem as it (sensibly) involves the
stability of molecules, not only mathematics. To my knowledge there is only
a single algorithm published and coded that generates all stable
stereoisomers out of a canonical connection table. It has its origin in
Munk's lab too:

M. Razinger et al., J. Chem. Inf. Comput. Sci., Vol. 33, No. 6 (1993) p. 812

======

3. Perceiving aromaticity
Before the question of perceiving aromaticity can be addressed, it must be
clear what the results are used for. You have to clearly define what
aromaticity is. This can be done in a purely mathematical way. Benzene,
furane, and thiophene might be considered aromatic in this way, butadiene
could be non-aromatic, cyclobutadiene and cyclooctatetraene anti-aromatic.
If you consider chemical behaviour such as reactivity, benzene and
thiophene could be considered aromatic. Furane, butadiene, and
cyclooctatetraene are non-aromatic. Cyclobutadiene is anti-aromatic and
therefore rather unstable.

Martin Badertscher, head of radiochemistry,
dpt. of organic chemistry, federal institute of technology, Zurich, Switzerland

E-Mail:  [email-masked]