Symmetry perception algorithms

Quantitative structure-activity relationships are used to model the biological effect of a set of compounds and to propose new structures with optimized biological activity (see Quantitative StructureActivity Relationships in Drug Design). Such a system makes extensive use of structure generation, substructure search, and symmetry perception algorithms. 

Ouyang, Z., Yuan, S., Brandt, J. and Zheng, C. (1999). An Effective Topological Symmetry Perception and Unique Numbering Algorithm. JChem.Inf.Comput.ScL, 39,299-303. 

See, for example, M. Razinger, K. Balasubramanian, and M. E. Munk,/. Chem. Inf. Comput. Sci., 33, 197 (1993). Graph Automorphism Perception Algorithms in Computer-Enhanced Structure Elucidation. C. Jochum and J. Gasteiger, J. Chem. Inf. Comput. Sci., 17, 113 (1977). Canonical Numbering and Constitutional Symmetry. See also Ref. 7... 

The problem of canonical coding, graph isomorphism, and graph automorphism has both mathematical and chemical significance. The mathematical formulation of the problem is briefly set out below, and some cormections with the chemical counterpart are presented. In the subsequent sections, the main algorithms used in chemistry for canonical coding of molecular graphs and constitutional symmetry perception are presented and compared. 

Rucker, G. and Rilcker, C. (1990). Computer Perception of Constitutional (Topological) Symmetry TOPSYM, a Fast Algorithm for Partitioning Atoms and Pairwise Relations among Atoms into Equivalence Classes. J.Chem.lnfComputSci., 30,187-191. 

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

Atoms characterized by identical NOON values are considered to belong to the same equivalence class. As is apparent from the NOONs computed for graph (22) some nonequivalent atoms receive identical values. This initial partition is refined using a set of rules and an iterative algorithm. The heuristic partitioning of atoms in classes is used in connection with an automorphism detection CCAP algorithm, which makes the whole procedure efficient for canonical coding and perception of constitutional symmetry. 

Symbolic representation of double bond and quasi-rigid-center configurational stereochemistry of single and fully defined molecules can be considered a solved problem. Even for highly symmetrical molecules, the performance of algorithms for canonical numbering has been improved to a level that makes it efficient in all practical applications. Perception of symmetry can usually be considered a by-product of canonical numbering. 

---