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: 

 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
Author:
John Mayfield
See Also:

  • Method Details

    • 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:

    • 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: