However, introduction of multiple edges may lead to fused or bridged cycles and
the size of cycle may become different than intended. Consider the case of starting
structure generation from the tree in Fig. 2. If it is required to have two cycles
which can have size 5, or 6, it can be seen (Fig. 3) that the edge introductions
between vertices 3 and 6 and vertices 4 and 6 individually satisfy the size criteria,
but in combination, they inadvertently lead to having a 3-sided cycle.
On the other hand, edge introductions between vertices 3 and 7 and vertices 4
and 6 satisfy the size criteria individually as well as in combination (Fig. 4).
Thus, in order to detect and remove cases similar to the first multiple introductions discussed before, it will be required to check the cycle size validity criteria
considering all the elementary cycles, e.g. in the case being considered of multiple
edge introductions, the elementary cycles present are C 1 (1–2–3–6–5–1), C 2 (1–2–
3–4–6–5–1) and C 3 (3–4–6–3), having sizes 5, 6 and 3, respectively, even though
the intended cycles were only C 1 and C 2 . In graph theoretical terms, C 1 and C 2 are
the fundamental sets of cycles while C 3 is a derived cycle. The term elementary
cycles here has the standard graph theoretical definition, and from now on, the term
cycle is considered to be an elementary cycle unless stated otherwise.
It will thus suffice to identify the fundamental set of cycles corresponding to the
smallest sizes. The starting fundamental set of cycles corresponds to the cycles
directly resulting from edge introductions. Any cycle enumeration algorithm can
then be used to enumerate all the cycles present. We have considered the algorithm
by Gibbs [17] which is a cycle vector space method in which the cycles of the
fundamental set form the basis of the cycle vector space. With this vector space
Fig. 3 Multiple cycle introduction example (1)
Fig. 4 Multiple cycle introduction example (2)
Combinatorial Drug Discovery from Activity-Related Substructure …
83
the size of cycle may become different than intended. Consider the case of starting
structure generation from the tree in Fig. 2. If it is required to have two cycles
which can have size 5, or 6, it can be seen (Fig. 3) that the edge introductions
between vertices 3 and 6 and vertices 4 and 6 individually satisfy the size criteria,
but in combination, they inadvertently lead to having a 3-sided cycle.
On the other hand, edge introductions between vertices 3 and 7 and vertices 4
and 6 satisfy the size criteria individually as well as in combination (Fig. 4).
Thus, in order to detect and remove cases similar to the first multiple introductions discussed before, it will be required to check the cycle size validity criteria
considering all the elementary cycles, e.g. in the case being considered of multiple
edge introductions, the elementary cycles present are C 1 (1–2–3–6–5–1), C 2 (1–2–
3–4–6–5–1) and C 3 (3–4–6–3), having sizes 5, 6 and 3, respectively, even though
the intended cycles were only C 1 and C 2 . In graph theoretical terms, C 1 and C 2 are
the fundamental sets of cycles while C 3 is a derived cycle. The term elementary
cycles here has the standard graph theoretical definition, and from now on, the term
cycle is considered to be an elementary cycle unless stated otherwise.
It will thus suffice to identify the fundamental set of cycles corresponding to the
smallest sizes. The starting fundamental set of cycles corresponds to the cycles
directly resulting from edge introductions. Any cycle enumeration algorithm can
then be used to enumerate all the cycles present. We have considered the algorithm
by Gibbs [17] which is a cycle vector space method in which the cycles of the
fundamental set form the basis of the cycle vector space. With this vector space
Fig. 3 Multiple cycle introduction example (1)
Fig. 4 Multiple cycle introduction example (2)
Combinatorial Drug Discovery from Activity-Related Substructure …
83