.. _chapter_patternmatch:

********************************************************************************
Pattern Matching
********************************************************************************
.. index :: pattern matching

**OEChem TK** includes facilities to perform different types of pattern
(graph) matching.  Graph matching is based on node (atom) and edge
(bond) correspondences.  An atom which satisfies the conditions of a
node in a query graph is said to match.  Likewise, a bond which
satisfies the conditions of an edge in a query graph is said to match.
Pattern matching is the process of identifying groupings of matching
nodes and edges.  Substructure search, or subgraph isomorphism, is the
process of finding a graph match which is less than or equal to a
larger graph.  Maximum common substructure search is the process of
identifying the maximal graph correspondence between two
graphs. Clique detection is the process of finding all possible
correspondences between two graphs within a set of bounds.

.. _section_patternmatch_sss:

Substructure Search
================================================================================

.. index :: substructure search, SMARTS

Substructure searches can be done in **OEChem TK** using the
:ref:`OESubSearch <OEChem_OESubSearch>` class.  The :ref:`OESubSearch <OEChem_OESubSearch>`
class can be initialized with a :ref:`SMARTS <chapter_SMARTS>`
pattern, an :ref:`OEQMolBase <OEChem_OEQMolBase>` query molecule, or an
:ref:`OEMolBase <OEChem_OEMolBase>` with expression options.  The following
example demonstrates how to initialize a :ref:`OESubSearch <OEChem_OESubSearch>`
instance with a :ref:`SMARTS <chapter_SMARTS>` pattern, and perform a
substructure search.

.. oe:source:: SubstructureSearch.cpp
   :language: c++
   :refnum:   1
   :caption:  Simple substructure search example
   :frag:     SNIPPET

.. oe:source:: SubstructureSearch.py
   :language: python
   :refnum:   1
   :caption:  Simple substructure search example
   :frag:     SNIPPET

.. oe:language:: python

	:ref:`Full listing. <listing-SubstructureSearch.py>`



.. oe:source:: SubstructureSearch.java
   :language: java
   :refnum:   1
   :caption:  Simple substructure search example
   :frag:     SNIPPET

.. oe:source:: SubstructureSearch.cs
   :language: csharp
   :refnum:   1
   :caption:  Simple substructure search example
   :frag:     SNIPPET

In :oe:src:`Listing 1<SNIPPET-SubstructureSearch>`, the query pattern is
benzene and the molecule in which the substructure is being searched
for is toluene.  Since benzene is a substructure of toluene the
:oe:meth:`OEChem::OESubSearch::SingleMatch` method will return
``true``.  The :oe:meth:`SingleMatch<OEChem::OESubSearch::SingleMatch>`
method returns ``true`` if a single subgraph isomorphism is detected
in the molecule passed as the function argument.

Using the :oe:meth:`SingleMatch<OEChem::OESubSearch::SingleMatch>`
function  in :oe:src:`Listing 2<SNIPPET-MolFind>`, it is possible to loop through any molecular
file and extract molecules that match a particular :ref:`SMARTS <chapter_SMARTS>`
pattern.

.. oe:source:: MolFind.cpp
   :language: c++
   :refnum:   2
   :caption:  Extracting molecules based upon a substructure
   :frag:     SNIPPET

.. oe:source:: MolFind.py
   :language: python
   :refnum:   2
   :caption:  Extracting molecules based upon a substructure
   :frag:     SNIPPET

.. oe:language:: python

	:ref:`Full listing. <listing-MolFind.py>`



.. oe:source:: MolFind.java
   :language: java
   :refnum:   2
   :caption:  Extracting molecules based upon a substructure
   :frag:     SNIPPET

.. oe:source:: MolFind.cs
   :language: csharp
   :refnum:   2
   :caption:  Extracting molecules based upon a substructure
   :frag:     SNIPPET

The :oe:cls:`OESubSearch<OEChem::OESubSearch>` class is able to
identify the atom and bond correspondences of the pattern and target
structures.  :oe:src:`Listing 3<SNIPPET-AtomMap>` extends the simple match
example to write out all atom correspondences between benzene and
toluene.

.. oe:source:: AtomMap.cpp
   :language: c++
   :refnum:   3
   :caption:  Substructure search with atom mappings
   :frag:     SNIPPET

.. oe:source:: AtomMap.py
   :language: python
   :refnum:   3
   :caption:  Substructure search with atom mappings
   :frag:     SNIPPET

.. oe:language:: python

	:ref:`Full listing. <listing-AtomMap.py>`



.. oe:source:: AtomMap.java
   :language: java
   :refnum:   3
   :caption:  Substructure search with atom mappings
   :frag:     SNIPPET

.. oe:source:: AtomMap.cs
   :language: csharp
   :refnum:   3
   :caption:  Substructure search with atom mappings
   :frag:     SNIPPET

