一种基于改进多目标进化算法的生物代谢路径设计方法

摘要

本发明提出了一种基于改进多目标进化算法的生物代谢路径设计方法，包括设置基本参数，基本参数包括算法迭代次数G，种群大小N，交叉点判断次数M，并确定可利用的底物集和目标产物；采用基于化学相似性的生物路径编码方法进行种群初始化，生成初始种群，将初始种群设为父代种群；基于生物交叉和生物变异操作对父代种群进行交叉变异，获得子代种群；对父代种群和子代种群进行生物代谢路径评估，得到评估结果；基于父代种群和子代种群的评估结果进行帕累托前沿面排序；判断算法是否满足终止条件，如果不满足条件，则继续进行种群的生物交叉和变异，否则算法终止，输出帕累托前沿面，从帕累托前沿面中选择满足需求的个体。

说明书

技术领域

本发明属于生物代谢路径设计技术领域，尤其是涉及一种基于改进多目标进化算法的生物代谢路径设计方法。

背景技术

代谢工程的重点是微生物细胞工厂的工程，通过改变代谢路径来生产化学品、燃料、药品和药物。在代谢工程中，代谢路径的设计在生产增值化合物的过程中起着至关重要的作用。代谢路径设计是通过连接几个前体化合物或异源途径来寻找一组产生目标化合物的生化反应的过程。其中，"目标化合物"是要待生产的感兴趣的化合物，"前体化合物"是合成目标化合物的化合物。但是，生物代谢路径形成的代谢网络系统是非常复杂的，原因有三点：（1）生物代谢系统非常庞大，包括成千上万的反应和代谢物；（2）生物代谢系统非常难以建立数学模型，因为其具有时变性、非线性和不确定性；（3）生物代谢系统的功能是紧密协调的，所以很难进行严格的、定量的化学分析。因此，生物代谢路径设计是一项艰巨的任务。

传统上，代谢路径的设计是通过调查文献和数据库来寻找候选反应，并将这些反应手动组装成生化途径。这种方法非常依赖研究人员对催化反应的酶和微生物的生理学的生化知识。但一个人只能考虑少量的反应，还有很大可能无法考虑新颖的、预测的反应。所以这种方法无法拓宽路径的可能性。为了克服传统方法的局限性，又开发了相当多的计算方法，这些方法通过输出一个反应列表来表示一条可能的路径。同时为了确保路径的可行性，考虑了不同的评价标准，如总体化学计量、热力学潜力、理论产量、毒性和代谢负担。这些方法将代谢路径的设计问题转换成一个单目标优化问题，用各个评价标准得分的加权和作为预测途径的最终得分。可其局限性有两方面，一方面是这些方法忽略了这些不同标准之间的相关性和矛盾性。比如，如果路径较长，更多的异源反应和中间产物将被引入宿主生物体，这将增加毒性的概率。这样看来，较短的候选途径有利于减少代谢负担。但是一些特定的产品需要复杂的代谢网络来生成，并有相应的热力学和理论产量来达到满意的效果。如此一来，之前讨论的通过多标准得分相加对候选路径进行排名的方法可能会得到一个次优的结果，它不能有效地搜索决策空间并产生更多额外的好的候选途径。另一方面，不同评估标准指标之间的衡量单位不统一，通常需要给不同的标准分配不同的权重值，但是在没有太多事先信息的情况下，如何合理分配权重值是一个新的技术难点。通常是给衡量单位较大的标准分配较大的权重，这种方式同时也会放大该标准的噪声。因此，想要获得高性能的代谢路径，需要对所有标准进行优化权衡。

发明内容

有鉴于此，本发明提出一种基于改进多目标进化算法的生物代谢路径设计方法，通过改进传统的进化算法,使其适应于生物代谢路径的编码、交叉、变异和评估，最后使用帕累托前沿面权衡多个评估方案，选择最佳的候选路径，解决了现有设计工具未考虑评估方式之间的竞争和矛盾关系的问题。

为达到上述目的，本发明的技术方案是这样实现的：

一种基于改进多目标进化算法的生物代谢路径设计方法，具体包括如下步骤：

步骤1：设置基本参数，包括算法迭代次数G，种群大小N，交叉点判断次数M，并确定可利用的底物集和目标产物；

步骤2：采用基于化学相似性的生物路径编码方法进行种群初始化，生成初始种群，并将其设为父代种群；

步骤3：基于生物交叉和生物变异操作对父代种群进行交叉变异，获得子代种群；

步骤4：对父代种群和子代种群进行生物代谢路径评估，得到评估结果；

步骤5：基于父代种群和子代种群的评估结果进行帕累托前沿面排序；

步骤6：判断算法是否满足终止条件，如果不满足条件，则转到步骤3继续进行种群的生物交叉和变异，否则进入步骤7；

步骤7：算法终止，输出帕累托前沿面，从帕累托前沿面中选择满足需求的个体。

进一步的，所述步骤2中，基于化学相似性的生物路径编码方法具体包括：

步骤201：将化合物和反应处理为反应对；

步骤202：计算每个反应对中底物和产物之间的化学相似性，并将其作为附加信息保存于反应对中，然后建立一个总配对池保存这些反应对，并按照不同的化合物进行分类；

步骤203：设置目标化合物的底物集，根据底物集中的底物从总配对池中选择相应的反应对，得到初始化的底物池；

步骤204：在底物池中随机选择一个底物作为起始化合物，在其对应的底物对中，使用基于化学相似性的轮盘赌策略进行选择；

步骤205：如果选择的反应对中的产物不存在于底物池，那么从总配对池中选出产物对应的反应对加入底物池，新的底物池记为，否则不更新底物池；

步骤206：判断产物是否是目标产物，如果是，则算法终止，编码结束，输出编码路径，否则返回步骤204。

进一步的，所述步骤3具体包括：从父代种群的若干个个体中随机选择两个个体作为父代个体，判断两个父代个体中是否存在相同的底物或产物，如果存在，则进行生物交叉操作，否则再次从父代种群中随机选取两个父代个体并判断，如果判断M次后仍然不存在相同点，进行生物变异操作。

进一步的，所述生物交叉操作具体包括：

以父代个体相同点的位置作为交叉点，交换父代个体在交叉点右侧的部分，组成两个新的子代个体。

进一步的，所述生物变异操作具体包括：

从父代种群中随机选择一个个体作为父代个体，再从父代个体中随机挑选一个化合物对对应的位置作为变异点；

以变异点对应的化合物作为起始化合物，以目标产物作为目标化合物，按照基于化学相似性的生物路径编码方法设计一条从起始化合物到目标化合物的新路径，得到新个体；

将新个体拼接到父代个体变异位置的右侧，形成一个新的子代个体。

进一步的，所述步骤4具体包括：分别计算父代种群和子代种群的评价指标，得到对应的评估结果，每个评估结果包括三个评估值，分别对应代谢路径长度、吉布斯自由能和理论产量。

进一步的，所述步骤5具体包括：先组合父代种群和子代种群形成一个新种群，将新种群中的所有个体分配到所有的帕累托前沿面中，并根据个体评估值判断每个个体所属的帕累托前沿面次序，从新种群中选择前N个个体构成新种群的父代种群。

相对于现有技术，本发明所述的一种基于改进多目标进化算法的生物代谢路径设计方法具有以下优势：

本发明将生物代谢路径设计问题建模为一个多目标优化问题，通过多目标优化算法中的帕累托前沿面权衡多种评价指标之间的竞争和矛盾关系，提高了寻找各方面评估指标的均衡的生物代谢路径的概率；

本发明提出一种基于化学相似性的生物代谢路径编码方法，解决了传统多目标进化算法由于生物代谢路径的变长性和连续性无法编码的问题，且相似性的加入使得编码的生物代谢路径提高了被酶催化的概率，提高了所设计的生物代谢路径的可行性；

本发明提出了生物交叉和生物变异的操作方法，解决了传统多目标进化算法无法应用于连续的生物代谢路径的问题，更大地扩展了搜索空间，提高了生物代谢路径的多样性。

附图说明

构成本发明的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

图1为本发明的方法流程示意图。

具体实施方式

需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”等仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”等的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。

在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以通过具体情况理解上述术语在本发明中的具体含义。

下面将参考附图并结合实施例来详细说明本发明。

如图1所示，本发明提供了一种基于改进多目标进化算法的生物代谢路径设计方法，具体包括：

步骤一：参数设置：确定优化方法的基本参数：算法迭代次数G，种群大小N，交叉点判断次数M，此外还需要确定可利用的底物集

步骤二：种群初始化：采用基于化学相似性的生物路径编码方法进行种群初始化，生成初始种群

具体的，基于化学相似性的生物路径编码方法具体包括：

