演化蛙跳算法的药物-靶标相互作用预测

陆行政，林畅然，李智健，唐德玉

（广东药科大学医药信息工程学院，广州 510000）

0 引言

药物研发是现代社会中的一个重要课题，药物重定位是指发现现有药物的新用途，其生物学基础是一药多靶和一靶多药［1］。基于计算方法对药物-靶标相互作用（drug-target interaction，DTI）进行预测，以发现某个药物的多个潜在靶标或某个靶标的多个药物，从而实现对现有药物的重定位，可以显著减少后期过程（如临床试验）的负荷，节省大量资源和时间［2］。

研究人工智能的药物研发辅助系统，可以提高新药研发的速度和精度。杨朔等［3］通过引入高维分子指纹和蛋白质描述符并应用概率矩阵分解算法生成负样本集，构建一个高效的药物-靶标相互作用预测分类模型，训练不同的机器学习模型来预测DTI； Yamanishi 等［4］基于药物的理化性质和药物-靶标相互作用网络的拓扑性质，提出了基于支持向量机的方法，挖掘可能的药物-靶标相互作用； Mizutani 等［5］基于药物-靶标相互作用谱和副作用谱，定义稀疏典型相关分析进行预测。然而由于缺少负样本数据，使得监督学习方法预测效果不够理想，而且大部分有监督预测方法的时间复杂度较高［6］；同时，这些方法都严重依赖于药物的化学结构相似性和靶标的序列相似性。

为了缓解这些问题，我们使用了一种改进的洗牌蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）——演化蛙跳算法（evolutionary frog leaping algorithm，EFLA）预测药物-靶标相互作用，此算法由Tang 等［7］提出，但此算法并未应用于药物-靶标相互作用预测，本文的创新之处在于运用此算法解决药物-靶标相互作用预测难题。

1 提出的方法

1.1 训练数据集的产生方法

本文所用的数据来自Yamanishi 等［4］提供的来自人类酶（enzyme，EN）、离子通道（ion channels of biomembrane，IC）、G 蛋白偶联受体（G Protein-Coupled Receptors， GPCR）、 核受体（nuclear receptor，NR）的药物、靶标及其相互作用数据。四个数据集的信息见表1。

表1 药物靶标数据

各数据集中主要包括三种矩阵：Sd、St 和DTI。药物相似性矩阵Sd：表示某种药物与其他药物相似性。靶标相似性矩阵St：表示某靶标与其他靶标的相似性。药物-靶标相互作用矩阵DTI：表示某药物对某靶标是否具有相互作用，有相互作用的为1，无相互作用为0。

对于数据源的处理，我们尝试以药物与靶标的相似性作为预测药物-靶标相互作用关系的指标。将EN、GPCR、IC、NR 的Sd、St 以及DTI 矩阵分别合并成用于SVM 分类预测的药物靶标复合矩阵。合并原理如图1 所示，以1 号药物与3 号靶标为例，根据DTI 矩阵，1 号药物与3 号靶标是有相互作用的，将表示1 号药物与其他药物的相似性的一行与表示3号靶标与其他靶标的相似性的一行合并，作为新矩阵上的一行，并在最后加上一列，表示类标号，类标号“1”表示药物对该靶标有相互作用；类标号“0”表示无相互作用。由于无相互作用的药物靶标数量远大于有相互作用的药物靶标数量，因此合并时会先找出全部有相互作用的药物靶标，再随机找出同等数量无相互作用的药物靶标来进行合并。最后得到用来分类预测的药物靶标复合矩阵，其中每一行为一个样本，每一列为一个特征。运用随机获取的办法选择负样本。

图1 合并原理

1.2 演化蛙跳算法优化的SVM算法介绍

预测药物-靶标相互作用的机器学习模型之一是支持向量机（SVM），支持向量机是一种有监督的机器学习方法，它能有效解决小样本学习、高维及非线性问题，并表现出较强的泛化能力，在模式识别、分类等领域有着广泛的应用。支持向量机的两个主要参数极大程度上决定了其学习精度和泛化能力［8］。通常而言，比较重要的参数是gamma（-g）跟cost（-C）。C是惩罚系数，理解为调节优化方向中两个指标（间隔大小、分类准确度）偏好的权重，即对误差的宽容度，C越高，说明越不能容忍出现误差,容易过拟合；C越小，容易欠拟合，C过大或过小，泛化能力变差。g是选择RBF 函数作为kernel后，该函数自带的一个参数。隐含地决定了数据映射到新的特征空间后的分布，g越大，支持向量越少；g值越小，支持向量越多。支持向量的个数影响训练与预测的速度。

