生物网络中进化算法的应用综述

### 生物网络中进化算法的应用综述 在生物网络的研究中，蛋白质复合物检测、生物网络对齐和基因调控网络推断是三个常见且具有挑战性的任务。由于网络结构分析的固有性质和生物数据的日益复杂性，这些任务在计算上颇具难度。而进化算法（EAs）凭借其在寻找全局最优解方面的优势，正逐渐成为解决这些问题的可行技术。 #### 1. 蛋白质复合物检测 蛋白质复合物检测旨在识别蛋白质 - 蛋白质相互作用（PPI）网络中的蛋白质复合物。在PPI网络中，图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成，每个顶点对应一个蛋白质，每条边连接两个有相互作用的蛋白质。蛋白质复合物对应于PPI网络中的一个子图 $C \in G$，通常是由多个蛋白质 - 蛋白质相互作用连接而成的密集蛋白质簇。 ##### 1.1 基于遗传算法（GA）的方法 - **GA - RNSC**：Pizzuti和Rombo将GA与受限邻域搜索聚类（RNSC）相结合，用于发现PPI网络中的簇。 - **BiCAMWI**：在预处理阶段使用GA提取双簇，能够检测动态PPI网络中的蛋白质复合物。 - **GACluster**：设计了新的目标函数，以最大化簇内凝聚性并最小化簇间耦合。为避免干扰潜在的良好解决方案，排除了交叉算子，并采用了改进的变异算子。 - **EGCPI**：采用进化聚类策略，同时考虑拓扑结构和蛋白质属性。 - **GA - PPI - Net**：为GA引入特定的变异算子，用于检测蛋白质 - 蛋白质或基因 - 基因相互作用网络中的社区。 - **MGOC**：是一种双目标聚类方法，采用PPI网络的拓扑属性和基于基因本体（GO）的生物学属性作为目标函数，使用NSGA - II作为多目标框架来寻找帕累托解。 | 算法 | 框架 | 年份 | | --- | --- | --- | | Abduljabbar等 | GA | 2020 | | GA - PPI - Net | GA | 2019 | | EGCPI | GA | 2016 | | GACluster | GA | 2016 | | BiCAMWI | GA | 2016 | | GA - RNSC | GA | 2014 | | Pizzuti和Rombo | GA | 2012 | ##### 1.2 基于群体智能（SI）的方法 - **IQ - Flow**：基于量子行为粒子群智能（PSO）的功能流算法，能够在计算模块间最低相似度时确定最佳阈值。 - **Sharafuddin等**：开发了基于PSO的方法，以簇得分作为适应度函数评估每个子图。 - **NACO - FMD**：将拓扑属性与功能信息相结合，通过计算蛋白质对之间的距离在一定程度上克服噪声，有效引导蚂蚁在解空间中搜索。 - **ACO - MAE**：将蚁群优化（ACO）与多智能体概念相结合，避免局部最优，提高搜索性能。 - **HAM - FMD**：是ACO - MAE的改进版本，采用不同的聚类方法并应用受限邻域，减少候选节点数量，更有效地检测PPI网络中的功能模块。 #### 2. 生物网络对齐 生物网络对齐（BNA）问题的目标是基于蛋白质的拓扑和生物学相似性，在不同生物网络之间对齐蛋白质。给定两个无向图 $G_1 = (V_1, E_1)$ 和 $G_2 = (V_2, E_2)$，BNA问题旨在找到网络之间的最优对齐，可通过评分函数 $S$ 进行衡量。 ##### 2.1 基于GA的方法 - **GEDEVO**：基于图编辑距离（GED）的优化模型，采用GA最小化GED，以获得生物网络的最优对齐。 - **GEDEVO - M**：是GEDEVO的扩展，能够对齐多个PPI网络。 - **MAGNA**：基于GA的全局网络对齐方法，提出了新的交叉算子，并开发了新的对齐质量度量 $S3$。其改进版本包括MAGNA++、DynaMAGNA++和multiMAGNA++。 - **MeAlign**：结合GA和局部搜索细化，目标函数集成了生物网络的拓扑结构和序列相似性。 - **Optnetalign**：多目标模因算法（MA）方法，根据帕累托优势平衡拓扑和序列相似性的冲突目标，使用拥挤比较算子，并采用多种算子创建对齐种群。 - **ImAlign**：应用自适应人工免疫系统（AIS），通过自适应克隆选择方法结合个体的适应度和浓度，在保留生物网络的拓扑和生物学属性方面表现良好。 ##### 2.2 基于SI的方法 - **NABEECO**：首个基于人工蜂群（ABC）优化的BNA方法，关注生物网络的拓扑结构，采用GED作为优化模型。 - **PSONA*