.. _chapter_user_defined:

********************************************************************************
User-defined Fingerprint
********************************************************************************

The previous :ref:`chapter_fingerprint` chapter showed how to create
circular, path and tree fingerprints with default parameters.
These default parameters are calibrated on the Briem-Lessel
[Briem-Lessel-2000]_, Hert-Willett [Hert-Willett-2004]_ and Grant
[Grant-2006]_ benchmarks.

However, the **GraphSim TK** also provides facilities to construct
user-defined fingerprints.
When constructing a user-defined fingerprint, the following
parameters have to be considered:

#. Atom and bond typing that define which atom and bond properties are
   encoded into the fingerprints
   (see the :ref:`section_user_defined_atom_bond_typing` section)

#. Size of the fragments that are exhaustively enumerated during the
   fingerprint generation
   (see the :ref:`section_user_defined_length` section)

#. Size of the generated fingerprint (in bits)
   (see the :ref:`section_user_defined_bitsize` section)

The following code snippet shows how to generate a ``1024`` bit long
fingerprint that encodes paths from ``0`` up to ``5`` bonds in length
with default atom and bond properties defined by the
:oe:const:`OEGraphSim::OEFPAtomType::DefaultAtom` and
:oe:const:`OEGraphSim::OEFPBondType::DefaultBond` constants,
respectively.

.. oe:source:: MakePathFP.cpp
   :language: c++
   :noindent:
   :frag:     SNIPPET-MAKE-PATH-3

.. oe:source:: MakePathFP.py
   :language: python
   :noindent:
   :frag:     SNIPPET-MAKE-PATH-3

.. oe:language:: python

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

.. oe:source:: MakePathFP.java
   :language: java
   :noindent:
   :frag:     SNIPPET-MAKE-PATH-3

.. oe:source:: MakePathFP.cs
   :language: csharp
   :noindent:
   :frag:     SNIPPET-MAKE-PATH-3


.. warning::

   Two fingerprints which are generated with different parameters
   will have different fingerprint types!

In :oe:src:`Listing 14<SNIPPET-PATH-FP-TYPE-PathFPType>`, two fingerprints are generated with
different parameters, namely they have a different number of bits.
This means that they also have different types, therefore,
no similarity value can be calculated between them.

.. oe:source:: PathFPType.cpp
   :language: c++
   :refnum:   14
   :caption:  Example of different path fingerprint types
   :frag:     SNIPPET-PATH-FP-TYPE

.. oe:source:: PathFPType.py
   :language: python
   :refnum:   14
   :caption:  Example of different path fingerprint types
   :frag:     SNIPPET-PATH-FP-TYPE

.. oe:language:: python

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

.. oe:source:: PathFPType.java
   :language: java
   :refnum:   14
   :caption:  Example of different path fingerprint types
   :frag:     SNIPPET-PATH-FP-TYPE

.. oe:source:: PathFPType.cs
   :language: csharp
   :refnum:   14
   :caption:  Example of different path fingerprint types
   :frag:     SNIPPET-PATH-FP-TYPE

The output of :oe:src:`Listing 14<SNIPPET-PATH-FP-TYPE-PathFPType>` is the following:

::

   same fingerprint types = False
   Fatal: fingerprint type mismatch!


.. _section_user_defined_atom_bond_typing:

Atom and Bond Typing
================================================================================

:oe:src:`Listing 15<SNIPPET-ATOMTYPING-FPAtomTyping>` shows how to generate fingerprints for
two molecules with various atom and bond types
(depicted in :ref:`Example molecules<figure_path_atom_bond_typing>`).
Reducing the number of atom and bond properties increases the similarity
between the two molecules (*i.e.* their
:oe:const:`Tanimoto<OEGraphSim::OESimMeasure::Tanimoto>` similarity).
At the end, when only the topology of two molecules is considered,
*i.e.*, whether or not their atoms and bonds belong to any ring system,
the fingerprints of the two molecules become identical.

These effects are illustrated in
:ref:`Table: Examples of depiction molecule similarity based on fingerprints<table_atom_typing_examples>`.

