Subject: Summary: Recognition of compounds from a connection table

From: Joerg Weiser <[email-masked]>
Date: Mon, 06 Oct 1997 16:31:29 -0400

Some time ago, I posted the following question:

"Do you know of any references that deal with the recognition of
compounds (e.g stored in a compound library) from their connection
tables?"

I received two answers. Thanks a lot.

==============================================================

Try Ash, J., Chubb, P., Ward, S., Welford, S., Willet, P.,
Communiaction, Storage and Retrieval of Chemical Information,
Ellis Horwood Series Chemical Science, Ellis Horwood Limited,
Chichester, 1985.

It is not new, and some important modern developments are missing,
but is is still a good overview about the basic principles
and technology.

Dr. Wolf-D. Ihlenfeldt
Computer Chemistry Center, University of Erlangen-Nuernberg
Naegelsbachstrasse 25, D-91052 Erlangen (Germany)
Tel (+49)-(0)9131-85-6579  Fax (+49)-(0)9131-85-6566
==============================================================
References:

Balaban, A.T.; Mekenyan, O.; Bonchev, D. : Unique  Description  of 
Chemical Structures  Based  on  Hierarchically  Ordered  Extended 
Connectivities  (HOC -Procedures). I. Algorithms for finding Graph
Orbits and Canonical Numbering of Atoms., II. Mathematical Proofs,  J.
Comp. Chem. 1985, vol. 6, pp. 538-551.

Corneil D .G., Kirkpatrick D.G. : A Theoretical Analysis of various
Heuristics for the Graph Isomorphism Problem.  SIAM J. Comp., 1980, v.
9, No. 2, pp. 281-297.

Figueras J. : Automorphism and Equiavalence Classes. J. Chem. Inf. Comp.
Sci., 1992, v. 32, pp. 153-157.

Fortin S. : The Graph Isomorphism Problem. Technical Report No. TR
96-20, Dept. of Comp. Sci. University of Alberta, Edmonton, 1996.
ftp://ftp.cs.ualberta.ca/pub/TechReports/1996/TR96-20/ (gzip)

Golender V.E., Drboglav V.V., Rosenblit A,B.  Graph Potentials Method
and it's Applications for Chemical Information Processing.  J.
Chem.Inf.Comp.Sci., 1981, v.21, No. 4,  pp. 196-204.

Goodman S.E., Hedetniemi S.T., Introduction to the Design and Analysis
of Algorithms  McGraw-Hill, New York, 1977.

Harary F.  Graph Theory,  Addison Wesley, Reading,  MA, 1969.  

Hendrickson J.B., Toszko G.,  Unique Numbering and Cataloguing of
Molecular Structures. J.Chem.Inf.Comp.Sci., 1983, v. 23, pp. 171-177.

Herndon W.C.  Canonical labelling and System of Linear Notation for
Chemical Graphs.  in Chemical Applications of Topology and Graph
Theory.,  ed. by R.B. King,  Elsevier,  Amsterdam,  1983,  231-242.

C. Jochum,  J. Gasteiger,   Canonical  Numbering   and  
Constitutional   Symmetry.   J. Chem.Inf.Comp.Sci., 1977, vol. 17, pp.
113-117.

Liu X., Balasubramanian K., Munk M.E. : Computational Techniques for
Vertex Partitioning of Graphs,  J.Chem.Inf.Comp.Sci., 1990, v. 30, pp.
263-269.

Liu X., Klein D. J., The graph isomorphism problem,  J. Comp. Chem., 12
(1991) n. 10, 1243-1251.

McKay B. D.,  Nauty User's Guide (version 1.5), Technical Report No.
TR-CS-90-03, Comp. Sci. Dept., Australian National University,
Canberra,1990. 
http://cs.anu.edu.au/people/bdm/nauty

B. D. McKay, Practical graph isomorphism, Congressus Numerantium 30
!1981) 45-87.

Miller  G. L.,  Graph Isomorphism, General Remarks,  J. Comp. Syst.
Sci.  30 (1979) 128-142

Morgan H. L., The Generation of a unique machine description for
chemical structures - a technique developed at Chemical Abstracts
Service,  J. Chem. Doc. 5 (1965), 107-113. 

Randic M. : On Canonical Numbering of Atoms in a Molecule and Graph
Isomorphism. J.Chem.Inf.Comp.Sci., 1977, v. 17, No. 3, pp. 171-180.

Razinger, M.; Balasubramanian, K.; Munk, M.E. Graph Automorphism
Perception in Computer-Enhanced  Structure  Elucidation.
J.Chem.Inf.Comp.Sci., 1993, vol. 33, pp. 197-201.

Read, R.C.,  Corneil D.G., The Graph Isomorphism Disease,  J. Graph
Theory  1 (1977) 339-352.

G. Rucker,  C. Rucker,  Computer  perception of constitutional
(topological) symmetry:  TOPSYM, a fast algorithm for partitioning atoms
and pairwise relations among atoms  into equivalence classes.  J.Chem.
Inf. Comp. Sci., 30 (1990) 187-191.

G. Rucker, C. Rucker,  On Using the Adjacency Matrix Power Method for
Perception of Symmetry and for Isomorphism Testing of Highly Intricate
Graphs. J.Chem. Inf. Comp. Sci., 31 (1991)  123-126.

Schubert W., Ugi I. : Constitutional Symmetry and Unique Description of
Molecules. J. Am. Chem. Soc. 1978,  v.100,  No. 1,  pp. 37-41.

Shelley, C.A.; Munk, M.E. An Approach to the Assignment of Canonical
Connection Tables  and Topological Symmetry Perception.
J.Chem.Ihf.Comp.Sci., 1979, vol. 19, pp. 247-250. 

I. V. Stankevich, E. G. Gal'pern, A. L. Chistyakov, I. I. Baskin, M. I.
Skvortsova, N. S. Zefirov, O. B. Tomilin, Spectral Theory of Graphs in
Chemistry. 1. Projection Operators and Canonical Numeration of Graph
Vertices.  J. Chem. Inf. Comp. Sci., 34 (1994) 1105-1108.

Stankevitch M.I., Tratch S.S., Zefirov N.S. : Combinatorial Models and
Algorithms in Chemistry. Search for Isomorphisms and Automorphisms of
Molecular Graphs. J.Comp.Chem., 1988, v. 9, No. 4, pp. 303-314.

M. Uchino, Algorithms for Unique and Unambiguous Coding and Symmetry
Perception of Molecular Structure Diagram. I, II, III. J. Chem. Inf.
Comp. Sci., 1980,  20, pp. 116-126.

Ullmann, J.R. : An Algorithm  for Subgraph Isomorphism.  J. ACM, 1976,
vol. 23,  No 1, pp. 31-42.

Alexander A. Oliferenko, Department of Organic Chemistry
Moscow State University, Lenin Hills, Moscow 119899, Russia
e-mail: [email-masked];   [email-masked]
Phone:  7  095  939 35 57

-- 
     ================================================================
     Joerg Weiser               phone: +1 212 8545143
     Department of Chemistry           +1 212 8548402
     Columbia University        
     3000 Broadway MC 3140      fax:   +1 212 6789039
     New York, NY 10027         email: [email-masked]
     ================================================================