Information Technology Reference
In-Depth Information
C
C
C
C
C
C
C
O
S
C
C
Fig. 11.9.
Example molecule used to demonstrate full perfect extension pruning
To further illustrate the process, we study another complete example, which
also shows the different cases that can occur. Consider the molecule shown in
Figure 11.9. Our goal is to build this molecule using full perfect extension prun-
ing.
2
As the order of the elements we use again
S
<
C
<
O
, which is in line
with the order used in all preceding examples. As a consequence the search has
to start at the sulfur atom, because all other starting points obviously lead to
non-canonical code words (as even their first letter is greater).
Three extensions of this one-node fragment (code word:
S
) are possible: we
may add one of the two ring bonds to carbon atoms (which lead to the same
fragment
S-C
) or we may add the bond to the oxygen atom. Without perfect
extension pruning, both child fragments (i.e.
S-C
and
S-O
)wouldhavetobe
considered. However, the bond to the oxygen atom is a bridge, occurs in all
molecules (only one in this example), and the number of embeddings of the
extended fragment is the same as for the single sulfur atom. Hence adding this
bond is a perfect extension, while the bond to a carbon atom is not eligible as a
perfect extension, since it is a ring bond (and thus no bridge, see Section 11.3).
This leads to the code word
S 0-O1
. The extension is marked as perfect, and the
volatile part of the code word starts directly after the sulfur atom (as is indicated
by a gray background).
Note that the other extension (leading to the fragment
S-C
)wouldhavetobe
considered if we only used partial perfect extension pruning, since its code word,
that is,
S 0-C1
, is smaller than
S 0-O1
. Only full perfect extension pruning
allows us to eliminate this fragment from the search.
In the next step, all possible extensions are considered (no restriction by
“local” or “simple” rules, because the preceding extension was perfect), which
are the two ring bonds (again leading to the same fragment, now
O-S-C
)andthe
bond from the oxygen atom to the next carbon atom in the chain. The latter
is a perfect extension and thus the other two extensions are pruned, resulting
inthecodeword
S 0-O1 1-C2
. Since the new edge is a perfect extension, the
volatile part grows to two edge descriptions (gray background).
In the third step, the two ring bonds incident to the sulfur atom are again
eliminated due to the perfect extension to the next carbon atom in the chain,
which is in the left ring:
S 0-O1 1-C2 2-C3
. Now there are no perfect extensions
left, because all remaining bonds are part of rings (and thus no bridges).
It should be noted that the maximum source index is still 0 (sulfur atom),
because all extensions made so far were perfect and thus their source indices are
2
Mining only one molecule is, of course, not very useful in practice, but it keeps the
example simple, and the process, at least w.r.t. pruning, is exactly the same as when
mining a larger number of molecules.