在编码进行之前，要先对数据库进行处理，即先将生化反应处理为反应对，并计算每个反应对对应的化学相似性，然后构建反应对配对池。本发明提出的生物代谢路径编码方法基于之前计算的化学相似性从配对池中筛选反应对，构成代谢路径。通过这种编码方式，不仅解决了代谢路径的连续编码问题，还构成了更易于被酶催化的代谢路径。该编码方法的具体步骤如下：

处理反应对：将化合物和反应处理为反应对，如一个形如

构建总配对池：首先基于指纹描述符的相似性评估方法计算每个反应对中底物和产物之间的化学相似性，记为T，并将其作为附加信息保存于反应对中；

指纹是由预先定义的结构片段或在结构中发现的特征的列表组成，每个存在的特征通过使用数字1表示。这种方法中经常使用的指标是简单的距离测量，如Hamin和Euclid距离，以及关联系数，如Tanimoto、Dice、和Cosine系数。而根据基于指纹的相似性计算，Tanimoto系数是一个合适的选择。计算A化合物和B化合物之间的Tanimoto系数的公式如下：

其中，a和b分别是化合物A和化合物B的指纹中"1"特征的数量，c代表A和B的指纹中共同的"1"特征数量。

然后建立一个总配对池

初始化底物池：假定目标化合物为

选择反应对：在底物池中随机选择一个底物作为起始化合物，在其对应的底物对中，使用基于化学相似性的轮盘赌策略进行选择，具体的策略步骤如下：

1、假设选定的化合物s在底物池中共有n个反应对，第i个反应对

2、根据反应对被选择的概率

其中

3、在(0,1]之间生成一个均匀分布的伪随机数r，如果

更新底物池：如果选择的反应对中的产物p不存在于底物池

判断产物是否是目标产物

步骤三：生物交叉变异。基于生物交叉和生物变异操作对父代种群进行交叉变异，获得子代种群。通过生物交叉和生物变异操作产生的新个体，保存至子代种群Q

具体的，由于生物代谢路径具有变长和连续的特点，传统的交叉和突变方法会打破代谢路径的连续性，所以无法使用。为了解决这个问题，本发明提出了专门用于生物代谢路径设计的交叉和突变方法，命名为BioCrossover和BioMutation。通过所提方法，使得代谢路径在交叉和变异后，仍然能保持其变长性和连续性。BioCrossover和BioMutation具体的实现步骤如下：

a)判断相同点。从父代种群N个个体中随机选择两个个体作为父代个体，判断两个父代个体中是否存在相同的底物或产物，如果存在，则进行步骤b)，否则再次从父代种群中随机选取两个父代个体并判断，如果判断M次后仍然不存在相同点，则执行步骤c)。

b)BioCrossover

i.假设两个父代个体为

ii.交换父代个体在交叉点

c)BioMutation

i.从父代种群中随机选择一个个体作为父代个体，再从父代个体中随机挑选一个反应对对应的位置作为变异点

ii.以变异点对应的化合物

iii.将新个体

步骤四：生物代谢路径评估。分别计算父代种群

具体的，本发明将生物代谢路径设计问题看作一个多目标优化问题，包括三个优化目标：最小化路径长度、最小化热力学可行性和最大化理论产量，为了统一优化目标，将最大化理论产量定为最小化负理论产量。所以多目标生物代谢路径设计问题的数学模型如下所示：

其中，

路径长度

热力学可行性值

理论产量

步骤五：帕累托前沿面排序。先组合父代种群

步骤六：判断算法是否满足终止条件，即迭代次数达到规定的迭代次数，如果是则终止，进入步骤八，否则迭代次数加一，转到步骤三继续进行种群的生物交叉和变异。

步骤七：算法终止，输出帕累托前沿面（在此前沿面上的每个个体都被认为是同样重要的）。决策人员可根据自己的需求从帕累托前沿面中选择满足需求的个体。

本发明提出一种基于改进多目标进化算法的生物代谢路径设计方法，以糖酵解的过程为例，得到了帕累托前沿面，并从中选取三条极限路径，分别为最短长度路径、最小热力学路径和最大理论产量路径，与经典的糖酵解路径对比，在路径长度、热力学和理论产量上都有了显著提高，对比结果如表1所示。表1为在糖酵解过程中，本发明提出算法设计的路径与经典路径在三种评价指标上的对比结果。

糖酵解过程中，采用的数据集为KEGG中的KEGGCOMPOUND和KEGGREACTION部分，分别包括18900多个化合物和11800多条反应。底物池

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。