(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Algorithmic Cheminformatics --- Engineering a Chemical Graph Transformation System

Jakob Lykke Andersen
Institute for Theoretical Chemistry
University of Vienna

Wednesday, 01 November, 2017 at 14:15
IMADA's Seminar Room

ABSTRACT

For the modelling and computational analysis of chemistry on the level of systems we have developed a range of graph-based methods.  Molecules are modelled by labelled graphs, and graph transformation rules model generalised reactions.  This is used as the basis for a chemical graph transformation system that can be used to automatically generate reaction networks.  For analysing the behaviour of reaction networks we have developed a comprehensive pathway model, based on a generalisation of network flows from ordinary digraphs to directed hypergraphs.  We have proven many central hyperflow problems NP-complete, and our model is therefore implemented using ILP.  For enumerating multiple pathway solutions we have developed a tree-search algorithm on top of the state-of-the-art CPLEX solver.  Using reachability analysis in Petri nets we then analyse concurrency aspects of the pathways. The resulting reachability certificates can then be further used to perform tracing of atoms through pathways, in order to create an in silico model of stable isotope labelling experiments used in the wetlab to study chemical systems. In this talk I will focus on the engineering of a practically efficient chemical graph transformation system, that provides the foundation of the models.  We have adapted the traditional graph transformation methods to transformation of multisets of graphs, and we have developed the notion of rule composition which we for example use to implement graph transformation.  I will also present our recent extension of the transformation system to incorporate local geometric data, which allows modelling of stereochemistry.  In the final part I will present our very recent development of a generic framework for engineering graph canonisation algorithms, which through generic programming allows specification algorithm variations through individual visitor plugins.  The framework thus allows direct and fair performance comparison of individual algorithmic ideas.

Host: Fabrizio Montesi


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle