(III) Tie Breaking—The product of corresponding primes will yield same rank for
connectivity symmetrical vertices. In such cases, the ties can be broken by
arbitrarily choosing a node corresponding to the smallest repeating rank,
doubling all the ranks and then reducing only the rank of the chosen vertex by
one. The non-consecutive ranks so obtained are then remapped to form consecutive ranks, and the extended connectivity procedure using product of
primes is performed to update ranks as described in the previous step. This
step of breaking ties followed by rank updates is repeated until all the ties are
broken and highest rank becomes equal to the number of vertices in the graph.
The completion of this step also marks the completion of canonicalization of
the graph.
(IV) Initial Vertex Selection and Branching Decisions for Traversal—With the
completion of graph canonicalization, the only steps required for unique
SMILES generation is depth-first traversal sequence and identification of ring
closures and their order in traversal. To start with, the lowest ranked atom is
chosen for traversal. At a branching vertex, the branches are followed in the
increasing order of the ranks of the neighbouring vertices; i.e. the branch
corresponding to the lowest ranked neighbour is traversed first, then the
second lowest ranked neighbour is followed and so on. It may be noted that
Weininger et al. [27] also suggest giving branching preference towards the
double or triple bonds in a ring even though the rank corresponding to such a
vertex may be greater than other neighbouring vertices. However, this further
complicates the final traversal sequence in the case of polycyclic compounds
while the omission of this preference will save some computation time but will
still generate unique SMILES.
V) Two-pass Approach—Although, initially, the ring closures for the compounds
are the edges that were introduced by joining vertices in the canonical trees,
those edges will not be the ring closures under the depth-first traversal approach
of the canonicalized graph and the traversal rule as given in the previous
step. Additionally, the rings are to be numbered in the opening order in which
they are encountered during traversal. In order to meet these requirements, the
graph is traversed two times. During the first pass, the ring closures and their
ordering are identified for the canonicalized graph and are stored as auxiliary
data. The edges corresponding to these new ring closures will now be treated as
if they were the edges introduced to complete the cyclic structure, while the tree
obtained by removal of such edges is treated now as the spanning tree.
Subsequently, the second pass is undertaken for SMILES string generation
using the previously obtained auxiliary data.
2.5.2 Structure for a Relaxed Distance Distribution
The approach taken so far suffers from the drawback that only those compound
structures will be generated that have the same number of non-hydrogen atoms as
Combinatorial Drug Discovery from Activity-Related Substructure …
87
connectivity symmetrical vertices. In such cases, the ties can be broken by
arbitrarily choosing a node corresponding to the smallest repeating rank,
doubling all the ranks and then reducing only the rank of the chosen vertex by
one. The non-consecutive ranks so obtained are then remapped to form consecutive ranks, and the extended connectivity procedure using product of
primes is performed to update ranks as described in the previous step. This
step of breaking ties followed by rank updates is repeated until all the ties are
broken and highest rank becomes equal to the number of vertices in the graph.
The completion of this step also marks the completion of canonicalization of
the graph.
(IV) Initial Vertex Selection and Branching Decisions for Traversal—With the
completion of graph canonicalization, the only steps required for unique
SMILES generation is depth-first traversal sequence and identification of ring
closures and their order in traversal. To start with, the lowest ranked atom is
chosen for traversal. At a branching vertex, the branches are followed in the
increasing order of the ranks of the neighbouring vertices; i.e. the branch
corresponding to the lowest ranked neighbour is traversed first, then the
second lowest ranked neighbour is followed and so on. It may be noted that
Weininger et al. [27] also suggest giving branching preference towards the
double or triple bonds in a ring even though the rank corresponding to such a
vertex may be greater than other neighbouring vertices. However, this further
complicates the final traversal sequence in the case of polycyclic compounds
while the omission of this preference will save some computation time but will
still generate unique SMILES.
V) Two-pass Approach—Although, initially, the ring closures for the compounds
are the edges that were introduced by joining vertices in the canonical trees,
those edges will not be the ring closures under the depth-first traversal approach
of the canonicalized graph and the traversal rule as given in the previous
step. Additionally, the rings are to be numbered in the opening order in which
they are encountered during traversal. In order to meet these requirements, the
graph is traversed two times. During the first pass, the ring closures and their
ordering are identified for the canonicalized graph and are stored as auxiliary
data. The edges corresponding to these new ring closures will now be treated as
if they were the edges introduced to complete the cyclic structure, while the tree
obtained by removal of such edges is treated now as the spanning tree.
Subsequently, the second pass is undertaken for SMILES string generation
using the previously obtained auxiliary data.
2.5.2 Structure for a Relaxed Distance Distribution
The approach taken so far suffers from the drawback that only those compound
structures will be generated that have the same number of non-hydrogen atoms as
Combinatorial Drug Discovery from Activity-Related Substructure …
87