.. seealso::

   * :ref:`oegraphsim_section_visualizing_molecule_similarity` section


.. oe:source:: FPAtomTyping.cpp
   :language: c++
   :refnum:   15
   :caption:  Similarity calculation with various atom/bond typing
   :frag:     SNIPPET-ATOMTYPING

.. oe:source:: FPAtomTyping.py
   :language: python
   :refnum:   15
   :caption:  Similarity calculation with various atom/bond typing
   :frag:     SNIPPET-ATOMTYPING

.. oe:language:: python

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


.. oe:source:: FPAtomTyping.java
   :language: java
   :refnum:   15
   :caption:  Similarity calculation with various atom/bond typing
   :frag:     SNIPPET-ATOMTYPING

.. oe:source:: FPAtomTyping.cs
   :language: csharp
   :refnum:   15
   :caption:  Similarity calculation with various atom/bond typing
   :frag:     SNIPPET-ATOMTYPING


.. _figure_path_atom_bond_typing:

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

   **Example molecules**


The output of :oe:src:`Listing 15<SNIPPET-ATOMTYPING-FPAtomTyping>` is the following:

::

   Tanimoto(A,B) = 0.166
   Tanimoto(A,B) = 0.241
   Tanimoto(A,B) = 0.592
   Tanimoto(A,B) = 1.000

.. _table_atom_typing_examples:

.. list-table:: **Examples of depiction molecule similarity based on fingerprints**

   * - .. image:: images/FingerPrintAtomTypingExampleA.*
     - .. image:: images/FingerPrintAtomTypingExampleB.*

   * - .. image:: images/FingerPrintAtomTypingExampleC.*
     - .. image:: images/FingerPrintAtomTypingExampleD.*



:ref:`Table: Atom typing options<table_user_defined_atom_typing>`
and
:ref:`Table: Bond typing options<table_user_defined_bond_typing>`
list the currently available typing options.

.. _table_user_defined_atom_typing:

.. list-table:: Atom typing options
  :widths: 100 100
  :header-rows: 1

  * - atom typing constant
    - encoded atom property

  * - :oe:const:`OEGraphSim::OEFPAtomType::Aromaticity`
    - :oe:meth:`OEChem::OEAtomBase::IsAromatic`

  * - :oe:const:`OEGraphSim::OEFPAtomType::AtomicNumber`
    - :oe:meth:`OEChem::OEAtomBase::GetAtomicNum`

  * - :oe:const:`OEGraphSim::OEFPAtomType::Chiral`
    - :oe:meth:`OEChem::OEAtomBase::IsChiral`

  * - :oe:const:`OEGraphSim::OEFPAtomType::FormalCharge`
    - :oe:meth:`OEChem::OEAtomBase::GetFormalCharge`

  * - :oe:const:`OEGraphSim::OEFPAtomType::HCount`
    - :oe:meth:`OEChem::OEAtomBase::GetTotalHCount`

  * - :oe:const:`OEGraphSim::OEFPAtomType::HvyDegree`
    - :oe:meth:`OEChem::OEAtomBase::GetHvyDegree`

  * - :oe:const:`OEGraphSim::OEFPAtomType::Hybridization`
    - :oe:meth:`OEChem::OEAtomBase::GetHyb`

  * - :oe:const:`OEGraphSim::OEFPAtomType::InRing`
    - :oe:meth:`OEChem::OEAtomBase::IsInRing`

.. _table_user_defined_atomic_modifiers:

.. list-table:: Atomic number modifiers
  :widths: 100 100
  :header-rows: 1


  * - :oe:const:`OEGraphSim::OEFPAtomType::EqAromatic`
    -

  * - :oe:const:`OEGraphSim::OEFPAtomType::EqHalogen`
    -

  * - :oe:const:`OEGraphSim::OEFPAtomType::EqHBondAcceptor`
    -

  * - :oe:const:`OEGraphSim::OEFPAtomType::EqHBondDonor`
    -

.. _table_user_defined_bond_typing:

