8.25 基于演化优化的生物网络配准

生物网络配准是为了找到不同种群之间不同蛋白质网络的相似子图。生物网络配准可以帮助我们预测蛋白质功能。网络配准主要分为局部网络配准和全局网络配准两种。局部网络配准是为了匹配网络的局部区域，而全局网络是为了匹配网络的所有节点。在全局网络配准中，一个重要的问题是同时匹配网络结构和生物信息。全局网络配准被证明是一个 NP 完全问题。

目标函数

以前的算法主要是通过最大化网络的拓扑相似度，实现生物网络配准。学者提出了许多拓扑 相 似 度 函 数， 如 edge correctness、 inducedconserved structure 和 symmetric substructurescore。后来通过同时优化节点序列和拓扑相似度提高配准准确率[38] 。通常引入一个参数 α 来调节节点序列和拓扑相似度的权重，类似于下面的形式：其中， T s 表示网络拓扑相似度；S s 表示节点序列相似度；α 是介于 0~1 之间的权重。

传统算法中，需要反复实验来确定 α 的值。文献 [39] 的作者将网络匹配问题建模成一个多目标优化问题，其中 T s 和 S s 作为两个目标函数。

个体表示

给定两个网络 和 ，使得 。网络 G 1 中的所有节点使用序列 标记。 对于网络G 2 ，使用一个随机排列的序列 表示。表示匹配结果，它是由 中的前 n 1个元素组成。

遗传算子

对于网络匹配问题，主要有两种交叉操作。第一种基于 knuths 正则分解和循环分解算法[40] 。这种交叉操作产生的子代可以很好地继承它们父代大部分的性质。另外一种交叉操作是均匀部分匹配交叉。网络匹配问题中使用的变异操作一般都非常简单，如文献 [39] 中随机交换一个染色体的两个元素。

局部搜索

作为一个被广泛采用的局部搜索算法，爬山法也被用于网络匹配问题[39] 。在文献 [39] 中，作者设计了两种基于爬山法的策略来改善匹配的种群并且增加了目标空间种群的多样性。在文献 [41] 中，作者设计了一种新的基于邻域的局部搜索算法。