9. SMARTS Toolkit: Structural Searching
Back to Table of Contents
The Daylight SMARTS Toolkit provides a powerful set of substructure
searching algorithms. The SMARTS Toolkit can parse a
and produce a
then test the pattern against one or more
to see if the molecule contains the pattern.
Several types of pattern searches are available, including "yes/no"
tests and exhaustive enumeration of all occurances of a pattern in a
There are three objects specific to the Daylight SMARTS Toolkit:
The result of "compiling" a
Each SMARTS string is converted to a pattern before use; the
pattern-generation algorithm parses the SMARTS, checks for errors, and
pre-computes certain information that improves substructure-search speed.
A collection of
path objects all of which have the same
base molecule. A pathset is the result of matching a pattern against
a molecule. (For background information, see the
chapter on Substructures and Paths.)
A "vector binding". A binding of a name to a pattern or
pathset. This is explained in more detail below.
9.2 Optimizing SMARTS
dt_smarts_opt(string smarts, boolean vmatch) => string optsmarts
Returns a new SMARTS string that is equivalent in meaning to the
given SMARTS, but that has been reordered to permit matches to be done
more quickly on typical molecules. (See the
chapter on SMARTS
in the section entitled "Efficiency Considerations" for
The optimized SMARTS is called "equivalent in meaning" to the
original because the optimized string will match the exact same sets
of objects as the original (though the pathsets returned may have
their atoms and bonds in different orders), no matter what molecules
they are matched against.
The exact meaning of a SMARTS depends upon the type of match to be
performed, as described below in the functions dt_match(), and
dt_vmatch(). The parameter
vmatch, if TRUE, indicates that the
SMARTS string should be optimized for use by
indicates that it should be optimized for dt_match() or dt_umatch().
(In practical terms, optimizing for dt_match() or dt_umatch() means
that the head atom of the optimized string may not be the same as that
of the original string, whereas optimizing for dt_vmatch() means that
the first atom of the optimized string will be the same as that of the
The optimized SMARTS returned by this function are expected to be
matched reasonably quickly on the average. The actual matching
speed, however, depends on the molecules to be matched against, as
well as on the SMARTS string itself. It is not possible to guarantee
that the returned string will actually match faster than to original
SMARTS. It is often possible to generate faster SMARTS "by hand"
using particular knowledge of the molecules to which it will be
applied. The algorithm employed by this function is based on rules
generated from a database of "typical" organic molecules.
9.3 Allocating Patterns and Pathsets
dt_smartin(string smarts) => Handle pattern
Interprets the SMARTS string and creates a pattern object; returns
the object's handle.
dt_alloc_pathset(Handle molecule) => Handle pathset
Allocates a new pathset object and returns its handle. (Note: this function
is typically not needed; pathsets are normally generated by
9.4 Vector Bindings and Vbind Functions
Vector bindings are a mechanism that allow faster evaluation of a
match, and allows complex patterns to be constructed out of simpler
patterns. Those familiar with earlier Daylight software (versions
3.6x and earlier) will recognize vector bindings as closely related
to GCL's "define" functionality.
The term "binding" comes from mathematics. When one thing is bound
to another, the latter can be used to represent the former. For
example, in high-school algebra, the expression "x=3" binds the value
three to the symbolic name "x"; thereafter, wherever "x" appears we
9.4.1 Pattern Bindings
The simplest use of vector bindings is when a pattern is bound to a
name. Once the pattern and name are bound, the name can be used in
another SMARTS string in place of an atomic symbol. For example, if
we bind the pattern for C[Cl,Br,I] to the name "HALO", the string
[$HALO] becomes a valid atomic symbol; wherever it is used it is
equivalent to the atomic expression [$(C[Cl,Br,I])].
(This is an example of a
Binding patterns to names doesn't extend the expressive power of SMARTS
(unnamed vectors such as [$(C[Cl,Br,I])] are valid in any SMARTS), but it
tends to make SMARTS more readable. This is especially true where atomic
expressions such as [$(C[Cl,Br,I])] occur multiple times. For example, a
1,2,4-substituted cyclohexane could be written two ways; the second is easier
to write and easier to understand:
9.4.2 Pathset Bindings
When a pathset is bound to a name, that name represents all the
places in the molecule where a search has already succeeded. If, for
example, one has a number of SMARTS to test against a single
molecule, and many of the SMARTS contain an common expression such as
[$HALO], the search speed of each can be improved by pre-computing
the pathsets for [$HALO] (i.e. doing dt_vmatch() on the pattern for
C[Cl,Br,I]), then binding the resulting pathset to the name "HALO".
When the [$HALO] atomic expression is encountered in a SMARTS, the
vector binding already contains the pathset with all atoms that
match; no additional searching is required for that atomic
Binding pathsets in this fashion can greatly improve the performance
of "chemical knowledge" systems in which a large number of rules are
applied to each molecule. By carefully choosing common
subexpressions, matching them to the molecule, and binding the
resulting pathsets to names, a great deal of redundant searching can
dt_alloc_vbind(string name) => Handle vbind
If there is already a vector binding with the specified name, that existing
vector binding is returned. Otherwise, a new vector
binding is allocated and given the specified name.
The string name must begin with a letter from the alphabet;
subsequent characters in the name must be alphabetic, a digit, or the
underscore '_'. In UNIX parlance, the name must match the regular
If the object bound to a vector-binding is deallocated (see
dt_setval(), below), the vector binding's value is automatically set
to NULL_OB. (Note that the vector-binding object is not deallocated
in this case since its binding is not its parent or base object.)
dt_name(Handle vbind) => string name
Returns the vector binding's name.
dt_setval(Handle vbind, Handle pp) => boolean ok
Sets the value of the vector binding to the value of
which must be NULL_OB, a pattern, or a pathset.
dt_getval(Handle vbind) => Handle pp
Return the value of the vector binding vbind. It will be NULL_OB, a
pattern, or a pathset.
9.5 Pattern Matching
All of the matching functions require the target to be a valid, consistant
object. This means that molecules and reactions must be in mod-off state
before calling any of the following functions.
Back to Table of Contents
Handle mol, boolean exist) => pathset
Matches the pattern against the molecule; returns a pathset
indicating the results of the match, or NULL_OB if no match is found or
an error is detected.
The boolean parameter
exist indicates whether an
exhaustive search or a first-only search is to be performed. If exist
is FALSE, an exhaustive search takes place; pathset will contain
all places in the molecule where pattern matches. If
exist is TRUE, the match stops as soon as the first match
is found; pathset will contain just the first path that an exhaustive
search would have found.
Handle mol, boolean exist) => pathset
Matches the pattern pat against the molecule mol as
above, except that each of the paths in the returned pathset contains
just a single atom, the one that matched the "head" atom of the
SMARTS from which pat is derived. Further, no two paths in pathset
will contain the same atom.
Handle mol, boolean exist) => pathset
A unique set of atoms match. Matches the given pattern against
the molecule as with
above, except that each of the paths in the returned pathset is
guaranteed to contain a unique set of atoms (relative to all other
paths in the pathset).
Conceptually one can think of this as
though dt_match() were
performed, then all paths compared to one another. If two paths
contain the same atoms, one of the two (the choice is arbitrary) is
removed from the pathset. Notice that two paths thus compared may
not be equivalent; in particular paths that include cycles may
contain the same atoms but not the same bonds. The resulting pathset
is guaranteed to contain (as determined
by dt_member()) the exact
same number of atoms as a match performed
with dt_match(), but it may
not contain the same number of bonds.
The purpose of this function is to eliminate the "uninteresting"
redundancy in paths that are typically returned by exhaustive
searches using dt_match().
An exhaustive search, by definition, will find a path for each
symmetry in the pattern. For example,
dt_match() will return 12 paths
when the SMARTS c1ccccc1 is applied to the molecule c1ccccc1; once
for each of 6 possible starting atoms, times two for the clockwise
and anticlockwise paths. When
dt_umatch() is applied, only
one path is returned.
The parameter exist is included for consistency; note, however, that
if exist is TRUE, dt_match()
and dt_umatch() are equivalent.
Handle mol, integer limit) => pathset
This is a further restriction of the unique set of atoms match used
by dt_umatch(3). In this case, only non-overlapping paths are returned.
That is, no two paths in the result set will contain the same atom. The
parameter 'limit' works as follows: if 'limit' is zero, returns all
possible paths (exhaustive search). If 'limit' is a positive integer,
returns up to 'limit' answers. Hence, 'limit' can be used to restrict
the number of matches found.
NOTE: the results from dt_xmatch(3) depend on the processing order of
the atoms in the target molecule or reaction. For example, matching
the pattern 'CC' against the molecule 'CCCC' will return two pathsets,
Matching the same pattern against 'C(CC)C' gives one pathset.
In the first case, Carbons #1 and #2 are matched first,
leaving #3 and #4 as the second match. In the second case,
Carbons #2 and #3 are matched first, leaving #1 and #4, which don't
Logically, dt_xmatch(3) performs an exhaustive match and then picks one
of potentially multiple non-overlapping sets of paths for the answer.
Fortunately, although one can think of dt_xmatch(3) working this way,
the actual implementation is much faster.
Go to previous chapter Error Handling
Go to next chapter Fingerprint Toolkit.