Information Technology Reference
In-Depth Information
C
C
C
C
C
C
C
C
N O
N O
Fig. 11.4. Rings/cycles can cause problems
N
N O
N C
C N O
N O C
N C C
N O C
N O
N O C
C
N C C
C
C
C
C
N O C
N O C
C
N
C C C
O
N O C
C
C
C
C
C
N O C
C
N
O
C
C
C
C C C
Fig. 11.5. Search tree for the two molecules in Figure 11.4; closed fragments are
encircled
rest of the ring. Hence the bond leading to the carbon atom is only “locally”
perfect, but not “globally”, that is, when the ring structure is taken into account.
As a consequence we cannot restrict the search to the corresponding branch,
since we would lose fragments. This can be seen clearly from the location of the
closed fragments in the search tree shown in Figure 11.5: there are three closed
fragments (for a minimum support of 2, encircled in gray), but we cannot reach
all of them if we see adding an edge from the nitrogen atom to a carbon atom
as a perfect extension (even after the oxygen atom has been added, which could
actually be seen as a perfect extension).
Obviously, the problem is that therearetwowaysofreachingthecarbon
atom that is directly connected to the nitrogen atom. Even though only one of
them is possible in both molecules, both have to be considered, because part of
the second possibility is the same in both molecules, thus leading to a relevant
frequent fragment. Unfortunately there is no way to determine this locally, that
is, by looking only at the grown fragment and its direct extension. In order
to cope with this problem, we require that a perfect extension edge must be a
bridge 1 (that is, the extension edge must be a bridge in all embeddings of the
extended fragment). This is surely a safe (i.e. sucient) condition as it rules
out any possibility that the destination of the perfect extension edge can be
reached in any other way, and thus fixes the flaw mentioned above. However, this
1 An edge in an undirected graph is called a bridge if its removal increases the number
of connected components of the graph.
 
Search WWH ::




Custom Search