Graduate Theoretical Computer Science Seminar
Rojin Kianian
University of Southern Denmark
Finding the K best synthesis plans
Abstract: Synthetic Chemistry has developed sophisticated tools in order to create new compounds. However, current 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. We use classical objective functions for synthesis plans, such as overall yield or convergence of the plan. The 4-bond disconnections of decaline are used as an illustrative example.
Wednesday October 29, 2014 at 2:00 PM in SEO 427