Fagerberg Rolf, Flamm Christoph, Kianian Rojin, Merkle Daniel, Stadler Peter F
Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230, Odense, Denmark.
Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, 1090, Vienna, Austria.
J Cheminform. 2018 Apr 5;10(1):19. doi: 10.1186/s13321-018-0273-z.
In synthesis planning, the goal is to synthesize a target molecule from available starting materials, possibly optimizing costs such as price or environmental impact of the process. Current algorithmic approaches to synthesis planning are usually based on selecting a bond set and finding a single good plan among those induced by it. We demonstrate that synthesis planning can be phrased as a combinatorial optimization problem on hypergraphs by modeling individual synthesis plans as directed hyperpaths embedded in a hypergraph of reactions (HoR) representing the chemistry of interest. As a consequence, a polynomial time algorithm to find the K shortest hyperpaths can be used to compute the K best synthesis plans for a given target molecule. Having K good plans to choose from has many benefits: it makes the synthesis planning process much more robust when in later stages adding further chemical detail, it allows one to combine several notions of cost, and it provides a way to deal with imprecise yield estimates. A bond set gives rise to a HoR in a natural way. However, our modeling is not restricted to bond set based approaches-any set of known reactions and starting materials can be used to define a HoR. We also discuss classical quality measures for synthesis plans, such as overall yield and convergency, and demonstrate that convergency has a built-in inconsistency which could render its use in synthesis planning questionable. Decalin is used as an illustrative example of the use and implications of our results.
在合成规划中，目标是从可用的起始原料合成目标分子，可能需要优化成本，如过程的价格或环境影响。当前合成规划的算法方法通常基于选择一个键集，并在由其诱导的那些方案中找到一个好的方案。我们证明，通过将单个合成方案建模为嵌入在表示感兴趣化学过程的反应超图（HoR）中的有向超路径，合成规划可以表述为超图上的组合优化问题。因此，用于找到K条最短超路径的多项式时间算法可用于计算给定目标分子的K个最佳合成方案。有K个好的方案可供选择有很多好处：在后期添加更多化学细节时，它使合成规划过程更加稳健，它允许人们结合多种成本概念，并且它提供了一种处理不精确产率估计的方法。键集以自然的方式产生一个HoR。然而，我们的建模不限于基于键集的方法——任何已知反应和起始原料的集合都可用于定义一个HoR。我们还讨论了合成方案的经典质量度量，如总产率和收敛性，并证明收敛性存在内在的不一致性，这可能使其在合成规划中的应用受到质疑。十氢化萘用作我们结果的使用和含义的示例。
