fragment.java

A program to find frequent molecular substructures and discriminative fragments in a database of mol

/*----------------------------------------------------------------------
  File    : Fragment.java
  Contents: Management of molecular fragments
  Author  : Christian Borgelt
  History : 11.03.2002 file created as file submol.java
            14.03.2002 output method added (toString, for debugging)
            15.07.2002 function 'isEquivTo' added (later rewritten)
            01.08.2003 function 'isPerfect' added (later rewritten)
            06.08.2003 file split, this part renamed to Fragment.java
            07.08.2003 complete rewrite of most functions
            08.08.2003 function 'revert' added (perfect extensions)
            09.08.2003 position of new bonds changed, field "idx" added
            08.06.2005 perfect extension pruning restricted to bridges
            22.07.2005 adapted to changed embedding marking functions
            23.07.2005 function 'isClosed' debugged and optimized
            24.07.2005 function 'isCanonic' completed and debugged
            03.08.2005 special functions for seed embedding removed
            05.08.2005 chain size check for pruning simplified
            11.08.2005 ExtLE.merge modified, isCanonic -> Extension
            17.08.2005 initial fragment, embedding traversal modified
                       optional packed embedding lists added
            21.08.2005 reembedding adapted to packed embedding lists
            02.09.2005 creation of packed embedding lists modified
            07.04.2006 unnecessary code removed from function revert
            10.04.2006 fields atoms and bonds removed (unnecessary)
            11.04.2006 function adapt added (for perfect extensions)
            29.04.2006 function adapt debugged, Fragment.flgs added
            02.05.2006 adapted to changed function Extension.isCanonic
            03.05.2006 function makeCanonic added and debugged
            11.05.2006 function isCanonic replaced by new version
            14.05.2006 bug in isPerfect fixed (packed embeddings)
            16.05.2006 function mergeExts added and debugged
            17.05.2006 single extension section treatment in mergeExts
            18.05.2006 adapted to new field Extension.dst
            31.05.2006 function adapt extended, result added
            01.06.2006 function isCanonic extended, result changed
            04.06.2006 bugs in functions adapt and mergeExts fixed
            06.06.2006 ring extension handling in adapt modified
            07.06.2006 bug in function isPerfect fixed (single molecule)
            08.06.2006 ring adaption point corrected in function adapt
            19.06.2006 function isClosed adapted to ring extensions
            20.06.2006 changed reorg. point for max. source extensions
            21.06.2006 flag CHECKED added (for check for duplicates)
            22.06.2006 flag CLOSED added (for closed fragment check)
            23.06.2006 flag VALID added (for marking invalid fragments)
            30.06.2006 filtering of identical ring embeddings added
            01.07.2006 adaption of ring extensions moved to Extension
            05.08.2006 ring closing bonds allowed for perfect extensions
            12.08.2006 adapted to new Notation classes
----------------------------------------------------------------------*/
package moss;

/*----------------------------------------------------------------------
A fragment is a part of a molecule. It consists of a list of embeddings
that indicate where this fragment can be found in different molecules.
In addition, a fragment contains information about the extension bond
(and maybe atom) by which it was constructed from a smaller fragment.
----------------------------------------------------------------------*/

/*--------------------------------------------------------------------*/
class ExtLE {
/*--------------------------------------------------------------------*/

  /* Extension lists are used for checking whether a fragment is */
  /* closed, i.e., has no super-structure with the same support. */

  /* --- instance variables --- */
  protected int   src;          /* index of source      atom */
  protected int   dst;          /* index of destination atom */
  protected int   bond;         /* type  of extension   bond */
  protected int   atom;         /* type  of destination atom */
  protected int[] ring;         /* ring information (if needed) */
  protected ExtLE succ;         /* successor in list */

  /*------------------------------------------------------------------*/

  protected ExtLE (int src, int dst, int bond, int atom)
  {                             /* --- create extension list element */
    this.src  = src;  this.dst  = dst;
    this.bond = bond; this.atom = atom;
    this.ring = null;           /* store extension information */
  }  /* ExtLE() */    

  /*------------------------------------------------------------------*/

  protected ExtLE (int src, int dst, int bond, int atom,
                   int[] ring, int n)
  {                             /* --- create extension list element */
    this.src  = src;  this.dst  = dst;
    this.bond = bond; this.atom = atom;
    System.arraycopy(ring, 0, this.ring = new int[n], 0, n);
  }  /* ExtLE() */              /* store extension information */

