Abstract for the talk at 14.10.2014 (15:00 h)VW-Seminar
Rojin Kianian (University of Southern Denmark)
Formal Methods for Synthesis Design
Synthetic chemistry has developed sophisticated tools in order to create new compounds. However, despite the fact that computer-assisted organic synthesis design has been an active research topic for decades, many well-established approaches from theoretical computer science are nearly unused in this context. For instance, algorithmic approaches to find optimal synthesis plans are limited to determining optimal bond sets. Noting that each bond set represents a possibly very large set of different synthesis plans for the target compound, there is a need for methods for choosing among these. We attack this problem by modeling synthesis plans for a given bond set as hyperpaths in a hypergraph. As a consequence, a polynomial time algorithm to find the K shortest hyperpaths can be adapted to computing the K best synthesis plans for the bond set. Since any modeling and cost measure deffinition necessarily leaves out many real-world details, finding a (small) set of good plans - as oppose to merely one - allows for a chemist to choose a good plan based on additional chemical knowledge and actual wet-lab feasibility. We use classical objective functions for synthesis plans, such as overall yield or convergence of the plan. I will end the talk by briefly raising and discussing other questions relevant to synthesis design.