Large-Scale Bi-Level Strain Design Approaches and Mixed-Integer Programming Solution Techniques

The use of computational models in metabolic engineering has been increasing as more genome-scale metabolic models and computational approaches become available. Various computational approaches have been developed to predict how genetic perturbations affect metabolic behavior at a systems level, and have been successfully used to engineer microbial strains with improved primary or secondary metabolite production. However, identification of metabolic engineering strategies involving a large number of perturbations is currently limited by computational resources due to the size of genome-scale models and the combinatorial nature of the problem. In this study, we present (i) two new bi-level strain design approaches using mixed-integer programming (MIP), and (ii) general solution techniques that improve the performance of MIP-based bi-level approaches. The first approach (SimOptStrain) simultaneously considers gene deletion and non-native reaction addition, while the second approach (BiMOMA) uses minimization of metabolic adjustment to predict knockout behavior in a MIP-based bi-level problem for the first time. Our general MIP solution techniques significantly reduced the CPU times needed to find optimal strategies when applied to an existing strain design approach (OptORF) (e.g., from ∼10 days to ∼5 minutes for metabolic engineering strategies with 4 gene deletions), and identified strategies for producing compounds where previous studies could not (e.g., malate and serine). Additionally, we found novel strategies using SimOptStrain with higher predicted production levels (for succinate and glycerol) than could have been found using an existing approach that considers network additions and deletions in sequential steps rather than simultaneously. Finally, using BiMOMA we found novel strategies involving large numbers of modifications (for pyruvate and glutamate), which sequential search and genetic algorithms were unable to find. The approaches and solution techniques developed here will facilitate the strain design process and extend the scope of its application to metabolic engineering.

随着基因组尺度代谢模型（genome-scale metabolic models）与各类计算方法的不断涌现，计算模型在代谢工程领域的应用正持续增长。学界已开发出多种计算方法，用于预测遗传扰动如何在系统层面影响代谢行为，并已成功用于改造微生物菌株以提升初级或次级代谢产物的产量。然而，由于基因组尺度代谢模型的规模庞大且问题本身具有组合特性，涉及大量扰动的代谢工程策略识别工作目前仍受限于计算资源。本研究提出两项核心成果：(i) 两种基于混合整数规划（mixed-integer programming, MIP）的新型双层菌株设计方法；(ii) 可提升基于MIP的双层方法性能的通用求解技术。第一种方法（SimOptStrain）可同时兼顾基因敲除与异源反应添加；第二种方法（BiMOMA）则首次在基于混合整数规划的双层问题中，借助代谢调整最小化（minimization of metabolic adjustment）预测基因敲除行为。我们提出的通用MIP求解技术应用于现有菌株设计方法（OptORF）时，可显著缩短寻找最优策略所需的CPU运行时间——例如针对包含4个基因敲除的代谢工程策略，耗时可从约10天缩短至约5分钟；同时还可识别出此前研究无法实现的化合物生产策略（如苹果酸与丝氨酸）。此外，借助SimOptStrain，我们发现了针对琥珀酸与甘油的新型策略，其预测产量高于现有方法——现有方法仅按序考量代谢网络的添加与敲除，而非同时进行。最后，通过BiMOMA，我们发现了涉及大量修饰的新型策略（针对丙酮酸与谷氨酸），这类策略是序贯搜索与遗传算法无法获取的。本研究开发的菌株设计方法与求解技术，将有效简化菌株设计流程，并拓展其在代谢工程领域的应用范围。