具体实现步骤如下。

Step1：选取SVM 模型训练样本和检验样本，进行样本归一化处理，设定惩罚因子C、核函数参数g和不敏感系数ε的搜寻范围［9］。

Step2：确定各算法的适应度函数。适应度函数是描述种群个体优劣程度的主要指标，本文选用均方误差作为适应度函数，见方程：

其中：yi代表第i个样本实测值；̂代表第i个样本模拟值。

Step3：基于EFLA 算法操作流程获得待优化惩罚因子C、核函数参数g和不敏感系数ε值。

SFLA 可以描述如下：首先，初始种群是随机产生的，并按降序排列分成m个子模块。洗牌过程可表示为公式（2），其中popsize（popsize=m×n）是一个整数，表示种群大小，m表示子群的数量，n表示每个子群中青蛙的数量。第i只青蛙的适应度f（i）可以评估并按降序排序，形成m个memeplex：H1,H2,…,Hb,…,Hm，它们可以通过以下方式构建：

其中：H是一个memeplex 中的解决方案的集合，Xi表示一个解决方案，它是一个矢量。

但在SFLA 中，青蛙只有跳跃行为来传播信息，这不足以模拟它们的社会行为。因此，可以通过模拟互动学习特征来模拟青蛙的社会行为。演化蛙跳算法是由Tang 等［7］提出的一个SFLA 的两阶段搜索框架，在第一个搜索阶段，用量子进化算子来实现局部搜索，它模拟了青蛙在量子空间中的跳跃行为。在第二阶段的搜索中，利用自适应特征向量进化算子实现全局搜索，模拟了青蛙的交互学习特征。该算法根据EFLA 算法实现，该框架使SFLA 的开发和探索更加平衡。以下介绍量子进化算子和自适应特征向量进化算子：

量子进化算子：量子进化算子在不同的子元丛中通过打乱过程实现，如方程（2），因此可以被认为是一种局部搜索过程。量子进化算子是根据势阱模型通过蒙特卡罗方法实现的。在方程（3）中，考虑到收敛性，Xi(t) →Pi(t) ，当t→∞时，其中Pi被视为势阱。基本的量子进化算子只使用一个势阱，从而加速搜索速度，但容易陷入局部最优解。为此，我们提出了带有记忆的第二个势阱来增强量子进化的搜索能力。我们尝试使用该算法优化SVM 的C、g参数来优化SVM 的模型训练。算法第一阶段通过提出一个具有记忆的潜在阱优化了量子模拟方法的参数，增强了SFLA 算法的搜索能力，使算法不容易落入局部最优解。新的搜索算子可以用方程式（4）表示。

其中：Pi表示第一个势阱，表示第二个势阱，g是搜索参数，popsize是种群大小。rand表示［0,1］中的均匀分布的随机数。Pi是D 维空间中的一个向量。在D 维空间中，也是其中的一个向量。

自适应特征向量进化算子：互动学习行为是在整个群体中实现的，而不是在局部群体中。因此，它是一个全球搜索过程，表示为以下公式：

在一个D 维空间中，Xi、Xv和Xo是对应于三只青蛙的三个向量。i、v和o（i≠v≠o）是集合中的三个不同整数，其中popsize是种群大小。Xi是解向量，可以通过Xv和Xo之间的差异进行更新。rand表示［0,1］均匀分布的随机数。是种群中所有Xi的均值，是种群中所有Xj的均值。

为了计算特征向量基，我们将协方差矩阵cov(Y)分解为正则形式如下：

其中：Q是方形矩阵（D行和D列），其第1 列是cov(Y)的特征向量qi。Λ是对角线矩阵，其对角线元素是相应的特征值。特征向量进化算子可表示为

