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(N²) 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)

Author:

John Mayfield

See Also:

DfPattern, Mappings

Method Summary

Modifier and Type	Method and Description
static DfPattern	findSubstructure(IAtomContainer query) Create a pattern which can be used to find molecules which contain the query structure.
int[]	match(IAtomContainer target) Find a matching of this pattern in the target.
Mappings	matchAll(IAtomContainer mol) Find all mappings of this pattern in the target.
boolean	matches(IAtomContainer target) Determine if there is a mapping of this pattern in the target.
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

Methods inherited from class java.lang.Object

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

Method Detail

match

public int[] match(IAtomContainer target)

Find a matching of this pattern in the target. 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!
     }
 }
 

Specified by:

match in class Pattern

Parameters:

target - the container to search for the pattern in

Returns:

the mapping from the pattern to the target or an empty array

matches

public boolean matches(IAtomContainer target)

Determine if there is a mapping of this pattern in the target. Depending on the implementation stereochemistry may be checked (recommended).

 Pattern        pattern = ...; // create pattern
 for (IAtomContainer m : ms) {
     if (pattern.matches(m)) {
         // found mapping!
     }
 }
 

Overrides:

matches in class Pattern

Parameters:

target - the container to search for the pattern in

Returns:

the mapping from the pattern to the target

matchAll

public Mappings matchAll(IAtomContainer mol)

Find all mappings of this pattern in the target. Stereochemistry should not be checked to allow filtering with Mappings.stereochemistry().

 Pattern pattern = Pattern.findSubstructure(query);
 for (IAtomContainer m : ms) {
     for (int[] mapping : pattern.matchAll(m)) {
         // found mapping
     }
 }
 

Using the fluent interface (see 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();
 

Specified by:

matchAll in class Pattern

Parameters:

mol - the container to search for the pattern in

Returns:

the mapping from the pattern to the target

See Also:

Mappings

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 the query structure. If a 'real' molecule is provided is is converted with QueryAtomContainer.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...)