Premium
Unique description of chemical structures based on hierarchically ordered extended connectivities (HOC procedures). I. Algorithms for finding graph orbits and canonical numbering of atoms
Author(s) -
Balaban Alexandru T.,
Mekenyan Ovanes,
Bonchev Danail
Publication year - 1985
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.540060606
Subject(s) - numbering , equivalence (formal languages) , algorithm , computer science , canonical form , topological graph , topological sorting , similarity (geometry) , graph , mathematics , topology (electrical circuits) , combinatorics , directed acyclic graph , theoretical computer science , discrete mathematics , pure mathematics , artificial intelligence , image (mathematics)
An iterative algorithm is described for finding topological equivalence, ordering, and canonical numbering of vertexes (atoms) in molecular graphs. Like the Morgan algorithm, it is based on extended connectivities but: (i) the latter are used hierarchically, i. e., the discrimination in the next iteration is carried out only for the vertices having the same extended connectivities (ranks) at the previous iteration; (ii) at equal extended connectivities, additional discrimination is introduced by the ranks of adjacent vertices; (iii) there is no “best name” search; (iv) three levels of complexity of chemical structures are distinguished and handled by different procedures. Two schemes of application of HOC procedures are presented: one directed towards a fast canonical numbering for coding systems, and another one yielding levels of topological equivalence allowing a unique topological representation of the molecule with possible applications to similarity search, structure‐activity correlations, etc.