Package org.openscience.cdk.isomorphism
Class DfPattern
- java.lang.Object
-
- org.openscience.cdk.isomorphism.Pattern
-
- org.openscience.cdk.isomorphism.DfPattern
-
public class DfPattern extends Pattern
The depth-first (DF) backtracking sub-structure matching algorithm so named because it matches the molecule in a depth-first manner (bond by bond). The algorithm is a simple but elegant backtracking search iterating over the bonds of a query. Like the popular VF2 the algorithm, it uses linear memory but unlike VF2 bonded atoms are selected from the neighbor lists of already mapped atoms.
In practice VF2 take O(N2) to match a linear chain against it's self whilst this algorithm is O(N).
Usage:
ReferencesDfPattern ptrn = DfPattern.findSubstructure(query); // has match? if (ptrn.matches(mol)) { } // get lazy mapping iterator Mappings mappings = ptrn.matchAll(mol); for (int[] amap : mappings) { } // test if pattern matches at a given atom for (IAtom atom : mol.atoms()) { if (ptrn.matchesRoot(atom)) { } }
- [Louis C. Ray and Russell A. Kirsch. Science. 1957. 126]
- [Ullmann J R. Journal of the Association for Computing Machinery. 1976. 23]
- [Cordella Luigi P et. al.. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE. 2004. 26]
- [Nina Jeliazkova and Nikolay Kochev. Molecular Informatics. 2011. 30]
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static DfPattern
findSubstructure(IAtomContainer query)
Create a pattern which can be used to find molecules which contain thequery
structure.int[]
match(IAtomContainer target)
Find a matching of this pattern in thetarget
.Mappings
matchAll(IAtomContainer mol)
Find all mappings of this pattern in thetarget
.boolean
matches(IAtomContainer target)
Determine if there is a mapping of this pattern in thetarget
.boolean
matchesRoot(IAtom root)
Test whether the pattern matches at the provided atom.-
Methods inherited from class org.openscience.cdk.isomorphism.Pattern
findIdentical, matchAll, matches
-
-
-
-
Method Detail
-
match
public int[] match(IAtomContainer target)
Find a matching of this pattern in thetarget
. If no such order exist an empty mapping is returned. Depending on the implementation stereochemistry may be checked (recommended).Pattern pattern = ...; // create pattern for (IAtomContainer m : ms) { int[] mapping = pattern.match(m); if (mapping.length > 0) { // found mapping! } }
-
matches
public boolean matches(IAtomContainer target)
Determine if there is a mapping of this pattern in thetarget
. Depending on the implementation stereochemistry may be checked (recommended).Pattern pattern = ...; // create pattern for (IAtomContainer m : ms) { if (pattern.matches(m)) { // found mapping! } }
-
matchAll
public Mappings matchAll(IAtomContainer mol)
Find all mappings of this pattern in thetarget
. Stereochemistry should not be checked to allow filtering withMappings.stereochemistry()
.
Using the fluent interface (seePattern pattern = Pattern.findSubstructure(query); for (IAtomContainer m : ms) { for (int[] mapping : pattern.matchAll(m)) { // found mapping } }
Mappings
) we can search and manipulate the mappings. Here's an example of finding the first 5 mappings and creating an array. If the mapper is lazy other states are simply not explored.// find only the first 5 mappings and store them in an array Pattern pattern = Pattern.findSubstructure(query); int[][] mappings = pattern.matchAll(target) .limit(5) .toArray();
-
matchesRoot
public boolean matchesRoot(IAtom root)
Test whether the pattern matches at the provided atom.- Parameters:
root
- the root atom of the molecule- Returns:
- the pattern matches
-
findSubstructure
public static DfPattern findSubstructure(IAtomContainer query)
Create a pattern which can be used to find molecules which contain thequery
structure. If a 'real' molecule is provided is is converted withQueryAtomContainer.create(IAtomContainer, Expr.Type...)
matching elements, aromaticity status, and bond orders.- Parameters:
query
- the substructure to find- Returns:
- a pattern for finding the
query
- See Also:
QueryAtomContainer.create(IAtomContainer, Expr.Type...)
-
-