The output of :oe:src:`Listing 3<SNIPPET-AtomMap>` is the following:

.. code-block:: bash

   Match 1 : pattern atoms: 0 1 2 3 4 5 target atoms:  0 1 2 3 4 5
   Match 2 : pattern atoms: 0 1 2 3 4 5 target atoms:  0 5 4 3 2 1
   Match 3 : pattern atoms: 0 1 2 3 4 5 target atoms:  1 2 3 4 5 0
   Match 4 : pattern atoms: 0 1 2 3 4 5 target atoms:  1 0 5 4 3 2
   Match 5 : pattern atoms: 0 1 2 3 4 5 target atoms:  2 3 4 5 0 1
   Match 6 : pattern atoms: 0 1 2 3 4 5 target atoms:  2 1 0 5 4 3
   Match 7 : pattern atoms: 0 1 2 3 4 5 target atoms:  3 4 5 0 1 2
   Match 8 : pattern atoms: 0 1 2 3 4 5 target atoms:  3 2 1 0 5 4
   Match 9 : pattern atoms: 0 1 2 3 4 5 target atoms:  4 5 0 1 2 3
   Match 10 : pattern atoms: 0 1 2 3 4 5 target atoms:  4 3 2 1 0 5
   Match 11 : pattern atoms: 0 1 2 3 4 5 target atoms:  5 0 1 2 3 4
   Match 12 : pattern atoms: 0 1 2 3 4 5 target atoms:  5 4 3 2 1 0


The :oe:meth:`OEChem::OESubSearch::Match` method performs subgraph
isomorphism determination for instances of
:oe:cls:`OEMolBase<OEChem::OEMolBase>` or
:oe:cls:`OEQMolBase<OEChem::OEQMolBase>` and returns an iterator over
all detected subgraphs. Each of the detected subgraphs can be queried
for their atom and bond correspondences. In this particular example,
the benzene substructure is identified twelve times in toluene.  There
are twelve matches because the benzene ring can be rotated around for
6 matches, and then flipped and rotated around for another 6 matches,
yielding a total of 12 matches. Each of the matches differ in their
atom and bond correspondences to the pattern substructure.

A match or subgraph is considered unique if it differs from all other
subgraphs found previously by at least one atom. When doing unique
matching, two subgraph matches which cover the same atoms, albeit in
different orders, will be called duplicates and it will be discarded.
In order to retrieve only unique matches, the
:oe:meth:`Match<OEChem::OESubSearch::Match>` method has to be called
with a second argument being set to ``true``.  In :oe:src:`Listing
3<SNIPPET-AtomMap>`, using unique search would yield only a single match for
benzene in toluene.

An :ref:`OESubSearch <OEChem_OESubSearch>` may be initialized using a
:ref:`SMARTS <chapter_SMARTS>` or a query molecule
:oe:cls:`OEQMolBase<OEChem::OEQMolBase>`. Query molecules must have
atom and bond expressions built for the entire molecule to be able to
initialize the search object (see
:oe:meth:`OEChem::OEQMolBase::BuildExpressions` in the API).

:oe:meth:`OEChem::OESubSearch::GetPattern` returns a read-only
reference to the query molecule contained in an instance of
:ref:`OESubSearch <OEChem_OESubSearch>`.  :ref:`OEQMolBase <OEChem_OEQMolBase>` methods can
be used to interrogate the returned :ref:`OEQMolBase <OEChem_OEQMolBase>`
reference.

The :oe:meth:`OEChem::OESubSearch::SetMaxMatches` method sets the
maximum number of subgraphs to be returned by the
:oe:meth:`OEChem::OESubSearch::Match` method. Once the maximum number
of subgraphs has been found the search is terminated. By default, an
:ref:`OESubSearch <OEChem_OESubSearch>` is constructed with the maximum number of
matches set to ``1024``. The constraint on the maximum number of matches
can be removed by calling :oe:meth:`OEChem::OESubSearch::SetMaxMatches`
with a value of ``0``.

When an :ref:`OESubSearch <OEChem_OESubSearch>` object is initialized with a query molecule,
the :oe:meth:`OEChem::OESubSearch::Match` method returns a match between the copy
of the query molecule stored inside the  :ref:`OESubSearch <OEChem_OESubSearch>` object and the
target molecule.

The :oe:src:`Listing 4<SNIPPET-SubstructureSearchMatch>` example below
illustrates how to reconstruct matches between the original query
molecule that is used to initialize a search and a target molecule.

.. oe:language:: c++

   In order to keep track of the atoms, each atom of the query molecule is
   attached to itself before the
   :ref:`OESubSearch <OEChem_OESubSearch>` object is constructed.
   After the matches are returned by calling the
   :oe:cls:`OEChem::OESubSearch::Match` the original atoms can be
   retrieved by these pointers.