其中：Xi（或Yi）表示一个个体，它是一个有一列和D行的向量，QT是一个由D行和D列组成的方形矩阵。D表示解决方案矢量的维度。因此，［QT-Xi］（或［QT-Yi］）表示一个新的个体，它是一个有一列和D行的向量。Ui是一个整数集合，包括从1 到D的所有整数，表示个体（［QT·Yi］）随机选择的r行数据，其中r也是从｛1,2,3,…，D｝这个集合中随机选取的整数。

当用特征向量作为基础更新解决方案时，更新行为会在自然基础上变得具有旋转不变性。为了减少具有旋转不变性的算子（）无效行为的风险，我们引入了一种自适应选择策略，以选择原始算子和特征向量进化算子。

其中：rand为［0, 1］中均匀分布的随机数，p为自适应选择参数值。它可以表示如下：

鉴于现实世界优化问题的复杂性，原算子和特征向量进化算子将根据其成功率交替运行，并通过公式（10）和（11）的自适应选择机制来实现。在一定程度上降低所处理的多元数据的维数，加快训练速度以及一些无用信息的剔除。

Step4：将获得的优化参数值作为SVM 的最佳学习参数对预测样本进行预测。

图2为上诉方法的算法流程图。

图2 EFLA算法流程

1.3 算法描述

设置算法参数，包括种群大小、迭代次数等；初始化一个由ps只青蛙组成的种群X，并计算适应度。在fes≤max_fes的循环中，先进行局部搜索，将种群X按适应度排序，然后对每个memeplex 中的n只青蛙，根据公式计算出两个最佳位置，计算潜在的两个最佳位置，并更新位置。

然后进行全局搜索：对每个青蛙，根据公式计算出新位置Yi，并根据条件随机选择标准搜索或特征向量搜索，根据成功率更新概率p，重复以上步骤直至达到最大迭代次数，最终输出全局最佳解。

2 实验结果与讨论

2.1 预测药物靶标相互作用

本实验使用核受体预测数据，把演化蛙跳算法与KNN 算法、朴素贝叶斯算法、决策树和随机森林进行分析比较，所得结果见表2。

表2 算法比较

各算法的使用参数见表3。

表3 算法使用参数

2.2 比较结果分析

分析表2的预测结果可以得知，演算蛙跳算法虽然预测时间较长，但准确率要远好于其他方法。与KNN 算法相比，准确率提高了14 个百分点；与朴素贝叶斯算法和决策树算法相比，准确率均提高了34 个百分点；与随机森林算法相比，准确率提高了11个百分点。

基于演算蛙跳算法的SVM 模型训练因为需要不停训练模型之后进行比较从而取得最好的参数，所以相比于其他常见的机器学习算法训练花费的时间较长，但是训练的结果相比于其他算法的准确率普遍高出10个百分点。

3 结语

在药物研发领域，药物靶标相互作用一直是一个重要的课题，以往的实验挖掘研究方法既耗时又费力，所以采用不同的数学分析模型来预测药物靶标是否具有相互作用，可以大大降低药物研发的风险和成本。

本文的研究是在大数据背景下，以人工智能新技术为基础，为新药的研发提供理论指导。作为人工智能的一个重要分支，群体智能算法已解决了很多机器学习中普遍存在的问题，大大提高了机器学习的性能。因此，本文重点以疾病-通路-靶标-药物的分子网络为基础，使用群体智能算法为主的机器学习方法，对新药物研发具有实际意义：

（1）对于指定的疾病，可以高效地识别新的药物-药物、药物与靶标的相互关系。可以在药理实验之前，对新的药物、靶标、通路及疾病的关系完成理论分析，为后面的理论实验奠定基础。

（2）本文的研究进一步扩展了传统的药物分析方法，完善了传统药物网络分析方法的不足。建立多源同构的药物团分析模型，并以进化计算的方法对其求解。

（3）对于很多复杂疾病，尽管组合药物临床疗效显著，在医药界有一定的发展，但由于组合药物的作用机制不明，限制了组合药物的设计和研发。本文算法的提出和发展，为组合药物的研制和开发提供了强有力的理论支撑。

本文尝试将演算蛙跳算法运用于药物靶标预测。通过与其他算法比较，演算蛙跳算法的训练时间较长，但准确率高于一般常见的机器学习算法10个百分点以上。