.. _chapter_measure:

********************************************************************************
Similarity Measures
********************************************************************************

The basic idea underlying similarity-based measures is that molecules
that are structurally similar are likely to have similar properties.
In a fingerprint the presence or absence of a structural fragment is
represented by the presence or absence of a set bit.
This means that two molecules are judged as being similar if they have
a large number of bits in common.

Measuring molecular similarity or dissimilarity has two basic components:
the representation of molecular characteristics (such as fingerprints)
and the similarity coefficient that is used to quantify the degree of
resemblance between two such representations.


Built-in Similarity Measures
================================================================================

Since different similarity coefficients quantify different types of
structural resemblance, several built-in similarity measures are available
in the **GraphSim TK**
(see :ref:`Table: Basic bit count terms of similarity calculation<table_measure_basic_terms>`)
The table below defines the four basic bit count terms that are used in
fingerprint-based similarity calculations:

.. _table_measure_basic_terms:

.. list-table:: **Basic bit count terms of similarity calculation**
   :widths: 40 160 160
   :header-rows: 1

   * - Symbol
     - Description
     -

   * - :math:`onlyA`
     - number of bits set "on" in fingerprint A but not in B
     - .. image:: images/Fingerprints-OnlyA.*

   * - :math:`onlyB`
     - number of bits set "on" in fingerprint B but not in A
     - .. image:: images/Fingerprints-OnlyB.*

   * - :math:`bothAB`
     - number of bits set "on" in both fingerprints
     - .. image:: images/Fingerprints-BothAB.*

   * - :math:`neitherAB`
     - number of bits set "off" in both fingerprints
     - .. image:: images/Fingerprints-NeitherAB.*

   * - :math:`|A|`
     - number of bits set "on" in fingerprint A
     -

   * - :math:`|B|`
     - number of bits set "on" in fingerprint B
     -

   * - :math:`fpsize`
     - length of fingerprint in bits
     -

.. _section_measure_cosine:

Cosine
--------------------------------------------------------------------------------
.. index::
   pair: Cosine; similarity measure

**Formula:**

  :math:`Sim_{Cosine}(A,B) = \frac{bothAB}{\sqrt{|A|*|B|}} = \frac{bothAB}{\sqrt{(onlyA + bothAB) * (onlyB + bothAB)}}`

**Range:**

 :math:`[0.0, 1.0]`

**Example:**

================================== =======================================================================================================================
.. image:: images/Fingerprints.*   :math:`\frac{bothAB}{\sqrt{(onlyA+bothAB)*(onlyB+bothAB)}} = \frac{3}{\sqrt{(1+3)*(2+3)}} = \frac{3}{\sqrt{20}} = 0.67`
================================== =======================================================================================================================

Calculates the ratio of the bits in common to the geometric mean of
the number of "on" bits in the two fingerprints.

.. _section_measure_dice:

Dice
--------------------------------------------------------------------------------

.. index::
   pair: Dice; similarity measure

**Formula:**

  :math:`Sim_{Dice}(A,B) = \frac{2*bothAB}{|A|+|B|} = \frac{2 *bothAB}{onlyA + onlyB + 2 * bothAB}`

**Range:**

 :math:`[0.0, 1.0]`

**Example:**

================================== ======================================================================================
.. image:: images/Fingerprints.*   :math:`\frac{2*bothAB}{onlyA+onlyB+2*bothAB}=\frac{2*3}{1+2+2*3}=\frac{6}{9} = 0.666`
================================== ======================================================================================

Calculates the ratio of the bits in common to the arithmetic mean of
the number of "on" bits in the two fingerprints.

.. _section_measure_euclid:

Euclidean
--------------------------------------------------------------------------------

.. index::
   pair: Euclidean; similarity measure

**Formula:**

  :math:`Sim_{Euclid}(A,B) = \sqrt{\frac{bothAB + neitherAB}{fpsize}} = \sqrt{\frac{bothAB + neitherAB}{onlyA + onlyB + bothAB + neitherAB}}`

**Range:**

  :math:`[0.0, 1.0]`

**Example:**

================================== ===========================================================================================================================
.. image:: images/Fingerprints.*   :math:`\sqrt{\frac{bothAB+neitherAB}{onlyA+onlyB+bothAB+neitherAB}}=\sqrt{\frac{3+2}{1+2+3+2}} = \sqrt{\frac{5}{8}}=0.791`
================================== ===========================================================================================================================

.. _section_measure_manhattan:

Manhattan
--------------------------------------------------------------------------------

.. index::
   pair: Manhattan; similarity measure


**Formula:**

  :math:`Sim_{Manhattan}(A,B) = \frac{onlyA +onlyB}{fpsize} = \frac{onlyA + onlyB}{onlyA + onlyB + bothAB + neitherAB}`

**Range:**

  :math:`[0.0, 1.0]`

**Example:**

================================== ====================================================================================================================
.. image:: images/Fingerprints.*   :math:`\frac{onlyA + onlyB}{onlyA + onlyB + bothAB + neitherAB} = \frac{1 + 2}{1 + 2 + 3 + 2} = \frac{3}{8} = 0.375`
================================== ====================================================================================================================

.. note::

  Although :math:`Sim_{Manhattan}` shares the same range with other
  similarity measures, it acts more like a **distance** measure,
  scoring more similar fingerprints lower. Identical fingerprints have
  :math:`Sim_{Manhattan}` of 0.0 (as opposed to 1.0 in any other measure).

.. _section_measure_tanimoto:

Tanimoto
--------------------------------------------------------------------------------

.. index::
   pair: Tanimoto; similarity measure