.. oe:language:: python java csharp

   In order to keep track of the atoms, each atom of the query molecule is
   marked with its own unique atom index before the
   :ref:`OESubSearch <OEChem_OESubSearch>` object is constructed.
   After the matches are returned by calling the
   :oe:cls:`OEChem::OESubSearch::Match` the original atoms can be
   retrieved by these indices.

.. oe:source:: SubstructureSearchMatch.cpp
   :language: c++
   :refnum:   4
   :caption:  Substructures match for query molecule
   :frag:     SNIPPET

.. oe:source:: SubstructureSearchMatch.py
   :language: python
   :refnum:   4
   :caption:  Substructures match for query molecule
   :frag:     SNIPPET

.. oe:language:: python

	:ref:`Full listing. <listing-SubstructureSearchMatch.py>`



.. oe:source:: SubstructureSearchMatch.java
   :language: java
   :refnum:   4
   :caption:  Substructures match for query molecule
   :frag:     SNIPPET

.. oe:source:: SubstructureSearchMatch.cs
   :language: csharp
   :refnum:   1
   :caption:  Substructures match for query molecule
   :frag:     SNIPPET

.. seealso::

   * [Figueras-1972]_
   * [Ullman-1976]_

.. _section_patternmatch_mcss:

Maximum Common Substructure Search
================================================================================

.. index :: maximum common substructure search, MCSS

The maximum common substructure (henceforth MCS) of two molecular
graphs can be identified using the :ref:`OEMCSSearch <OEChem_OEMCSSearch>` class.
:oe:src:`Listing 5<SNIPPET-MaximumCommonSS>` demonstrates how to initialize an
:ref:`OEMCSSearch <OEChem_OEMCSSearch>` object, perform a maximum common
substructure search, and then retrieve the matches.

.. oe:source:: MaximumCommonSS.cpp
   :refnum:   5
   :language: c++
   :caption:  Maximum common substructure search
   :frag:     SNIPPET

.. oe:source:: MaximumCommonSS.py
   :refnum:   5
   :language: python
   :caption:  Maximum common substructure search
   :frag:     SNIPPET

.. oe:source:: MaximumCommonSS.java
   :refnum:   5
   :language: java
   :caption:  Maximum common substructure search
   :frag:     SNIPPET

.. oe:source:: MaximumCommonSS.cs
   :refnum:   5
   :language: csharp
   :caption:  Maximum common substructure search
   :frag:     SNIPPET

The first molecule, ``pattern``, is dopamine, and the second molecule,
``target``, is a dopamine analog.  The :ref:`OEMCSSearch <OEChem_OEMCSSearch>`
instance is initialized with the dopamine query, atom and bond
expressions, and the type of the search.

.. oe:source:: MaximumCommonSS.cpp
   :language: c++
   :frag:     SNIPPET-INIT
   :noindent:

.. oe:source:: MaximumCommonSS.py
   :language: python
   :frag:     SNIPPET-INIT
   :noindent:

.. oe:source:: MaximumCommonSS.java
   :language: java
   :frag:     SNIPPET-INIT
   :noindent:

.. oe:source:: MaximumCommonSS.cs
   :language: csharp
   :frag:     SNIPPET-INIT
   :noindent:

The atom and bond expressions define criteria for atom and bond
equivalence used during the search and are defined in the
:oe:constns:`OEChem::OEExprOpts` namespace.  See the
:ref:`section_patternmatch_OEExprOpts` section for more information.

An :ref:`OEMCSSearch <OEChem_OEMCSSearch>` object can also be constructed from a
:ref:`SMARTS <chapter_SMARTS>` string directly. In this case standard
SMARTS matching rules apply for what constitutes a match.  If it is
constructed with an :ref:`OEQMolBase <OEChem_OEQMolBase>`, then whatever atom
and bond expressions have been applied to the
:ref:`OEQMolBase <OEChem_OEQMolBase>` will apply in the MCS search.

The last argument of the initialization defines the search type,
either :oe:const:`Approximate<OEChem::OEMCSType::Approximate>` or
:oe:const:`Exhaustive<OEChem::OEMCSType::Exhaustive>`. The difference
between the two search types is detailed in the
:ref:`section_patternmatch_mcss_rearchmode` section. This argument is
optional, if it is not specified, then the
:oe:const:`exhaustive<OEChem::OEMCSType::Exhaustive>` method is
employed.

During the search process, each identified common substructure is
evaluated by a scoring function and only substructures with the best
score are retained.  The :oe:meth:`OEChem::OEMCSSearch::SetMCSFunc`
method provides an ability to set the scoring function of an
:ref:`OEMCSSearch <OEChem_OEMCSSearch>` object, thereby influencing the result of
the maximum common substructure search process.  See the
:ref:`section_patternmatch_mcss_score` section for more information.

.. oe:source:: MaximumCommonSS.cpp
   :language: c++
   :frag:     SNIPPET-SCORE
   :noindent:

.. oe:source:: MaximumCommonSS.py
   :language: python
   :frag:     SNIPPET-SCORE
   :noindent:

.. oe:source:: MaximumCommonSS.java
   :language: java
   :frag:     SNIPPET-SCORE
   :noindent:

.. oe:source:: MaximumCommonSS.cs
   :language: csharp
   :frag:     SNIPPET-SCORE
   :noindent:

The :oe:meth:`OEChem::OEMCSSearch::Match` method returns an iterator
over the maximum common substructures.

.. oe:source:: MaximumCommonSS.cpp
   :language: c++
   :frag:     SNIPPET-MATCH
   :noindent:

.. oe:source:: MaximumCommonSS.py
   :language: python
   :frag:     SNIPPET-MATCH
   :noindent:

.. oe:source:: MaximumCommonSS.java
   :language: java
   :frag:     SNIPPET-MATCH
   :noindent:

.. oe:source:: MaximumCommonSS.cs
   :language: csharp
   :frag:     SNIPPET-MATCH
   :noindent:


The :ref:`OEMatchBase <OEChem_OEMatchBase>` is then passed as an argument to the
:oe:func:`OEChem::OESubsetMol` function, and subsequently converted
into a :term:`SMILES` string.

.. oe:source:: MaximumCommonSS.cpp
   :language: c++
   :frag:     SNIPPET-SUBSET
   :noindent:

.. oe:source:: MaximumCommonSS.py
   :language: python
   :frag:     SNIPPET-SUBSET
   :noindent:

.. oe:source:: MaximumCommonSS.java
   :language: java
   :frag:     SNIPPET-SUBSET
   :noindent:

.. oe:source:: MaximumCommonSS.cs
   :language: csharp
   :frag:     SNIPPET-SUBSET
   :noindent:

The detected maximum common substructure of the example program is
depicted in :ref:`Figure: Example of MCSS<figure_mcss_dopamine>`. The following is the output
of the program in :oe:src:`Listing 5<SNIPPET-MaximumCommonSS>`:

.. code-block:: bash

   Match 1:
   pattern atoms: 0 1 2 3 4 5 6 7 8 9
   target atoms:  7 5 3 4 1 2 0 8 9 10
   match smiles = CCc1ccc(c(c1)O)O


.. _figure_mcss_dopamine:

.. figure:: images/OEMCSSearch.*
   :scale: 100
   :align: center

   **Example of MCSS**

   *The maximum common substructure (highlighted by light blue) of dopamine and dopamine analog.*


The maximum common substructure search can perform unique or
non-unique substructure searching by changing the second argument of
the :oe:meth:`OEChem::OEMCSSearch::Match` method. The default is a
non-unique search.

By definition, a match or subgraph is considered unique if it differs
from all other subgraphs found previously by at least one atom or
bond.  Additionally, it is also considered unique if the pattern
subgraph is mapped to a different part of the target.

:ref:`Figure: Unique match<figure_mcss_umatch>` shows an example in which the two matches
are identified using the unique search method.  Even though the two
obtained subgraphs are identical, they represent different mappings
between the pattern and the target, therefore they are both considered
unique. Using a non-unique search would result in four matches, since
the phenol can flip, yielding two additional matches.

.. _figure_mcss_umatch:

.. figure:: images/OEMCSSearchUnique.*
   :scale: 100
   :align: center

   **Unique match**

   *Example for unique maximum common substructures*


The search space of a maximum common subgraph determination can be
restricted by constraining pairs of atoms or bonds to be mapped onto
one another in all subgraph solutions.  This is done using the
:oe:meth:`OEChem::OEMCSSearch::AddConstraint` method. Failure to
satisfy atom or bond pairwise constraints will prevent any subgraph
solutions from being identified. Constraints are considered satisfied
in subgraphs which do not contain any constrained atoms or bonds in
either the pattern or target molecules.

The :oe:meth:`AddConstraint<OEChem::OEMCSSearch::AddConstraint>` method
returns ``true`` if a constraint is added successfully. If the pattern
atom or bond in the :ref:`OEMatchPair <OEChem_OEMatchPair>` does not exist as
part of the query molecule created in the initialization of the
:ref:`OESubSearch <OEChem_OESubSearch>` object then
:oe:meth:`AddConstraint<OEChem::OEMCSSearch::AddConstraint>` will
return ``false``. Multiple calls to
:oe:meth:`AddConstraint<OEChem::OEMCSSearch::AddConstraint>` using the
same pattern atom or bond will cause previously stored constraints to
be overwritten as constraints are mutually exclusive. It is impossible
to satisfy multiple simultaneous constraints for a single pattern atom
or bond, hence the exclusivity.

