Flexible Depth-First Search With MX

Graph theory is an essential component of cheminformatics, if you dig deeply enough. MX is a lightweight cheminformatics toolkit written in Java with a major goal of exposing the most important cheminformatics graph manipulations in a flexible, Java-centric way. Previous releases have focused on implementing subgraph monomorphism functionality for use in substructure search. The new MX release, 0.104.0, introduces support for depth-first traversal. This article will give a simple example using this feature.

Downloading MX

MX can be downloaded in source or binary form:

• mx-0.104.0.jar Platform-independent bytecode.
• mx-0.104.0-src.tar.gz Source code and regression tests.

Scripting MX with JRuby

A previous article outlined the simple steps needed to install JRuby on unix-based systems for scripting MX.

Finding All Paths From a Given Atom

A fundamental graph operation in cheminformatics is finding all paths through a molecule from a starting atom. MX makes this easy with the com.metamolecular.mx.path.PathFinder class. Depth-first traversal is used in creating molecular fingerprints. Another use is in creating SMILES strings, although a limited form of depth-first traversal is used in which each atom in a molecule is traversed only once.

We can create a short library to print out all of the paths through a molecule in JRuby:

require 'mx-0.104.0.jar'
import 'com.metamolecular.mx.path.PathFinder'

class PathPrinter
  def initialize
    @finder = PathFinder.new
  end

  def print_paths atom
    paths = @finder.find_all_paths atom

    puts "printing all paths through the molecule"

    paths.each do |path|
      print_path path
    end
  end

  private

  def print_path path
    path.each do |atom|
      print atom.get_index
      print '-' unless path.get(path.length - 1).equals(atom)
    end

    puts
  end
end

Saving the above code in a file called pathprinter.rb, we can test it from interactive JRuby:

jirb
irb(main):001:0> require 'pathprinter'                   
=> true
irb(main):002:0> import com.metamolecular.mx.io.Molecules
=> Java::ComMetamolecularMxIo::Molecules
irb(main):003:0> benzene=Molecules.create_benzene        
=> #<Java::ComMetamolecularMxModel::DefaultMolecule:0x43da1b @java_object=com.metamolecular.mx.model.DefaultMolecule@8a2023>
irb(main):004:0> p=PathPrinter.new                       
=> #<PathPrinter:0x19ed7e @finder=#<Java::ComMetamolecularMxPath::PathFinder:0x3727c5 @java_object=com.metamolecular.mx.path.PathFinder@1140709>
irb(main):005:0> p.print_paths benzene.get_atom(0)       
printing all paths through the molecule
0-5-4-3-2-1
0-1-2-3-4-5
=> nil

How It Works

Two classes collaborate in this traversal: com.metamolecular.mx.path.PathFinder and com.metamolecular.mx.path.DefaultStep.

Creating a depth-first traversal of your own is as simple as creating a DefaultStep from an Atom and implementing a walk method similar to the one shown below:

public void walk(Step step)
{
  if (!step.hasNextBranch())
  {
    // do something with the completed branch

    return;
  }

  while(step.hasNextBranch())
  {
    Atom next = step.nextBranch();

    if (step.isBranchFeasible(next))
    {
      walk(step.nextStep(next));

      step.backTrack();
    }
  }
}

Conclusions

Depth-first traversal is an important tool in any cheminformatics library. MX offers an implementation of this traversal strategy that can be easily customized.