《Journal of Chemical Information and Modeling》：Navigating Large Chemical Spaces Using Graph Theory and Integer Programming
编辑推荐：
导航与分析大型化学空间对于加速新分子与化学工艺的设计和发现十分必要。本研究提出一种融合图论（graph theory）与整数规划（integer programming, IP）的计算框架，以实现大型化学空间的高效导航。该框架将化学空间表示为图（graph），
导航与分析大型化学空间对于加速新分子与化学工艺的设计和发现十分必要。本研究提出一种融合图论（graph theory）与整数规划（integer programming, IP）的计算框架，以实现大型化学空间的高效导航。该框架将化学空间表示为图（graph），其中节点（node）表示分子，边（edge）依据领域特定信息表示相似程度或连接关系。借助该图表示，研究人员通过求解所谓的最小支配集（minimum dominating set, MDS）——即与所有其他分子均相连的最小分子集合——来识别代表性分子。研究人员给出了包括启发式与严格整数规划（IP）方法在内的一套最小支配集求解策略，表明这些策略能够纳入理化性质与领域特定逻辑及约束，从而便于识别具有目标性质的分子。研究人员以约15000个分子结构的全氟和多氟烷基物质（per- and polyfluoroalkyl substances, PFAS）化学空间为例验证框架有效性，并与t-SNE和K-means聚类等传统降维和聚类方法进行比较。
研究背景方面，在药物发现、材料设计与溶剂设计等领域，从潜在成千上万至数百万分子的化学空间中识别具有目标性质的分子是关键问题。对全部分子通过实验或分子模拟获取性质通常计算上不可行。数据科学方法如机器学习、主动学习、主成分分析（principal component analysis, PCA）、t分布随机邻域嵌入（t-distributed stochastic neighbor embedding, t-SNE）与均匀流形近似与投影（uniform manifold approximation and projection, UMAP）等降维技术，以及K-means、DBSCAN、层次聚类等聚类算法，虽可可视化与发现模式，但难以直接编码分子相似性，也难以获得覆盖化学空间的极小且具代表性、非冗余的分子子集。因此，研究人员开展本研究，将图论中的支配集（dominating set, DS）与最小支配集（minimum dominating set, MDS）概念引入化学科学，用图表示分子相似关系，并以整数规划求代表性分子集合。
论文发表于《Journal of Chemical Information and Modeling》。研究人员构建化学空间图G(V,E)，节点为分子，当分子对相似度不低于阈值ε时连边；最小支配集为基数最小的支配集，且解可不唯一。该研究意义在于为化学空间系统性导航提供可纳入理化性质与领域逻辑的数学优化框架，并能以较少分子代表全体空间，从而降低实验与模拟成本。
关键技术方法上，研究人员采用MACCS密钥（MACCS keys）将分子结构转为167位指纹，以Tanimoto系数量化结构相似性；构建无向图并依相似阈值ε控制图疏密；用贪心启发式算法求支配集上界；将最小支配集建模为整数规划（IP）并借求解器获精确或近优解；提出混合启发式—整数规划（hybrid heuristic–IP, HIP）方法，以启发式解基数约束缩小可行域。案例为美国EPA约15000个PFAS结构，并筛查1000种溶剂去除PFAS跨聚合物基质的问题。
- 2.
Methods
2.1. Graph Representation of Chemical Space
研究人员将化学空间定义为无向图G(V,E)，V为分子节点，E为相似度≥ε的分子对连边；全图与空图分别对应完全相似与完全不相似，支配集S满足每节点属于S或邻接到S中节点，最小支配集S_为基数最小者，可非唯一。
2.2. Encoding Molecular Similarity
研究人员用SMILES与SMARTS表示结构，取MACCS keys等指纹，以Tanimoto相似度s(u,v)=|X∩Y|/(|X|+|Y|?|X∩Y|)度量；ε越大图越稀疏，ε越小图越稠密，图布局不表达潜空间距离而由边表达相似性。
2.3. Computing the Minimum Dominating Set (MDS)
2.3.1. Heuristic (Greedy) Approach
因最小支配集为NP难，研究人员用贪心法按节点度选最大度节点入集并删其邻域，得近似支配集与上界；不同最大度节点选择会导致不同基数，说明启发式结果依赖步骤5选择。
2.3.2. Integer Programming Approach
研究人员设二值变量xi，目标为min∑i∈Vxi，约束xj+∑i∈NG(j)xi≥1保证每节点被自身或邻居覆盖；现代混合整数线性规划（mixed-integer linear programming, MILP）求解器可处理不同规模图并给出最优解。
2.3.3. Hybrid Heuristic–IP Approach
研究人员在整数规划中加入∑i∈Vxi≤|SH|的边界约束，以启发式基数限制可行域，提升稠密图求解效率，所得最小支配集记为S_HIP。
讨论与结论部分指出，传统降维与聚类方法缺乏直接编码分子相似性的能力，难以提供最小代表性分子集；图论与整数规划框架可灵活换用相似度度量，并将分子性质作为节点权重、以优化约束嵌入领域逻辑，如优先少电子分子或限定分子量阈值。在PFAS案例中，该框架能用远少于全空间的分子代表15000个PFAS结构，并将1000溶剂×15000 PFAS×聚合物基质带来的约1.2亿次实验或模拟（超30000 CPU小时）的筛选负担，转化为小规模代表性分子上的靶向实验与模拟。结论为：minimum dominating set（MDS）可作为化学空间代表性的严格数学定义；graph theory与integer programming（IP）结合能系统导航large chemical spaces；该框架较t-SNE与K-means更易获得minimal yet representative set，并可借node weighting与logic constraints服务溶剂设计、污染物捕获与分子筛选等应用。
