最小生成树算法应用于蛋白质复合物识别实验设计

梁 冰，张益嘉，吕嘉庆

（1.大连理工大学 创新创业学院，辽宁 大连 116024；2.大连理工大学 电子信息与电气工程学部，辽宁 大连 116024）

算法基础作为计算机专业的核心课程，是计算机专业人才培养的基石，从事计算机学科的信息处理、人工智能、数据库、操作系统、图形图像等方面的研究，都离不开算法的应用[1-2]。传统的算法实验课程内容包括排序算法、树的遍历算法、图的最短路算法等基础算法[3-4]。

算法基础是一门实践性很强的课程，其教学不仅应该注重学生对理论知识的理解，锻炼学生的抽象思维和创造能力，还应注重培养学生的实践能力，而该课程实验课是学生验证、掌握和应用算法理论的重要手段，也是影响整个课程教学质量的重要因素。目前实验课程存在的主要问题，一是传统实验的设计题目过于程式化，不能调动学生的主动性思维。一些学生仅仅是拿一些现成的程序来应付实验，不能达到实验目的。综合设计性和探索创新性实验偏少，影响学生探讨问题的积极性和创新能力培养，学生虽能完成实验，但实践工作量严重不足。二是理论和实际结合不紧密，学生在课堂上虽然掌握了很多概念和理论，但是涉及实际项目的设计开发，往往就不能将已学知识和实际问题联系起来，对于算法设计和项目开发感到力不从心[5-7]。

根据前沿的研究热点设计实验内容，能够调动学生动手编程的热情，还能使学生在学习经典算法的同时，了解前沿研究热点，扩展知识面。

图论是计算机科学中最重要的领域之一，很多实际问题都可以通过图来建模，比如道路交通网、电网、通信网、水管网等。图论中需要掌握的算法，包括：bellman-ford 算法、Dijkstra 算法和floyd-warshall 算法等3 种最短路算法；Prim 算法和Kruskal 算法2 种最小生成树算法；Ford-Fulkerson 算法和Dinic 算法2 种网络流算法；以及最小费用最大流算法[8-9]等。掌握图论的经典算法，并能选择和应用其中的算法解决实际问题，是培养学生的主要目标。本实验项目就是为了实现这个目标而设计的。

1 蛋白质相互作用网络

蛋白质相互作用数据通常由蛋白质-蛋白质节点相互作用的蛋白质网络（protein-protein internet,PPI）表示，两个节点之间的边代表已知的两种蛋白质之间的相互作用。大多数蛋白质只有作为蛋白质复合物的一部分时，才具有生物活性。蛋白质复合物是执行复制、转录和基因表达等细胞功能的生物分子[10]。那么如何在PPI 网络中定义哪一组蛋白质属于同一个蛋白质的复合物，就成为一个问题。

近来人们花了很大精力去发现蛋白质-蛋白质相互作用中的蛋白质复合物网络，大规模费时费力地开展鉴定蛋白质复合物实验室实验，如亲和纯化（AP）实验和质谱（MS）实验[11]。为了减少实验中繁琐的试错步骤，最近还出现了一些通过计算方法识别蛋白质复合物的尝试。这些研究方法大多依赖于这样一种观点，即同一复合物中的蛋白质会有相对更多的相互作用。于是，这些研究方法根据不同的图聚类算法，可以发现基于不同拓扑性质，如密度、k 核、核附着生物分子的结构和外围等，目的是寻找PPI 网络中的稠密子图，这些方法给出了如何找到一个稠密子图以及将节点聚集成稠密子图的过程。因此，通过算法从网络图中识别蛋白质复合物，是生物学与计算机交叉学科的研究热点问题。

从蛋白质相互作用关系网的定义可知，PPI 网络完全符合图论中无向图（边没有方向的图称为无向图）的定义，因此，如何选择和应用图论中经典算法解决蛋白质复合物识别问题的实验项目，具有前沿性和创新性，能够培养学生科学研究的能力和解决实际问题的能力。

值得说明的是,不同分析方法基于不同的蛋白质拓扑性质，对同一种蛋白质网络使用不同分析方法会得到不同的分析结论，不同的分析方法也具有各自的分析特色。

2 蛋白质关系网络的拓扑特征

蛋白质相互作用网络与其他生物实体一样，缺乏自顶向下的设计。生物进化的选择性通过随机事件，如个别基因的突变和基因复制，形成了蛋白质网络。因此，蛋白质之间的联系具有很大程度的随机性，但有些联系则是由进化或功能设计原则和限制而产生的，具有非随机性。

本文提出的应用图论中最小生成树Prim 算法识别蛋白质复合物的研究方法，是利用了蛋白质相互作用网络拓扑学的以下3 个非随机性特征。

2.1 网路节点的度

PPI 网络的第一个非随机拓扑特征是节点的度，有时也称为连接度，即在给定的蛋白质网络中直接连接蛋白质的数量。

虽然大多数蛋白质与其他蛋白质只有少量的相互作用，但也存在具有大量直接连接的蛋白质节点，我们称之为“枢纽”。这种网络中连接最多的节点的度通常比网络中节点的平均度大几个数量级。 参与简单任务的蛋白质可能只需要几个相互作用的伙伴，而那些蛋白质“枢纽”则是用于更复杂和全局性任务的。

2.2 网络直径

蛋白质相互作用网络图中，任意两个节点之间距离的最大值叫做网络直径，而任意两点之间的距离为这两个节点的最短路径的长度。

