Package org.openscience.cdk.graph
Class TripletShortCycles
java.lang.Object
org.openscience.cdk.graph.TripletShortCycles
Compute the shortest cycles through each vertex triple. This allows one to
directly obtain the envelope rings of bicyclic fused system. These cycles
can be thought of as the 'ESSSR' (extended smallest set of smallest rings)
and 'envelope' rings as used by PubChem fingerprints (CACTVS Substructure
Keys). The PubChem fingerprint documentation exclusively refers to the ESSSR
and envelopes as just the ESSSR and the rest of this documentation does the
same. This class provides the cycles (vertex paths) for each ring in the
ESSSR.
The ESSSR should not be confused with the extended set of smallest rings
(ESSR) [Downs, G et. al.. J. Chem. Inf. Comput. Sci. 1989. 29].
Algorithm To our knowledge no algorithm has been published for
the ESSSR. The PubChem
Specifications states - "An ESSSR ring is any ring which does not
share three consecutive atoms with any other ring in the chemical structure.
For example, naphthalene has three ESSSR rings (two phenyl fragments and the
10-membered envelope), while biphenyl will yield a count of only two ESSSR
rings". The name implies the use of the smallest set of smallest rings
(SSSR). Not every graph has an SSSR and so the minimum cycle basis is used
instead. With this modification the algorithm is outlined below.
- Compute a minimum cycle basis (or SSSR) of the graph (may not be unique)
- For each vertex v and two adjacent vertices (u and w) check if the path -u-v-w- belongs to any cycles already in the basis
- If no such cycle can be found compute the shortest cycle which travels through -u-v-w- and add it to the basis. The shortest cycle is the shortest path from u to w which does not travel through v
RelevantCycles
which is the
the smallest set of short cycles which is uniquely defined for a
graph.
To better explain the issue with the canonical labelling several examples are
shown below. The table outlining the size of rings found for each molecule
when using canonical and non-canonical generation. Also shown are the sizes
of rings stored in the PubChem fingerprint associated with the entry. The
fingerprints were obtained directly from PubChem and decoded using the
specification. Sizes underlined and coloured red represent rings which may
or may not be present depending on the atom ordering. It can be seen from the
PubChem fingerprint that even using a consistent canonical labelling rings
may be absent which would be present if the subgraph was used.
PubChem CID | Diagram | Size of Rings in
ESSSR (fingerprints only store cycles |C| <= 10) | Source | ||||||
---|---|---|---|---|---|---|---|---|---|
CID 135973 |
|
|
|||||||
CID 9249 |
|
|
|||||||
CID 931 |
|
|
|||||||
CID 5702 |
|
|
|||||||
CID 1211 |
|
|
|||||||
CID 17858819 |
|
|
|||||||
CID 1909 |
|
|
- Author:
- John May
- See Also:
- Source code:
- main
- Belongs to CDK module:
- core
- Keywords:
- ESSSR, ring, cycle
-
Constructor Summary
ConstructorsConstructorDescriptionTripletShortCycles
(MinimumCycleBasis mcb, boolean canonical) Compute the cycles of the extended smallest set of smallest rings (ESSSR) for an existing minimum cycle basis. -
Method Summary
-
Constructor Details
-
TripletShortCycles
Compute the cycles of the extended smallest set of smallest rings (ESSSR) for an existing minimum cycle basis. Choosing the set to be canonical means the set depends on the order of the vertices and may not be consistent in subgraphs. Given a different order of vertices the same cycles may not be found.- Parameters:
mcb
- minimum cycle basiscanonical
- should the set be canonical (non-unique)
-
-
Method Details
-
paths
public int[][] paths()Access the vertex paths for all cycles of the basis.- Returns:
- paths of the basis
-
size
public int size()Size of the cycle basis, cardinality of the ESSSR.- Returns:
- number of cycles in the basis
-