vertices over the tree structures with exact distance restriction. The theories and
implementation details are described in the following subsections.
2.5.1 Structure for a Given Distance Distribution
A molecular graph represents topological connections between the atoms of the
molecules. A spanning tree of the graph can provide the basic skeleton over which
additional edges can be inserted to introduce cycles and thereby produce the entire
molecular structure. The multiplicity of bonds can be considered as edge weights
and can be dealt by assigning weights 1, 2 and 3 for single, double and triple bonds,
respectively. Similarly, heterogeneous atoms, with their valency information, can
also be introduced as nodes, which are by default considered to be carbon atoms in
our discussions.
It is clear from above that the starting point of structure generation for a given
number of vertices (atoms) is the generation of rooted trees since the structure
generation will be carried out with respect to a particular atom in a molecule in our
current approach based on topological distances from a particular vertex. Moreover,
to prevent duplicate structures, only non-isomorphic trees should be generated.
For the purpose of illustration, consider the chemical structure and the corresponding graphical and tree representation as shown in Fig. 2.
The numbering of vertices has no structural significance apart from that it is done
to obtain the rightmost tree having node 1 as the root and pre-order numbering for
the other vertices and is merely for array representation of the tree structure. The
tree can be represented by the following parent and level array representations:
parent ¼ 0; 1; 2; 3; 1; 5; 5
½
level ¼ 1; 2; 3; 4; 2; 3; 3
½
where for a given vertex i, parent i
½ ¼ j means vertex j is the parent of vertex
i except for root vertex 1 having no parent vertex and is represented by 0 as its
parent. Similarly, for a vertex i, level i
½ ¼ j means vertex i is at level j, where root
vertex 1 has a level 1 and other vertices have level one greater than the level of its
parent vertex. The root vertex can sometimes be considered to have level 0 and the
levels of the subsequent vertices follow.
With the illustrated example and the terms introduced in consideration, the
different steps in structure generation are explained in the following points:
Fig. 2 Graph and tree illustration
Combinatorial Drug Discovery from Activity-Related Substructure …
81
implementation details are described in the following subsections.
2.5.1 Structure for a Given Distance Distribution
A molecular graph represents topological connections between the atoms of the
molecules. A spanning tree of the graph can provide the basic skeleton over which
additional edges can be inserted to introduce cycles and thereby produce the entire
molecular structure. The multiplicity of bonds can be considered as edge weights
and can be dealt by assigning weights 1, 2 and 3 for single, double and triple bonds,
respectively. Similarly, heterogeneous atoms, with their valency information, can
also be introduced as nodes, which are by default considered to be carbon atoms in
our discussions.
It is clear from above that the starting point of structure generation for a given
number of vertices (atoms) is the generation of rooted trees since the structure
generation will be carried out with respect to a particular atom in a molecule in our
current approach based on topological distances from a particular vertex. Moreover,
to prevent duplicate structures, only non-isomorphic trees should be generated.
For the purpose of illustration, consider the chemical structure and the corresponding graphical and tree representation as shown in Fig. 2.
The numbering of vertices has no structural significance apart from that it is done
to obtain the rightmost tree having node 1 as the root and pre-order numbering for
the other vertices and is merely for array representation of the tree structure. The
tree can be represented by the following parent and level array representations:
parent ¼ 0; 1; 2; 3; 1; 5; 5
½
level ¼ 1; 2; 3; 4; 2; 3; 3
½
where for a given vertex i, parent i
½ ¼ j means vertex j is the parent of vertex
i except for root vertex 1 having no parent vertex and is represented by 0 as its
parent. Similarly, for a vertex i, level i
½ ¼ j means vertex i is at level j, where root
vertex 1 has a level 1 and other vertices have level one greater than the level of its
parent vertex. The root vertex can sometimes be considered to have level 0 and the
levels of the subsequent vertices follow.
With the illustrated example and the terms introduced in consideration, the
different steps in structure generation are explained in the following points:
Fig. 2 Graph and tree illustration
Combinatorial Drug Discovery from Activity-Related Substructure …
81