.. list-table:: Bond typing options
  :widths: 100 100
  :header-rows: 1

  * - bond typing constant
    - encoded bond property

  * - :oe:const:`OEGraphSim::OEFPBondType::BondOrder`
    - :oe:cls:`OEChem::OEBondBase::GetOrder`

  * - :oe:const:`OEGraphSim::OEFPBondType::Chiral`
    - :oe:meth:`OEChem::OEBondBase::IsChiral`

  * - :oe:const:`OEGraphSim::OEFPBondType::InRing`
    - :oe:meth:`OEChem::OEBondBase::IsInRing`

.. seealso::

   * :oe:constns:`OEGraphSim::OEFPAtomType` namespace
   * :oe:constns:`OEGraphSim::OEFPBondType` namespace

.. _section_user_defined_length:

Fragment Size
================================================================================

Circular, path and tree-based fingerprint generation involves molecular
graph traversal to identify all unique radial, linear or branched fragments,
respectively.
When a path or tree fingerprint is initialized, the minimum and maximum
number of bonds of the fragments that are encoded into the fingerprint
can be specified.
See :ref:`Figure: Example of enumerated path fragments with increasing number of bonds<figure_path_enumeration_length>` and
:ref:`Figure: Example of enumerated tree fragments with increasing number of bonds<figure_tree_enumeration_length>`.

.. _figure_path_enumeration_length:

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

   **Example of enumerated path fragments with increasing number of bonds**

.. _figure_tree_enumeration_length:

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

   **Example of enumerated tree fragments with increasing number of bonds**

In case of a circular fingerprint, the minimum and maximum radius of the
enumerated fragments can be specified.
See :ref:`Figure: Example of enumerated circular fragments with increasing radius<figure_circular_enumeration_length>`

.. _figure_circular_enumeration_length:

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

   **Example of enumerated circular fragments with increasing radius**


For example, when generating a fingerprint of the molecule shown in
:ref:`Figure: Example Molecule<figure_path_path_length_example>`
with minimum and maximum length set to ``0`` and ``3``, respectively,
only paths listed in the first four rows in :ref:`Table: Enumerated
Paths<table_path_enumeration>`, are encoded into the fingerprint.

.. _figure_path_path_length_example:

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

   **Example molecule**

.. _table_path_enumeration:

.. list-table:: Enumerated paths
   :widths: 15 35
   :header-rows: 1

   * - Path length (in bonds)
     - Generated Unique Paths
   * - 0
     - ``C``, ``N``, ``O``
   * - 1
     -  ``C-C``, ``C-N``, ``C-O``
   * - 2
     - ``C-C-C``, ``C-C-N``, ``C-C-O``, ``C-N-C``, ``N-C-O``
   * - 3
     -  ``C-C-C-C``, ``C-C-C-N``, ``C-C-C-O``, ``C-C-N-C``, ``C-N-C-O``,
   * - 4
     - ``C-C-C-C-C``, ``C-C-C-C-N``, ``C-C-C-C-O``, ``C-C-C-N-C``, ``C-C-N-C-C``, ``O-C-N-C-C``
   * - 5
     -  ``C-C-C-C-C-N``, ``C-C-C-C-C-O``, ``C-C-C-C-N-C``, ``C-C-C-N-C-C``, ``C-C-C-N-C-O``

:ref:`Figure: Example of enumerated paths<figure_path_path_length_enumeration>`
depicts the six unique paths of length four that are generated for the example
molecule. Each unique path is encoded only once without considering its frequency.

.. _figure_path_path_length_enumeration:

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

   **Example of enumerated paths**

In the example shown in :oe:src:`Listing 16<SNIPPET-FPPATHLENGTH-FPPathLength>`, fingerprints
with various minimum and maximum path length are generated for pyrrole
and pyridine.
When enumerating only paths that are shorter than four bonds,
the fingerprints generated for the two molecules are identical.
Since the four bond-length pattern ``ccccc`` is present in pyridine
but not in pyrrole, the fingerprints become different, resulting in
a smaller Tanimoto similarity score.

.. oe:source:: FPPathLength.cpp
   :language: c++
   :refnum:   16
   :caption:  Similarity calculation with various path lengths
   :frag:     SNIPPET-FPPATHLENGTH

.. oe:source:: FPPathLength.py
   :language: python
   :refnum:   16
   :caption:  Similarity calculation with various path lengths
   :frag:     SNIPPET-FPPATHLENGTH

.. oe:language:: python

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

.. oe:source:: FPPathLength.java
   :language: java
   :refnum:   16
   :caption:  Similarity calculation with various path lengths
   :frag:     SNIPPET-FPPATHLENGTH

.. oe:source:: FPPathLength.cs
   :language: csharp
   :refnum:   16
   :caption:  Similarity calculation with various path lengths
   :frag:     SNIPPET-FPPATHLENGTH

The output of :oe:src:`Listing 16<SNIPPET-FPPATHLENGTH-FPPathLength>` is the following:

::

   Tanimoto(A,B) = 1.000
   Tanimoto(A,B) = 1.000
   Tanimoto(A,B) = 0.950
   Tanimoto(A,B) = 0.731

.. _section_user_defined_bitsize:

Fingerprint Size
================================================================================

The previous sections explain how the atom and bond typing and encoded fragment
size can effect the similarity scores.
Selecting an adequate fingerprint size is also very crucial.
The number of unique circular, path or tree fragments present in molecular
structures can be extremely large, therefore the generated fragments have to
be hashed into the fixed-length fingerprint.
This means that a bit in a fingerprint does not correspond to
a unique pattern exclusively (as it does in :term:`structural key`).
Also a bit has no particular structural meaning, *i.e.*, each bit
represents the presence of a number of structural patterns.

The smaller the size of the fingerprints, the more dense they become,
raising the probability of collisions.
A collision occurs when different fragments are mapped to the same bit.
This will inherently result in information loss and weaken
the power to discriminate between structurally similar and dissimilar
molecules.
On the other hand, when the size of the fingerprints is too large
they become very sparse, which will reduce information loss.
However, the time spent to calculate similarity scores will increase.

The following table shows the number of unique paths generated for
benzylpenicillin
(depicted in :ref:`Figure: Benzylpenicillin<figure_path_benzylpenicillin>`).

.. note::

   The more atom and bond properties that are taken into account and the
   larger the size of paths to enumerate, the larger the size of the
   fingerprint has to be in order to encode the enumerated fragments
   without a significant number of bit collisions.

.. _figure_path_benzylpenicillin:

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

   **Benzylpenicillin**

.. list-table:: Number of unique paths generated for Benzylpenicillin
   :widths: 90 15 15 15
   :header-rows: 1

   * - Atom/Bond typing
     - path 0-3
     - path 0-5
     - path 0-7
   * - :oe:const:`AtomicNumber<OEGraphSim::OEFPAtomType::AtomicNumber>`, :oe:const:`BondOrder<OEGraphSim::OEFPBondType::BondOrder>`
     -  56
     - 149
     - 297
   * - :oe:const:`AtomicNumber<OEGraphSim::OEFPAtomType::AtomicNumber>` | :oe:const:`HvyDegree<OEGraphSim::OEFPAtomType::HvyDegree>`, :oe:const:`BondOrder<OEGraphSim::OEFPBondType::BondOrder>`
     - 111
     - 265
     - 453
   * - :oe:const:`AtomicNumber<OEGraphSim::OEFPAtomType::AtomicNumber>` | :oe:const:`HvyDegree<OEGraphSim::OEFPAtomType::HvyDegree>` | :oe:const:`Aromaticity<OEGraphSim::OEFPAtomType::Aromaticity>`, :oe:const:`BondOrder<OEGraphSim::OEFPBondType::BondOrder>` | :oe:const:`InRing<OEGraphSim::OEFPBondType::InRing>`
     - 126
     - 297
     - 499
   * - :oe:const:`DefaultAtom<OEGraphSim::OEFPAtomType::DefaultAtom>`, :oe:const:`DefaultBond<OEGraphSim::OEFPBondType::DefaultBond>`
     - 147
     - 362
     - 617

