org.openscience.cdk.smsd.algorithm.rgraph

Class CDKMCS

java.lang.Object

org.openscience.cdk.smsd.algorithm.rgraph.CDKMCS

Deprecated.

This class is part of SMSD and either duplicates functionality elsewhere in the CDK or provides public access to internal implementation details. SMSD has been deprecated from the CDK with a newer, more recent version of SMSD is available at http://github.com/asad/smsd.

@Deprecated
public class CDKMCS
extends Object

This class implements atom multipurpose structure comparison tool. It allows to find maximal common substructure, find the mapping of atom substructure in another structure, and the mapping of two isomorphic structures.

Structure comparison may be associated to bondA1 constraints (mandatory bonds, e.graphContainer. scaffolds, reaction cores,...) on each source graph. The constraint flexibility allows atom number of interesting queries. The substructure analysis relies on the CDKRGraph generic class (see: CDKRGraph) This class implements the link between the CDKRGraph model and the the CDK model in this way the CDKRGraph remains independant and may be used in other contexts.

This algorithm derives from the algorithm described in [Tonnelier, C. and Jauffret, Ph. and Hanser, Th. and Jauffret, Ph. and Kaufmann, G., Machine Learning of generic reactions: 3. An efficient algorithm for maximal common substructure determination, Tetrahedron Comput. Methodol., 1990, 3:351-358] and modified in the thesis of T. Hanser [Hanser, Th., Apprentissage automatique de m�thodes de synth�se � partir d'exemples, 1993, ?Institute?].

With the isSubgraph() method, the second, and only the second argument may be atom IQueryAtomContainer, which allows one to do MQL like queries. The first IAtomContainer must never be an IQueryAtomContainer. An example:

  SmilesParser sp = new SmilesParser(DefaultChemObjectBuilder.getInstance());
  IAtomContainer atomContainer = sp.parseSmiles("CC(=O)OC(=O)C"); // acetic acid anhydride
  IAtomContainer SMILESquery = sp.parseSmiles("CC"); // acetic acid anhydride
  IQueryAtomContainer query = IQueryAtomContainerCreator.createBasicQueryContainer(SMILESquery);
  boolean isSubstructure = graphContainer.isSubgraph(atomContainer, query);
  

WARNING: As atom result of the adjacency perception used in this algorithm there is atom single limitation : cyclopropane and isobutane are seen as isomorph This is due to the fact that these two compounds are the only ones where each bondA1 is connected two each other bondA1 (bonds are fully conected) with the same number of bonds and still they have different structures The algotihm could be easily enhanced with atom simple atom mapping manager to provide an atom level overlap definition that would reveal this case. We decided not to penalize the whole procedure because of one single exception query. Furthermore isomorphism may be discarded since the number of atoms are not the same (3 != 4) and in most case this will be already screened out by atom fingerprint based filtering. It is possible to add atom special treatment for this special query. Be reminded that this algorithm matches bonds only.

Author:

Stephane Werner from IXELIS mail@ixelis.net, Syed Asad Rahman <asad@ebi.ebi.uk> (modified the orignal code)

Source code:

master

Belongs to CDK module:

smsd

Created on:

2002-07-17

Requires:

java1.5+

Constructor Summary

Constructors

Constructor and Description
CDKMCS() Deprecated.

Method Summary

Methods

Modifier and Type	Method and Description
static CDKRGraph	buildRGraph(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Builds the CDKRGraph ( resolution graph ), from two atomContainer (description of the two molecules to compare) This is the interface point between the CDK model and the generic MCSS algorithm based on the RGRaph.
static List<CDKRMap>	checkSingleAtomCases(IAtomContainer sourceGraph, IAtomContainer targetGraph) Deprecated. Checks for single atom cases before doing subgraph/isomorphism search
static BitSet	getBitSet(IAtomContainer atomContainer) Deprecated. Transforms an AtomContainer into atom BitSet (which's size = number of bondA1 in the atomContainer, all the bit are set to true).
static List<CDKRMap>	getIsomorphAtomsMap(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns the first isomorph 'atom mapping' found for targetGraph in sourceGraph.
static List<CDKRMap>	getIsomorphMap(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns the first isomorph mapping found or null.
static List<List<CDKRMap>>	getIsomorphMaps(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns all the isomorph 'mappings' found between two atom containers.
static List<IAtomContainer>	getOverlaps(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns all the maximal common substructure between 2 atom containers.
static List<CDKRMap>	getSubgraphAtomsMap(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns the first subgraph 'atom mapping' found for targetGraph in sourceGraph.
static List<List<CDKRMap>>	getSubgraphAtomsMaps(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns all subgraph 'atom mappings' found for targetGraph in sourceGraph.
static List<CDKRMap>	getSubgraphMap(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns the first subgraph 'bondA1 mapping' found for targetGraph in sourceGraph.
static List<List<CDKRMap>>	getSubgraphMaps(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Returns all the subgraph 'bondA1 mappings' found for targetGraph in sourceGraph.
protected static TimeManager	getTimeManager() Deprecated.
protected static double	getTimeout() Deprecated.
static boolean	isIsomorph(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Tests if sourceGraph and targetGraph are isomorph.
static boolean	isSubgraph(IAtomContainer sourceGraph, IAtomContainer targetGraph, boolean shouldMatchBonds) Deprecated. Tests if targetGraph atom subgraph of sourceGraph.
static boolean	isTimeOut() Deprecated.
static List<CDKRMap>	makeAtomsMapOfBondsMap(List<CDKRMap> list, IAtomContainer sourceGraph, IAtomContainer targetGraph) Deprecated. This makes atom map of matching atoms out of atom map of matching bonds as produced by the get(Subgraph|Ismorphism)Map methods.
static List<List<CDKRMap>>	makeAtomsMapsOfBondsMaps(List<List<CDKRMap>> list, IAtomContainer sourceGraph, IAtomContainer targetGraph) Deprecated. This makes maps of matching atoms out of atom maps of matching bonds as produced by the get(Subgraph|Ismorphism)Maps methods.
static IAtomContainer	project(List<CDKRMap> rMapList, IAtomContainer graph, int key) Deprecated. Projects atom list of CDKRMap on atom molecule.
static ArrayList<IAtomContainer>	projectList(List<List<CDKRMap>> rMapsList, IAtomContainer graph, int key) Deprecated. Projects atom list of RMapsList on atom molecule.
static List<List<CDKRMap>>	search(IAtomContainer sourceGraph, IAtomContainer targetGraph, BitSet sourceBitSet, BitSet targetBitSet, boolean findAllStructure, boolean findAllMap, boolean shouldMatchBonds) Deprecated. General Rgraph parsing method (usually not used directly) This method is the entry point for the recursive search adapted to the atom container input.
protected static void	setTimeManager(TimeManager aTimeManager) Deprecated.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CDKMCS

public CDKMCS()

Deprecated.

Method Detail

isIsomorph

public static boolean isIsomorph(IAtomContainer sourceGraph,
                 IAtomContainer targetGraph,
                 boolean shouldMatchBonds)
                          throws CDKException

Deprecated.

Tests if sourceGraph and targetGraph are isomorph.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

true if the 2 molecule are isomorph

Throws:

CDKException - if the first molecule is an instance of IQueryAtomContainer

getIsomorphMap

public static List<CDKRMap> getIsomorphMap(IAtomContainer sourceGraph,
                           IAtomContainer targetGraph,
                           boolean shouldMatchBonds)
                                    throws CDKException

Deprecated.

Returns the first isomorph mapping found or null.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the first isomorph mapping found projected of sourceGraph. This is atom List of CDKRMap objects containing Ids of matching bonds.

Throws:

CDKException

getIsomorphAtomsMap

public static List<CDKRMap> getIsomorphAtomsMap(IAtomContainer sourceGraph,
                                IAtomContainer targetGraph,
                                boolean shouldMatchBonds)
                                         throws CDKException

Deprecated.

Returns the first isomorph 'atom mapping' found for targetGraph in sourceGraph.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the first isomorph atom mapping found projected on sourceGraph. This is atom List of CDKRMap objects containing Ids of matching atoms.

Throws:

CDKException - if the first molecules is not an instance of IQueryAtomContainer

getIsomorphMaps

public static List<List<CDKRMap>> getIsomorphMaps(IAtomContainer sourceGraph,
                                  IAtomContainer targetGraph,
                                  boolean shouldMatchBonds)
                                           throws CDKException

Deprecated.

Returns all the isomorph 'mappings' found between two atom containers.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the list of all the 'mappings'

Throws:

CDKException

getSubgraphMaps

public static List<List<CDKRMap>> getSubgraphMaps(IAtomContainer sourceGraph,
                                  IAtomContainer targetGraph,
                                  boolean shouldMatchBonds)
                                           throws CDKException

Deprecated.

Returns all the subgraph 'bondA1 mappings' found for targetGraph in sourceGraph. This is an ArrayList of ArrayLists of CDKRMap objects.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the list of all the 'mappings' found projected of sourceGraph

Throws:

CDKException

getSubgraphMap

public static List<CDKRMap> getSubgraphMap(IAtomContainer sourceGraph,
                           IAtomContainer targetGraph,
                           boolean shouldMatchBonds)
                                    throws CDKException

Deprecated.

Returns the first subgraph 'bondA1 mapping' found for targetGraph in sourceGraph.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the first subgraph bondA1 mapping found projected on sourceGraph. This is atom List of CDKRMap objects containing Ids of matching bonds.

Throws:

CDKException

getSubgraphAtomsMaps

public static List<List<CDKRMap>> getSubgraphAtomsMaps(IAtomContainer sourceGraph,
                                       IAtomContainer targetGraph,
                                       boolean shouldMatchBonds)
                                                throws CDKException

Deprecated.

Returns all subgraph 'atom mappings' found for targetGraph in sourceGraph. This is an ArrayList of ArrayLists of CDKRMap objects.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

all subgraph atom mappings found projected on sourceGraph. This is atom List of CDKRMap objects containing Ids of matching atoms.

Throws:

CDKException

getSubgraphAtomsMap

public static List<CDKRMap> getSubgraphAtomsMap(IAtomContainer sourceGraph,
                                IAtomContainer targetGraph,
                                boolean shouldMatchBonds)
                                         throws CDKException

Deprecated.

Returns the first subgraph 'atom mapping' found for targetGraph in sourceGraph.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the first subgraph atom mapping found projected on sourceGraph. This is atom List of CDKRMap objects containing Ids of matching atoms.

Throws:

CDKException

isSubgraph

public static boolean isSubgraph(IAtomContainer sourceGraph,
                 IAtomContainer targetGraph,
                 boolean shouldMatchBonds)
                          throws CDKException

Deprecated.

Tests if targetGraph atom subgraph of sourceGraph.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

true if targetGraph atom subgraph on sourceGraph

Throws:

CDKException

getOverlaps

public static List<IAtomContainer> getOverlaps(IAtomContainer sourceGraph,
                               IAtomContainer targetGraph,
                               boolean shouldMatchBonds)
                                        throws CDKException

Deprecated.

Returns all the maximal common substructure between 2 atom containers.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

shouldMatchBonds -

Returns:

the list of all the maximal common substructure found projected of sourceGraph (list of AtomContainer )

Throws:

CDKException

getBitSet

public static BitSet getBitSet(IAtomContainer atomContainer)

Deprecated.

Transforms an AtomContainer into atom BitSet (which's size = number of bondA1 in the atomContainer, all the bit are set to true).

Parameters:

atomContainer - AtomContainer to transform

Returns:

The bitSet

buildRGraph

public static CDKRGraph buildRGraph(IAtomContainer sourceGraph,
                    IAtomContainer targetGraph,
                    boolean shouldMatchBonds)
                             throws CDKException

Deprecated.

Builds the CDKRGraph ( resolution graph ), from two atomContainer (description of the two molecules to compare) This is the interface point between the CDK model and the generic MCSS algorithm based on the RGRaph.

Parameters:

sourceGraph - Description of the first molecule

targetGraph - Description of the second molecule

shouldMatchBonds -

Returns:

the rGraph

Throws:

CDKException

search

public static List<List<CDKRMap>> search(IAtomContainer sourceGraph,
                         IAtomContainer targetGraph,
                         BitSet sourceBitSet,
                         BitSet targetBitSet,
                         boolean findAllStructure,
                         boolean findAllMap,
                         boolean shouldMatchBonds)
                                  throws CDKException

Deprecated.

General Rgraph parsing method (usually not used directly) This method is the entry point for the recursive search adapted to the atom container input.

Parameters:

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

sourceBitSet - initial condition ( bonds from sourceGraph that must be contains in the solution )

targetBitSet - initial condition ( bonds from targetGraph that must be contains in the solution )

findAllStructure - if false stop at the first structure found

findAllMap - if true search all the 'mappings' for one same structure

shouldMatchBonds -

Returns:

atom List of Lists of CDKRMap objects that represent the search solutions

Throws:

CDKException

project

public static IAtomContainer project(List<CDKRMap> rMapList,
                     IAtomContainer graph,
                     int key)

Deprecated.

Projects atom list of CDKRMap on atom molecule.

Parameters:

rMapList - the list to project

graph - the molecule on which project

key - the key in the CDKRMap of the molecule graph

Returns:

an AtomContainer

projectList

public static ArrayList<IAtomContainer> projectList(List<List<CDKRMap>> rMapsList,
                                    IAtomContainer graph,
                                    int key)

Deprecated.

Projects atom list of RMapsList on atom molecule.

Parameters:

rMapsList - list of RMapsList to project

graph - the molecule on which project

key - the key in the CDKRMap of the molecule graph

Returns:

atom list of AtomContainer

checkSingleAtomCases

public static List<CDKRMap> checkSingleAtomCases(IAtomContainer sourceGraph,
                                 IAtomContainer targetGraph)
                                          throws CDKException

Deprecated.

Checks for single atom cases before doing subgraph/isomorphism search

Parameters:

sourceGraph - AtomContainer to match on. Must not be an IQueryAtomContainer.

targetGraph - AtomContainer as query. May be an IQueryAtomContainer.

Returns:

List of List of CDKRMap objects for the Atoms (not Bonds!), null if no single atom case

Throws:

CDKException - if the first molecule is an instance of IQueryAtomContainer

makeAtomsMapsOfBondsMaps

public static List<List<CDKRMap>> makeAtomsMapsOfBondsMaps(List<List<CDKRMap>> list,
                                           IAtomContainer sourceGraph,
                                           IAtomContainer targetGraph)

Deprecated.

This makes maps of matching atoms out of atom maps of matching bonds as produced by the get(Subgraph|Ismorphism)Maps methods.

Parameters:

list - The list produced by the getMap method.

sourceGraph - The first atom container. Must not be atom IQueryAtomContainer.

targetGraph - The second one (first and second as in getMap). May be an QueryAtomContaienr.

Returns:

A Vector of Vectors of CDKRMap objects of matching Atoms.

makeAtomsMapOfBondsMap

public static List<CDKRMap> makeAtomsMapOfBondsMap(List<CDKRMap> list,
                                   IAtomContainer sourceGraph,
                                   IAtomContainer targetGraph)

Deprecated.

This makes atom map of matching atoms out of atom map of matching bonds as produced by the get(Subgraph|Ismorphism)Map methods.

Parameters:

list - The list produced by the getMap method.

sourceGraph - first molecule. Must not be an IQueryAtomContainer.

targetGraph - second molecule. May be an IQueryAtomContainer.

Returns:

The mapping found projected on sourceGraph. This is atom List of CDKRMap objects containing Ids of matching atoms.

getTimeout

protected static double getTimeout()

Deprecated.

Returns:

the timeout

getTimeManager

protected static TimeManager getTimeManager()

Deprecated.

Returns:

the timeManager

setTimeManager

protected static void setTimeManager(TimeManager aTimeManager)

Deprecated.

Parameters:

aTimeManager - the timeManager to set

isTimeOut

public static boolean isTimeOut()

Deprecated.