这里还涉及连通图和非连通图的概念。如果蛋白质网络图中的任意一对顶点都是连通的，则称此网络图叫做连通图，反之则叫做非连通图。

因为非连通图的网络直径为所有连通子图的网络直径的最大值，因此非连通图的网络直径是无穷大的。

2.3 特征路径长度

蛋白质相互作用网络图中，所有最短路径长度的平均值称为特征路径长度。

特征路径长度描述了网络中节点的分离程度，且0≤特征路径长度≤1。当特征路径长度为1 时，表示该PPI 为连通图，当为0 时表示该PPI 图是完全离散的，特征路径长度越接近1，表示PPI 的连通性越好。

3 图论最小生成树Prim 算法

本研究基于蛋白质相互作用网络的非随机拓扑特征，应用图论中最小生成树Prim 算法进行蛋白质复合物识别。本研究方法的最大特点是能有效提升蛋白质复合物识别的性能。

那么什么是最小生成树呢？给定一个无向图,如蛋白质PPI 图，如果其某个子图中任意两个节点都互相连通，并且呈现一棵树的结构，那么这个PPI 图就称为具有生成树结构。生成树是一种重要的非线性数据结构，它是数据元素按分支关系组织起来的结构。如果两节点之间的边有权值，那么这些边权之和最小的生成树就叫做最小生成树。

最小生成树Prim 算法是图论中最小生成树的一种算法，可在加权连通图里搜索最小生成树。由此算法搜索到的边的子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和为最小。

从进化角度理解蛋白质复合物的形成，认为蛋白质复合物应该由一个具有关键功能的核心蛋白质开始扩展。核心蛋白质与某些蛋白质产生联系，形成蛋白质复合物，这个蛋白质复合物又继续与一些蛋白质产生联系，使复合物逐渐变大。在不断扩展的过程中，蛋白质复合物内部蛋白质之间的联系逐渐变得更加紧密。因此应用Prim 算法识别蛋白质的步骤为：

（1）首先进行初始化操作，将所有蛋白质节点入优先队列。优先队列是指，当访问元素时，具有最高优先级的元素最先删除的一种数据结构。

（2）取队列顶端的点，并找到所有与它相邻且不在树中的顶端的点，逐步进行优选。

（3）重复（2）的操作，直至队列为空。

（4）得到了两个数组，一个是表示树中连接节点的最小权值边的权值，一个是连接节点的上一级节点。

通过以上4 个步骤，使得“枢纽”蛋白质节点与其他相连接的蛋白质节点逐步形成蛋白质复合物。

实现Prim 算法的伪代码如图1 所示。

图1 实现Prim 算法的伪代码

4 实验设计与分析

4.1 基于Prim 算法的蛋白质复合物的具体识别

从图论角度来理解，把每个点的所有带权边的权值之和作为其是否为关键蛋白质的指标。

首先，使用Prim 生成树的算法实现，以生成树的过程去扩展蛋白质，每次扩展后，使用ClusterONE 算法[12]中提出的内聚性算法，判断蛋白质的内聚性。蛋白质复合物C 的内聚性由下式给出：

其中，Win是完全包含在C 中的边的权重之和，Wout是将属于C 的蛋白质连接到网络其余部分的边缘权重之和，m 用来反映蛋白质相互作用网络的不确定性。该指标用来反映复合物内部是否具有强连接，并与外部分离良好。

若蛋白质内聚性增加，则继续扩展。若蛋白质内聚性减小，则认为此次扩展不正确，撤回此次扩展，并将此次扩展前的蛋白质复合物放入结果中。对于每一个已经被加入过某个蛋白质复合物的蛋白质，均做标记，不再将其加入任何蛋白质，从而避免蛋白质重叠问题。

基于Prim 算法的蛋白质复合物识别核心Python代码如图2 所示。

图2 基于Prim 算法的蛋白质复合物识别核心Python 代码

4.2 实验评价标准

为了验证本算法的性能，我们用了4 个评价标准或称评价指标：F 值、阳性预测值PPV、精准率ACC和最大匹配率MMR。这4 个指标能够从不同侧面反映蛋白质复合物识别的准确性，指标得分越高，表示识别的准确性越好。由于篇幅所限，且这4 个指标为业内所周知，这里不对其具体计算详细展开。

4.3 实验结果及分析

以下对本研究基于Prim 算法的蛋白质复合物识别方法与其他6 种基于网络拓扑特征的蛋白质复合物识别方法进行比较。其他6 种方法分别为：MCL[13]，CMC[14]，RRW[15]，ClusterONE[12]，MCODE[16]，COACH[10]。比较结果见表1。

表1 不同蛋白质复合物识别算法的性能对比

本实验选取的标准蛋白质复合物来自于MIPS[17]，过滤掉标准蛋白质复合物中包含蛋白质个数小于3 的蛋白质复合物之后，共有203 个标准蛋白质复合物。

从表1 可知，本实验基于Prim 算法的蛋白质复合物识别方法的准确率虽然超过其他6 种算法（匹配率更高），但是预测数较低，因此本方法更偏向于精准预测，即虽然识别出的数量较少，但是正确率较高，为53.9%。

5 结语

算法基础是一门实践性课程，是计算机专业培养学生编程能力和算法设计能力的基础课程。通过在实验项目中引入前沿热点内容，鼓励学生进行独特的创新性设计并尝试新颖算法，能够激发学生的动手实践热情和编写程序的积极性。将所学算法用于解决实际问题，能够提升学生的创造力、实践力及科学研究的综合素质，符合创新型卓越工程科技人才的培养目标。