Package org.openscience.cdk.isomorphism
Class DfPattern
java.lang.Object
org.openscience.cdk.isomorphism.Pattern
org.openscience.cdk.isomorphism.DfPattern
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:
In practice VF2 take O(N2) to match a linear chain against it's self whilst this algorithm is O(N).
Usage:
DfPattern 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)) {
}
}
References
- [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
Modifier and TypeMethodDescriptionstatic 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
.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 Details
-
match
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
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
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
Test whether the pattern matches at the provided atom.- Parameters:
root
- the root atom of the molecule- Returns:
- the pattern matches
-
findSubstructure
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:
-