今天给大家介绍的是来自佐治亚理工学院的Le Song课题组发表在ICML2020上的关于逆合成规划的一篇文章。在本文中，作者提出了一种基于神经的类A*算法，称为Retro*，它能有效地找到高质量的合成路线。在基准USPTO数据集上进行的实验表明，作者提出的方法在成功率和解决方案质量方面均优于现有的最新技术，同时效率更高。
1
1背景
逆合成设计是有机化学的关键问题之一。由于在反应的每一步理论上都有成千上万种可能的转化导致设计的搜索空间是巨大的，即使是有经验的化学家处理这个问题也是十分棘手的。
单步逆合成预测对给定产物可能的直接反应物列表的预测，尽管单步合成法不断得到改进，但现实世界中的大多数分子都无法在一步之内合成。合成步骤的数量可以达到60个甚至更多。单步逆合成法面临着巨大的搜索空间和性能测量及基准测试模糊性的挑战，为实现多步逆合成设计奠定基础。
在本文中，作者提出了一种新的基于学习的逆合成设计算法Retro*来学习以前的设计经验，该算法框架可以归纳出保证最优解的搜索算法。另外，作者提出了一种构建合成路线数据集的方法，用于对多步合成设计方法进行定量分析。其设计算法是通用的，它也可以应用于其他机器学习问题，如定理证明和分层任务设计，实验结果表明该算法的性能大大优于现有方法。
2
框架
Retro*是最佳优先搜索算法，该算法利用神经先验直接优化解决方案的质量。在该算法中：
明确地将有关反应的信息保存为“AND-OR”树中的节点，其中“AND”类型的节点对应于反应，而“OR”类型的节点对应于分子。该树捕获了候选反应和反应物分子之间的关系，使得能够利用对应于单个分子的子问题的结构。
基于AND-OR树表示，作者提出了一种类A*的规划算法，该算法由从过去的逆合成设计经验中学习到的神经网络指导。
更具体地说，神经网络学习每个分子的合成成本，并帮助搜索算法选择最有希望的分子节点进行扩展。
图1 Retro* 算法
搜索树T是AND-OR树，其中分子节点为“OR”节点，反应节点为“AND”节点。它以单个根分子节点（即目标分子t）开始搜索树T。在每个步骤中，它根据值函数选择T边界中的节点u(表示为F(T))。然后用单步模型B(u)扩展u，并用一个AND-OR树桩增长T。最终，对u有潜在依赖性的节点将被更新。
图2 Retro *算法框架
3
实验
3.1 数据集
作者使用从USPTO提取的公开可用的反应数据集来训练单步模型并提取合成路线。对于有多种产物的反应，作者将它们复制成多种反应，每种反应有一种产物。删除重复和错误原子映射的反应后，进一步使用RDChiral 提取所有反应的反应模板，并丢弃那些无法通过将反应模板应用于其产品而获得反应物的模板。其余约1.3M反应按照80%/10%/10%的比例进一步随机分成训练/验证/测试集。利用反应数据，作者还训练了一个基于模板的MLP模型用于单步逆合成。为了训练值函数并定量分析预测的路线，作者基于USPTO反应数据集和eMolecules 的市售结构单元列表构建了合成路线。
作者获得的验证和测试路线数据集的过程略有不同。对于验证数据集，首先组合训练和验证反应数据集，然后在组合数据集上重复上述提取过程。作者排除具有与训练数据相同长度的路线的分子，并将剩余的作为验证路线数据集。作者对测试数据采用类似的方式，但要确保测试与训练/验证集之间没有重叠。
作者进一步清理测试路线数据集，只保留那些其反应被单步模型的前50个预测所覆盖的路线。为了使测试集更具挑战性，作者通过运行一个基于启发式的BFS规划算法来过滤掉更容易的分子，并在固定的时间限制内丢弃已解决的分子。经过处理，最终获得了299202条训练路线、65274条验证路线、189条测试路线和相应的目标分子。
3.2 结果
作者将Retro*与DFPN-E、MCTS和贪婪深度优先搜索(DFS)进行了比较。贪婪的DFS总是优先考虑可能性最大的反应。MCTS是通过PUCT实现的，在这里作者使用了单步模型提供的反应概率作为搜索偏差的先验。
表1 性能总结
性能总结：表1总结了所有算法的性能。在500个单步调用的时间限制下，Retro*比第二好的方法DFPN-E解决的测试分子多31％。Retro*提供的所有解决方案中，有50条比专家路线短，而有112条在总成本方面更好。作者还进行了消融研究，以通过评估非学习版本Retro*-0来了解Retro*中学习组件的重要性。与基线方法相比，Retro*-0也显示出有希望的结果，然而就成功率而言，Retro*表现优于6％，这表明从先前的规划经验中学习带来的性能提升。
图3 时间限制的影响
时间限制的影响：为了显示时间限制对性能的影响，图3绘制了成功率与单步模型调用次数的关系。可以看到，Retro*不仅在开始时大大优于基线算法，而且改进速度也快于基线，随着时间限制的增加，性能差距也在进一步扩大。
图4 解决方案质量
解决方案质量: 图4左: 就长度/成本而言，所有算法中最佳解决方案的数量；图4中:Retro*的示例解决方案路线。边上的数字是反应的可能性。黄色节点是构建模块；图4右:专家路线中相应的虚线框部分，比解决方案更长，可能性更小。
为了评估整体解决方案质量，对于每个测试分子，作者从所有算法中收集解决方案，并比较路线长度和成本(见图4-左)。作者只保留每个测试分子的最佳路线(可以是多条)，并计算每种方法的最佳路线总数。就总成本而言，Retro*比第二好的方法产生的最佳路线多4倍。即使对于长度度量，这也不是Retro*选择的目标，它仍然可以获得与最佳方法大致相同的性能。
4
结论
在这项工作中，作者提出了Retro*，这是一种基于学习的逆向合成设计算法，可以有效地找到高质量的路线。Retro*能够利用以前的设计经验，将对看不见的分子的搜索偏向有希望的方向。作者还提出了一种系统化的方法，用于从公开的反应数据集和新的度量标准中创建一个逆合成数据集，用于在不涉及人类专家的情况下评估解决方案路线。在真实世界基准数据集上的实验表明，该算法在设计效率和求解质量上均优于现有方法。