**Formula:**

  :math:`Sim_{Tanimoto}(A,B) = \frac{bothAB}{|A| + |B| - bothAB} = \frac{bothAB}{onlyA + onlyB + bothAB}`

**Range:**

  :math:`[0.0, 1.0]`

**Example:**

================================== ===========================================================================
.. image:: images/Fingerprints.*   :math:`\frac{bothAB}{onlyA+onlyB+bothAB}=\frac{3}{1+2+3}=\frac{3}{6} = 0.5`
================================== ===========================================================================

.. note::

   The calculation of the :oe:const:`OEGraphSim::OEFPType::Lingo`
   fingerprint is based on fragmenting canonical isomeric
   :term:`SMILES` into overlapping four character long substrings.
   If any of the two :term:`SMILES` being compared is shorter than four characters,
   then their Tanimoto score will be:

   * `1.0`, if the two :term:`SMILES` are identical
   * `0.0`, otherwise.

.. _section_measure_tversky:

Tversky
--------------------------------------------------------------------------------

.. index::
   pair: Tversky; similarity measure

**Formula:**

  :math:`Sim_{Tversky}(A,B) = \frac{bothAB}{\alpha * onlyA + \beta * onlyB + bothAB}`

The Tversky similarity measure is asymmetric.
Setting the parameters :math:`\alpha = \beta = 1.0` is identical to
using the :ref:`section_measure_tanimoto` measure.

The factor :math:`\alpha` weights the contribution of the first
'reference' molecule. The larger :math:`\alpha` becomes, the more
weight is put on the bit setting of the reference molecule.

**Range:**

  :math:`[0.0, 1.0]`

**Example:**

================================== =========================================================================================================================
.. image:: images/Fingerprints.*   :math:`\frac{bothAB}{\alpha*onlyA+\beta*onlyB+bothAB} (\alpha=2.0,\beta=1.0)=\frac{3}{2.0*1+1.0*2+3}=\frac{3}{7} = 0.429`
================================== =========================================================================================================================

.. note::
  Although :math:`Sim_{Tversky}` shares the same range with other
  similarity measures, its scaling can vary by orders of magnitude
  depending on the choice of :math:`\alpha` and :math:`\beta` parameters.


Similarity Calculation
================================================================================

The following example demonstrates how to calculate
:oe:const:`Tanimoto<OEGraphSim::OESimMeasure::Tanimoto>` similarity
scores for the molecules depicted in
:ref:`Figure: Example molecules<figure_measure_fptanimoto>`.

.. _figure_measure_fptanimoto:

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

   **Example molecules**


.. oe:source:: FPTanimoto.cpp
   :language: c++
   :refnum:   8
   :caption:  Calculating Tanimoto index
   :frag:     SNIPPET-FP-TANIMOTO

..  oe:source:: FPTanimoto.py
    :language: python
    :refnum:   8
    :caption:  Calculating Tanimoto index
    :frag:     SNIPPET-FP-TANIMOTO

..    oe:language:: python

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

.. oe:source:: FPTanimoto.java
   :language: java
   :refnum:   8
   :caption:  Calculating Tanimoto index
   :frag:     SNIPPET-FP-TANIMOTO

..  oe:source:: FPTanimoto.cs
   :language: csharp
   :refnum:   8
   :caption:  Calculating Tanimoto index
   :frag:     SNIPPET-FP-TANIMOTO

Molecules B and C (shown in :ref:`Figure: Example Molecules<figure_measure_fptanimoto>`)
have the largest Tanimoto value since they share the largest number of
common structural features.

For these example molecule the output of :oe:src:`Listing 8<SNIPPET-FP-TANIMOTO-FPTanimoto>` is the following:

::

   Tanimoto(A,B) = 0.618
   Tanimoto(A,C) = 0.709
   Tanimoto(B,C) = 0.889


.. _section_measure_user_defined:

User-defined Similarity Measures
================================================================================

The following code snippet demonstrates how implement the Yule
similarity measure with the following formula:

:math:`Sim_{Yule}(A,B) = \sqrt{\frac{(bothAB * neitherAB) - (onlyA * onlyB)}{(bothAB * neitherAB) + (onlyA * onlyB)}}`

.. oe:source:: FPYule.cpp
   :language: c++
   :noindent:
   :frag:     SNIPPET-FP-YULE-1

.. oe:source:: FPYule.py
   :language: python
   :noindent:
   :frag:     SNIPPET-FP-YULE-1

..    oe:language:: python

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


.. oe:source:: FPYule.java
   :language: java
   :frag:     SNIPPET-FP-YULE-1

.. oe:source:: FPYule.cs
   :language: csharp
   :frag:     SNIPPET-FP-YULE-1

The :oe:func:`OEGraphSim::OEGetBitCounts` function returns the four basic
values (namely :math:`onlyA`, :math:`onlyB`, :math:`bothAB` and
:math:`neitherAB`) from which any similarity measures can be calculated.
For the definition of these values see
:ref:`Table: Basic bit count terms<table_measure_basic_terms>`


.. oe:source:: FPYule.cpp
   :language: c++
   :noindent:
   :frag:     SNIPPET-FP-YULE-2

.. oe:source:: FPYule.py
   :language: python
   :noindent:
   :frag:     SNIPPET-FP-YULE-2

..    oe:language:: python

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

.. oe:source:: FPYule.java
   :language: java
   :noindent:
   :frag:     SNIPPET-FP-YULE-2

.. oe:source:: FPYule.cs
   :language: csharp
   :noindent:
   :frag:     SNIPPET-FP-YULE-2

.. warning::

   User-defined similarity measures can only be used with circular,
   path, tree, and  MACCS key fingerprints but **not** with LINGO
   (:oe:const:`OEGraphSim::OEFPType::Lingo`).
