资 源 简 介
生物复杂网络motif发现是一种研究生物网络的重要方法，它基于复杂网络的理论研究，以新的视角来研究生命现象和生命机制，但是在处理较大的网络规模或者需挖掘较大的moTIf时计算效率低。针对这个问题，在现有串行网络moTIf发现算法ESU的基础上，提出一种基于消息传递接口（MPI）的并行化ESU算法。该方法在ESU计算过程中优化了节点值以解决节点值依赖问题，并以ESU算法的子图发现策略统计各节点子图数，利用动态规划策略寻找最佳节点分配策略以解决负载不均衡问题。模拟网络数据和真实生物网络数据的实验结果表明，并行化ESU算法优化了节点值依赖问题，实现了基于动态规划的负载均衡策略，其运行时间比串行算法缩短了90%，并且该并行算法对不同类型不同规模的网络都具有较强的适用性，有效地提高了网络moTIf发现问题的计算效率。
生物网络比对对网络医学和物种演化等领域的发展有着重大的意义”，其中，一项很重要的研究就是生物网络moTIf发现。生物网络motif发现是指在生物网络中寻找所有特定大小、拓扑结构一致的子图 ，它包括在生物网络中枚举子图和计算子图之间的同构关系等问题。生物网络motif是生物网络的基本单元，它所表现的局部性质与网络的构成机制密切相关，对它的研究可以加深对生物网络的结构和功能的理解，有助于揭示很多重要的生物学问题;然而精确识别网络motif 是-个计算复杂度很高的问题，每-一个枚举的子图都需要执行同构比较，而子图之间同构关系的计算-直是NP（ Non-deterministic Polynomial）难问题，无法通过改进算法来降低其时间复杂度。随着生物网络研究的规模和motif的大小不断增大，参与枚举和同构比较的子图数呈指数级别的增长，其计算量越来越大，给网络motif的发现带来了挑战。
