author: Peter van Dijk
title: Searching for molecular structure using graph transformation
topics: Algorithms and Data Structures , Case studies and Applications , Graphs
committee: Arend Rensink ,
Hajo Broersma


Modern synthesis methods have improve to the point where it becomes feasible to actually synthesize materials based on a model of their molecular structure. This makes it possible to construct compounds not occurring in nature, with properties far exceeding anything that can be built in more conventional ways.

However, before actually taking the step of constructing something in vivo, as it were, it is an obvious idea to first model those structures that can exist according to the laws of physics and chemistry. Molecules are known to bond in certain ways and not others, and building a molecure can be likened to bulding a Lego structure from bricks of different shapes and with different connectors. Moreover, among the many, many different molecules that can be synthesized in principle, there is only a tiny fraction that have interesting properties, and it is not obvious up front which those are. Essentially, one can look upon this as an essentially infinite search space, within which the task is to find molecules with certain recognizable structural properties.

Modelling techniques from computer science can be used to (first) define and (subsequently) prune this search space. In particular, the structural properties of molecules make a graph-based model obviously suitable, and their step-by-step synthesis lends itself very well for a rule-based formalism such as graph transformation. This would take care of the first step. For the second step of pruning, heuristic techniques are a logical direction of investigation. These are well-known in the area of graph transformation, and indeed here is where the graph representation pays off as well: the structural properties in question can be expressed as graph patterns, and this makes existing notions of graph distance very suitable as a basis for a heuristic.

In this project, you will be asked to explore these possibilities. This consists of finding a suitable representation of molecules as graphs and their interactions as graph transformation rules, formulating structural properties as search goals, developing and applying suitable heuristics and experimenting with the resulting system.


  1. A Software Package for Chemically Inspired Graph Transformation (Digital version available here)