Using Hypergraphs for Chemical Synthesis Design

Rojin Kianian
Department of Mathematics and Computer Science, University of Southern Denmark

Rolf Fagerberg
Department of Mathematics and Computer Science, University of Southern Denmark

Christoph Flamm
Institute for Theoretical Chemistry, University of Vienna

Daniel Merkle
Department of Mathematics and Computer Science, University of Southern Denmark

Peter F. Stadler
Bioinformatics Group, Department of Computer Science and Interdisciplinary Center for Bioinformatics, Leipzig

PDF

Minisymposium: CHEMICAL GRAPH THEORY

Content: Sophisticated tools have been developed 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 often limited to revolve around the question of 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 as hyperpaths in a hypergraph. As a consequence, a polynomial time algorithm to find the $K$ shortest hyperpaths can be adapted to compute the $K$ best synthesis plans. Since any modeling and cost measure definition necessarily leaves out many real-world details, finding a (small) set of good plans -- as oppose to merely one -- allows a chemist to choose a good plan based on additional chemical knowledge and actual wet-lab feasibility. We discuss classical objective functions for synthesis plans, such as convergence of a plan and the total weight of starting materials.

Back to all abstracts