A read-only reference to the query molecule
:ref:`OEQMolBase <OEChem_OEQMolBase>` contained in an instance of
:ref:`OEMCSSearch <OEChem_OEMCSSearch>` can be obtained with the
:oe:meth:`GetPattern<OEChem::OEMCSSearch::GetPattern>` method.  Note
that if the :ref:`OEMCSSearch <OEChem_OEMCSSearch>` was constructed with an
:ref:`OEQMolBase <OEChem_OEQMolBase>`, the returned :ref:`OEQMolBase <OEChem_OEQMolBase>`
is a separate object. :ref:`OEQMolBase <OEChem_OEQMolBase>` methods can then be
used to interrogate the returned :ref:`OEQMolBase <OEChem_OEQMolBase>`
reference.

The :oe:meth:`SetMaxMatches<OEChem::OEMCSSearch::SetMaxMatches>` method
alters the maximum number of maximum common subgraph matches that will
be returned by the :oe:meth:`OEChem::OEMCSSearch::Match` method. The
search for maximum common substructures will not terminate immediately
upon reaching this limit. The maximum common subgraph cannot be known
unless the MCS is composed of all atoms and bonds of at least one of
the graphs being compared. The limit of subgraphs to be returned may
be reached with a smaller subgraph than the maximum. In such a case
the search continues for larger subgraphs until the search is
exhausted. :oe:meth:`OEChem::OEMCSSearch::Match` will return the first
``N`` maximum common subgraphs where ``N`` is less than or equal to the
maximum match limit.  The default limit set upon construction of an
:ref:`OEMCSSearch <OEChem_OEMCSSearch>` instance is ``1024`` matches.

The :oe:meth:`SetMinAtoms<OEChem::OEMCSSearch::SetMinAtoms>` method
sets the minimum number of atoms required of a subgraph match to be
returned by a MCS search. For example, changing the parameter of
:oe:meth:`SetMinAtoms<OEChem::OEMCSSearch::SetMinAtoms>` in
:oe:src:`Listing 5<SNIPPET-MaximumCommonSS>` to 11 would result in no solution
since there are only 10 atoms of the largest maximum common
substructure (see :ref:`Figure: Example of MCSS<figure_mcss_dopamine>`).

.. oe:source:: MaximumCommonSS.cpp
   :language: c++
   :frag:     SNIPPET-MINATOMS
   :noindent:

.. oe:source:: MaximumCommonSS.py
   :language: python
   :frag:     SNIPPET-MINATOMS
   :noindent:

.. oe:source:: MaximumCommonSS.java
   :language: java
   :frag:     SNIPPET-MINATOMS
   :noindent:

.. oe:source:: MaximumCommonSS.cs
   :language: csharp
   :frag:     SNIPPET-MINATOMS
   :noindent:


A single atom can be a perfectly valid maximum common subgraph,
however, for many applications such a small subgraph may not be
considered useful.  Setting the minimum number of atoms to a useful
size prevents unproductive subgraph matches from being returned by the
:oe:meth:`OEChem::OEMCSSearch::Match` method. The default set upon
construction of an :ref:`OEMCSSearch <OEChem_OEMCSSearch>` instance for the
minimum number of atoms is one.

.. _section_patternmatch_mcss_rearchmode:

Exhaustive and approximate MCSS
================================================================================

The maximum common substructure search can be performed in two
different modes: a very fast method,
:oe:const:`OEChem::OEMCSType::Approximate`, or a more comprehensive
method, :oe:const:`OEChem::OEMCSType::Exhaustive`.

The type of the :ref:`OEMCSSearch <OEChem_OEMCSSearch>` can be set at
initialization.  The default value is
:oe:const:`OEChem::OEMCSType::Exhaustive`.


The approximate method is based on traversing through pre-defined
paths of the query structure and trying to map the visited query atoms
into target atoms. Because these pre-defined paths represent only a
fraction of all possible paths of a compound, it is not guaranteed
that the approximate method can find the largest and all common
substructures. Significant difference between the detected matches of the
two methods could exist in cases when the query or target structure
contains complex ring systems (fused or bridged) or stereo centers.
However, comparing the two methods for thousands of structures
revealed that these cases are rare and the approximate method provides
a good trade-off between identifying MCS matches accurately and doing
it 3 to 6 times faster than the exhaustive method.

:ref:`Figure: Approximate MCSS<figure_mcss_approximate>` and
:ref:`Figure: Exhaustive MCSS<figure_mcss_exhaustive>`,
show an example where the substructure identified by the approximate
method is smaller by one atom then the solution identified by the
exhaustive method.

.. _figure_mcss_approximate:

.. figure:: images/OEMCSSearchApproximate.*
   :scale: 100
   :align: center

   **Approximate MCSS**

   *Example for maximum common substructure identified by the approximate method.*


.. _figure_mcss_exhaustive:

.. figure:: images/OEMCSSearchExhaustive.*
   :scale: 100
   :align: center

   **Exhaustive MCSS**

   *Example for maximum common substructure identified by the exhaustive method.*