  /*------------------------------------------------------------------*/

  protected int compareTo (ExtLE e)
  {                             /* --- compare extension list elements*/
    int i, k;                   /* loop variable, buffer */

    if (this.src  < e.src)  return -1;  /* compare the properties */
    if (this.src  > e.src)  return +1;  /* of the first/only bond */
    if (this.dst  < e.dst)  return -1;
    if (this.dst  > e.dst)  return +1;
    if (this.bond < e.bond) return -1;
    if (this.bond > e.bond) return +1;
    if (this.atom < e.atom) return -1;
    if (this.atom > e.atom) return +1;
    i = (this.ring == null) ? 0 : this.ring.length;
    k = (   e.ring == null) ? 0 :    e.ring.length;
    if (i < k) return -1;       /* compare the extension type */
    if (i > k) return +1;       /* (bond or ring) and the ring size */
    for (i = 0; i < k; i++) {   /* traverse the ring bonds */
      if (this.ring[i] < e.ring[i]) return -1;
      if (this.ring[i] > e.ring[i]) return +1;
    }                           /* compare the ring bond properties */
    return 0;                   /* if no diff. found, exts. are equal */
  }  /* compareTo() */

  /*------------------------------------------------------------------*/

  protected static ExtLE merge (ExtLE l1, ExtLE l2)
  {                             /* --- merge two extension lists */
    int   r;                    /* result of comparison */
    ExtLE out, tail = null, e;  /* output list, list element */

    if (l1 == null) return l2;  /* if one of the lists is empty, */
    if (l2 == null) return l1;  /* return the other */
    r = l1.compareTo(l2);       /* compare the first list elements */
    if (r == 0) { l2 = l2.succ; }
    if (r <= 0) { out = tail = l1; l1 = out.succ; }
    else        { out = tail = l2; l2 = out.succ; }
    while ((l1 != null) && (l2 != null)) {
      r = l1.compareTo(l2);     /* compare the first list elements */
      if (r == 0) { l2 = l2.succ; }
      if (r <= 0) { e = l1; l1 = e.succ; }
      else        { e = l2; l2 = e.succ; }
      tail.succ = e; tail = e;  /* move smaller element */
    }                           /* to the output list */
    if      (l1 != null) tail.succ = l1;
    else if (l2 != null) tail.succ = l2;
    else                 tail.succ = null;
    return out;                 /* append remaining elements */
  }  /* merge() */              /* and return the merged list */

  /*------------------------------------------------------------------*/

  protected static ExtLE sort (ExtLE list)
  {                             /* --- sort an extension list */
    ExtLE l1, l2, e;            /* sublists for mergesort */

    if ((list == null) || (list.succ == null))
      return list;              /* abort for zero and one element */
    l1 = l2 = null;             /* initialize the two output lists */
    while (true) {              /* traverse the input list */
      e = list; list = list.succ; e.succ = l1; l1 = e;
      if (list == null) break;  /* transfer element to first list */
      e = list; list = list.succ; e.succ = l2; l2 = e;
      if (list == null) break;  /* transfer element to second list */
    }                           /* (split into two equal lists) */
    return merge(sort(l1), sort(l2));
  }  /* sort() */               /* sort and then merge the two lists */

}  /* class ExtLE */


/*--------------------------------------------------------------------*/
public class Fragment {
/*--------------------------------------------------------------------*/

  /* --- constants: flags --- */
  protected static final int VALID   = 0x01;
  protected static final int CLOSED  = 0x02;
  protected static final int UNIQUE  = 0x04;
  protected static final int PERFECT = 0x08;
  protected static final int ADAPTED = 0x10;
  protected static final int DEFAULT = VALID | CLOSED;

  /* --- instance variables --- */
  protected Molecule  mol;      /* this fragment as a molecule */
  protected Fragment  base;     /* base fragment (which was extended) */
  protected Embedding list;     /* list of embeddings of the fragment */
  protected Embedding tail;     /* tail of the embedding list */
  protected Embedding curr;     /* current embedding (cursor) */
  protected int       max;      /* maximal number of embeddings */
  protected int       cnt;      /* current number of embeddings */
  protected int       chns;     /* number of carbon chains */
  protected int       idx;      /* index of new bond */
  protected int       src;      /* index of source atom of new bond */
  protected int       dst;      /* index of dest.  atom of new bond */
  protected int       size;     /* number of atoms in ring/chain */
  protected int       flgs;     /* property flags, e.g. PERFECT */
  protected int[]     supp;     /* support counters (<=/> threshold) */
  protected int[]     ris;      /* indices of atoms of new ring bonds */

  /*------------------------------------------------------------------*/

  protected Fragment ()             { this((Molecule)null, 0); }
  protected Fragment (Molecule mol) { this(mol,            0); }
  protected Fragment (int max)      { this((Molecule)null, max); }

  /*------------------------------------------------------------------*/

  protected Fragment (Molecule mol, int max)
  {                             /* --- create an initial fragment */
    this.mol  = mol;            /* store the molecule */
    this.base = null;           /* there is no base fragment */
    this.list = null;           /* and no embedding */
    this.tail = this.curr = null;
    this.max  = (max > 0) ? max : Integer.MAX_VALUE;
    this.cnt  = 0;              /* set memory usage parameters */
    this.src  = this.dst  = 0;  /* clear the extension information */
    this.chns = this.size = 0;  /* and init. the other parameters */
    this.idx  = -1;             /* there is no previous bond */
    this.flgs = DEFAULT;        /* set the default properties */
    this.supp = new int[3];     /* create the support counters */
    this.supp[0] = this.supp[1] = this.supp[2] = 0;
  }  /* Fragment() */

  /*------------------------------------------------------------------*/

  protected void add (Embedding emb)
  {                             /* --- add (a list of) embedding(s) */
    /* It is assumed that all embeddings in the list to be added */
    /* refer to the same underlying molecule. On the other hand, */
    /* the function may be called several times with different   */
    /* lists of embbedings that all refer to the same molecule.  */
    if (this.list == null) {    /* if the list is empty, */
      this.list = emb;          /* set embedding(s) as the new list */
      this.supp[emb.mol.group]++; }
    else {                      /* if there is already a list, */
      this.tail.succ = emb;     /* append the new embedding */
      if (emb.mol != this.tail.mol) {
        this.supp[emb.mol.group]++;
        this.cnt  = 0;          /* count the molecule if necessary, */
        this.curr = emb;        /* (re)init. the embedding counter, */
      }                         /* and note the new embedding(s) */
    }                           /* as the first for this molecule */
    do {                        /* traverse the embedding list */
      this.cnt++;               /* count the embedding */
      this.supp[2]++;           /* (per molecule and globally) */
      this.tail = emb;          /* note new tail of embedding list */
      emb       = emb.succ;     /* and go to the next embedding */
    } while (emb != null);      /* while not at the end of the list */
    if ((this.cnt      <= this.max)
    ||  (this.tail.mol == this.list.mol))
      return;                   /* check condition for packing */
    if (this.mol == null)       /* create molecule if necessary */
      this.mol = new Molecule(this);
    /* Note that creating this molecule works only, because it is  */
    /* certain that the current embedding refers to a different    */
    /* molecule than the one that is used to create this molecule. */
    /* This is also the reason why the embeddings for the first    */
    /* molecules cannot be packed, at least not at this point.     */
    this.tail = emb = this.curr;
    emb.base  = null;           /* if there are too many embeddings */
    emb.atoms = null;           /* for the current molecules, */
    emb.bonds = null;           /* delete them and only keep */
    emb.succ  = null;           /* a reference to the molecule */
  }  /* add() */

  /*--------------------------------------------------------------------
  The initial fragment for the search is created from embeddings of the
  seed into all molecules. These embeddings are not restricted w.r.t.
  possible extensions, that is, all atoms can be extended. Note that
  the add function assumes that, if multiple embeddings are added with
  one call (list of embeddings), they all refer to the same molecule.
  --------------------------------------------------------------------*/

  protected Fragment (Extension ext)
  {                             /* --- create an extended fragment */
    int  i, k, na;              /* loop variable, counters, buffer */
    Atom a;                     /* to traverse the atoms */

    this.mol  = null;           /* not yet available as a molecule */
    this.base = ext.frag;       /* note the base fragment */
    this.list = this.tail = this.curr = new Embedding(ext);
    this.list.succ = null;      /* create a corresponding embedding */
    this.max  = ext.frag.max;   /* copy the maximum number */