.. note::

   Using the approximate MCS is recommended if the speed of the search
   is crucial.


.. _section_patternmatch_mcss_score:

MCS scoring functions
================================================================================

:ref:`OEMCSFunc <OEChem_OEMCSFunc>` is an abstract base-class that defines the
API used for scoring subgraph matches. The scores generated by
implementations of :ref:`OEMCSFunc <OEChem_OEMCSFunc>` influence the sorting
and retention of maximum common subgraph matches generated by the
:ref:`OEMCSSearch <OEChem_OEMCSSearch>` class. The scoring function is set by the
:oe:meth:`OEChem::OEMCSSearch::SetMCSFunc` method.

It is important to mention that using different scoring functions does
not alter the way the search space is traversed to identify common
substructures. It affects only how these identified substructures are
evaluated.

Four implementations of the :ref:`OEMCSFunc <OEChem_OEMCSFunc>` class are
available in **OEChem TK**:

.. rubric:: OEMCSMaxAtoms

The :ref:`OEMCSMaxAtoms <OEChem_OEMCSMaxAtoms>` class is designed to order
maximum common substructure matches by the maximum number of atoms
included in the graph match.  If two matches have the same number
of atoms, then the tie is split based on the number of bonds
contained in the match.
(See example in :ref:`figure_mcss_maxatoms`.)

**Scoring function:**

:math:`num.\ of\ mapped\ atoms + \frac{num.\ of\ mapped\ bonds}{100}`

.. _figure_mcss_maxatoms:

.. figure:: images/OEMCSSearchOEMCSMaxAtoms.*
   :scale: 100
   :align: center

   **Scoring A**

   *Retrieved matches using 'OEMCSMaxAtoms' as scoring function.*


.. rubric:: OEMCSMaxBonds

The :oe:cls:`OEMCSMaxBonds<OEChem::OEMCSMaxBonds>` class is designed to
order maximum common substructure matches by the maximum number of bonds
included in the graph match.
If two matches have the same number of bonds, then the tie is split based on the
number of atoms contained in the match.
(See example in :ref:`figure_mcss_maxbonds`.)

**Scoring function:**

:math:`num.\ of\ mapped\ bonds + \frac{num.\ of\ mapped\ atoms}{100}`

.. _figure_mcss_maxbonds:

.. figure:: images/OEMCSSearchOEMCSMaxBonds.*
   :scale: 100
   :align: center

   **Scoring B**

   *Retrieved matches using 'OEMCSMaxBonds' as scoring function.*


.. rubric:: OEMCSMaxAtomsCompleteCycles

The  :oe:cls:`OEMCSMaxAtomsCompleteCycles<OEChem::OEMCSMaxAtomsCompleteCycles>`
class is the same  as the :oe:cls:`OEMCSMaxAtoms<OEChem::OEMCSMaxAtoms>` with
the addition of penalizing cyclic query bonds that are not mapped to any target
bonds, thereby giving priority to matches which contain complete cycles
common to both the pattern and the target structure.
(See example in :ref:`figure_mcss_maxatomscc`.)

**Scoring function:**

:math:`num.\ of\ mapped\ atoms + \frac{num.\ of\ mapped\ bonds}{100} - penalty \times num.\ of\ unmapped\ cyclic\ query\ bonds`

The default penalty for each unmapped cyclic query bond is 1.0.

.. _figure_mcss_maxatomscc:

.. figure:: images/OEMCSSearchOEMCSMaxAtomsCompleteCycles.*
   :scale: 100
   :align: center

   **Scoring C**

   *Retrieved matches using 'OEMCSMaxAtomsCompleteCycles' as scoring function.*


.. rubric:: OEMCSMaxBondsCompleteCycles

The :ref:`OEMCSMaxBondsCompleteCycles <OEChem_OEMCSMaxBondsCompleteCycles>` class is the same
as the :ref:`OEMCSMaxBonds <OEChem_OEMCSMaxBonds>` class with the
addition of penalizing cyclic query bonds that are not mapped to
any target bonds, thereby giving priority to matches which contain
complete cycles common to both the pattern and the target
structure.
(See example in :ref:`figure_mcss_maxbondscc`.)

**Scoring function:**

:math:`num.\ of\ mapped\ bonds + \frac{num.\ of\ mapped\ atoms}{100} - penalty \times  num.\ of\ unmapped\ cyclic\ query\ bonds`

The default penalty for each unmapped cyclic query bond is 1.0.

.. _figure_mcss_maxbondscc:

.. figure:: images/OEMCSSearchOEMCSMaxAtomsCompleteCycles.*
   :scale: 100
   :align: center

   **Scoring D**

   *Retrieved matches using  'OEMCSMaxBondsCompleteCycles' as scoring function.*

It is important to remember that not only matches with the highest
score are retained, but also matches with scores higher than the best
score rounded down to the highest integer. In the example shown in
:ref:`figure_mcss_maxbonds` three common substructures are detected
using the :ref:`OEMCSMaxBonds <OEChem_OEMCSMaxBonds>` scoring function. The first
two matches are scored ``5.06``, since they are composed of 5 mapped
bonds and 6 mapped atoms. There is only one other match which scored
higher than 5.0, this is the third retained match with a score of
``5.05``.

.. seealso::

   * [Bunke-2002]_
   * [McGregor-1982]_
   * [Raymond-2002]_
   * [Wang-T-1997]_

.. _section_patternmatch_clique:

Clique Search
================================================================================

Clique detection is a bounded common substructure search.  It is a
useful search method in cases where common substructures other than
the maximum common substructure need to be identified.  The following
example demonstrates a clique search.

.. oe:source:: CliqueSearch.cpp
   :language: c++
   :caption:  Clique search example
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: CliqueSearch.py
   :language: python
   :caption:  Clique search example
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: CliqueSearch.java
   :language: java
   :caption:  Clique search example
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: CliqueSearch.cs
   :language: csharp
   :caption:  Clique search example
   :refnum:   6
   :frag:     SNIPPET


The same molecules and expression options are used as in
:oe:src:`Listing 5<SNIPPET-MaximumCommonSS>`, however, an iterator over all
identified cliques is returned by the
:oe:meth:`OEChem::OECliqueSearch::Match` method.  The
:oe:meth:`OEChem::OECliqueSearch::SetSaveRange` method bounds the
search. In this case, cliques returned will only differ by five nodes
relative to the maximum common substructure.  The atom correspondences
for each of the returned cliques are printed in the example program.


.. _section_patternmatch_OEExprOpts:

OEExprOpts Namespace
================================================================================

Pattern matching in **OEChem TK** is always done using query molecules or
query graphs. Non-query molecules, *i.e.* those that are defined only
by :ref:`OEMolBase <OEChem_OEMolBase>` abstract base-class must be converted
into a query molecule. Conversion into a query molecule is controlled
using the values in the :oe:constns:`OEChem::OEExprOpts` namespace.
Expression options can either be specified in the constructor for an
:ref:`OEQMol <OEChem_OEQMol>`, or using the convenience constructors in the
pattern matching classes, :ref:`OESubSearch <OEChem_OESubSearch>`,
:ref:`OEMCSSearch <OEChem_OEMCSSearch>`, :ref:`OECliqueSearch <OEChem_OECliqueSearch>` which
take expression options as arguments.

:ref:`Figure: Default example<figure_expr_default>` shows an example where the maximum common
substructure search is performed using the
:oe:const:`OEChem::OEExprOpts::DefaultAtoms` and
:oe:const:`OEChem::OEExprOpts::DefaultBonds` options.

.. _figure_expr_default:

.. figure:: images/OEExprOpts-Default-Default.*
   :scale: 100
   :align: center

   **Default example**

   *Example of maximum common substructure search with 'DefaultAtoms' and 'DefaultBonds' options*

The :oe:const:`OEChem::OEExprOpts::DefaultAtoms` option means that two
atoms are considered to be equivalent if they have the same atomic
number, aromaticity, and formal charge.  The
:oe:const:`OEChem::OEExprOpts::DefaultBonds` option means that two
bonds can be mapped to each other if they have the same bond order and
aromaticity.

.. oe:source:: MCSSOEExprOpts.cpp
   :language: c++
   :caption:  MCSS with atom and bond expressions
   :refnum:   7
   :frag:     SNIPPET

.. oe:source:: MCSSOEExprOpts.py
   :language: python
   :caption:  MCSS with atom and bond expressions
   :refnum:   7
   :frag:     SNIPPET

.. oe:source:: MCSSOEExprOpts.java
   :language: java
   :caption:  MCSS with atom and bond expressions
   :refnum:   7
   :frag:     SNIPPET

.. oe:source:: MCSSOEExprOpts.cs
   :language: csharp
   :caption:  MCSS with atom and bond expressions
   :refnum:   7
   :frag:     SNIPPET

The best way to understand how various atom and bond expressions
influence the pattern matching is to change the atom and bond
expressions in :oe:src:`Listing 7<SNIPPET-MCSSOEExprOpts>` and compare the
obtained matches.

.. oe:source:: MCSSOEExprOpts.cpp
   :language: c++
   :frag:     SNIPPET-EXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.py
   :language: python
   :frag:     SNIPPET-EXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.java
   :language: java
   :frag:     SNIPPET-EXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.cs
   :language: csharp
   :frag:     SNIPPET-EXPR
   :noindent:

After constructing the pattern molecule, the
:oe:meth:`BuildExpressions<OEChem::OEQMolBase::BuildExpressions>`
method defines the level of atom and bond matching between the pattern
molecule and any target molecule.


.. oe:source:: MCSSOEExprOpts.cpp
   :language: c++
   :frag:     SNIPPET-BUILDEXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.py
   :language: python
   :frag:     SNIPPET-BUILDEXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.java
   :language: java
   :frag:     SNIPPET-BUILDEXPR
   :noindent:

.. oe:source:: MCSSOEExprOpts.cs
   :language: csharp
   :frag:     SNIPPET-BUILDEXPR
   :noindent:

By modifying the atom and bond expression options, very diverse
pattern matching can be performed. :ref:`Figure: Example A<figure_expr_A>` --
:ref:`Figure: Example E<figure_expr_E>` show several examples where maximum common
substructure searches are performed for the same query and target
molecules, but with various atom and bond expression options.

In the first example in :ref:`Figure: Example A<figure_expr_A>`, the
:oe:const:`OEChem::OEExprOpts::ExactAtoms` expression option is used to
give a higher degree of discrimination of the equivalence of atoms,
*i.e.* atoms can only be mapped to each other if they have the same
degree, number of hydrogens, chirality, mass, and ring membership, in
addition to the requirements of the
:oe:const:`OEChem::OEExprOpts::DefaultAtoms` option.

.. _figure_expr_A:

.. figure:: images/OEExprOpts-Exact-Default.*
   :scale: 100
   :align: center

   **Example A**

   *`ExactAtoms` and 'DefaultBonds`*


:ref:`Figure: Example B<figure_expr_B>` -- :ref:`Figure: Example E<figure_expr_E>`
show examples where the
discrimination capability of the
:oe:const:`OEChem::OEExprOpts::DefaultAtoms` is decreased by adding
various modifiers.  For example, using the
:oe:const:`OEChem::OEExprOpts::EqAromatic` modifier, atoms in any
aromatic ring systems are considered equivalent. As a result, the
pyridine and pyrimidine ring can be mapped to each other in
:ref:`Figure: Example B<figure_expr_B>`. Similarly,
:oe:const:`OEChem::OEExprOpts::EqHalogen` (:ref:`Figure: Example C<figure_expr_C>`) and
:oe:const:`OEChem::OEExprOpts::EqONS` (:ref:`Figure: Example D<figure_expr_D>`) define
equivalency between halogen atoms and oxygen-nitrogen-sulfur atoms,
respectively.  Using :oe:const:`OEChem::OEExprOpts::EqCAliphaticONS`
(:ref:`Figure: Example E<figure_expr_E>`) an aliphatic query carbon atom is considered
equivalent to any oxygen, nitrogen, or sulfur atom.


.. _figure_expr_B:

.. figure:: images/OEExprOpts-DefaultEqArom-Default.*
   :scale: 100
   :align: center

   **Example B**

   *'DefaultAtoms|EqAromatic' and 'DefaultBonds'*


.. _figure_expr_C:

.. figure:: images/OEExprOpts-DefaultEqHal-Default.*
   :scale: 100
   :align: center

   **Example C**

   *'DefaultAtoms|EqHalogen' and 'DefaultBonds'*


.. _figure_expr_D:

.. figure:: images/OEExprOpts-DefaultEqONS-Default.*
   :scale: 100
   :align: center

   **Example D**

   *'DefaultAtoms|EqONS' and 'DefaultBonds'*


.. _figure_expr_E:

.. figure:: images/OEExprOpts-DefaultEqCAlipONS-Default.*
   :scale: 100
   :align: center

   **Example E**

   *'DefaultAtoms|EqCAliphaticONS' and 'DefaultBonds'*

Similar modifiers exist for altering bond equivalency.
:ref:`Figure: Example F<figure_expr_F>` shows an example where single and double bonds
are considered identical when
:oe:const:`OEChem::OEExprOpts::EqSingleDouble` modifier is utilized.


.. _figure_expr_F:

.. figure:: images/OEExprOpts-Default-DefaultEqSingleDouble.*
   :scale: 100
   :align: center

   **Example F**

   *'DefaultAtoms' and 'DefaultBonds|EqSingleDouble'*

The last example in :ref:`Figure: Example G<figure_expr_G>` represents a very
unrestrained search, where both the atom and bond expression options
have weak discrimination power.

.. _figure_expr_G:

.. figure:: images/EqAromEqCAlONSEqHalEqONSEqSnglDbl.*
   :scale: 100
   :align: center

   **Example G**

   *'DefaultAtoms|EqAromatic|EqCAliphaticONS|EqHalogen|EqONS' and 'DefaultBonds|EqSingleDouble'*

Even though only maximum common substructure search examples are
presented here, atom and bond expression options can be similarly used
with substructure searches or clique detections.  For a full
description of expression options and their usage please refer to the
:oe:constns:`OEChem::OEExprOpts` namespace section in **OEChem TK** API.
