生物复杂网络motif发现的并行算法
发布时间：2021-10-22 06:36
生物复杂网络motif发现是一种研究生物网络的重要方法,它基于复杂网络的理论研究,以新的视角来研究生命现象和生命机制,但是在处理较大的网络规模或者需挖掘较大的motif时计算效率低。针对这个问题,在现有串行网络motif发现算法ESU的基础上,提出一种基于消息传递接口（MPI）的并行化ESU算法。该方法在ESU计算过程中优化了节点值以解决节点值依赖问题,并以ESU算法的子图发现策略统计各节点子图数,利用动态规划策略寻找最佳节点分配策略以解决负载不均衡问题。模拟网络数据和真实生物网络数据的实验结果表明,并行化ESU算法优化了节点值依赖问题,实现了基于动态规划的负载均衡策略,其运行时间比串行算法缩短了90%,并且该并行算法对不同类型不同规模的网络都具有较强的适用性,有效地提高了网络motif发现问题的计算效率。
【文章来源】：计算机应用. 2019,39(01)北大核心CSCD
【文章页数】：6 页
【部分图文】：
ESU算法示意图Fig．1SchematicdiagramofESUalgorithm
馐?条件下的测试结果进行描述，测试条件为酵母菌蛋白质网络的motif大小为6，并行核数为8，测试结果如图4所描述。图4中，节点分配策略是在不计算子图数的前提下进行节点分配，子图分配策略是指计算子图数，根据子图数对节点分配，子图动态规划则为本文提出的节点分配策略，旨在计算出子图数后，根据子图数动态规划节点与进程号之间的关系。从图中可以得出，使用基于动态规划的节点分配策略明显优于不使用动态规划的节点分配策略，而且各个进程所计算的时间基本相当，满足了负载均衡的要求。图43种节点分配策略的各个进程计算时间Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均节点度的模拟网络的实验结果在这个实验中，本文对前文提到的3类网络模型进行测试，分别是无标度网络模型、小世界网络模型和规则网络模型，每种网络模型都使用motif大小固定为4的并行ESU算法来测试并行性能，测试结果取10个网络结果的平均值，3类网络模型的测试结果如图5所示。图5(a)、(b)、(c)描述了平均节点度为5、10和15的三种模拟网络，分别是无标度网络、小世界网络和规则网络使用并行化ESU算法的并行性能，分析图5的实验结果，网络的平均节点度的变化对并行化ESU的加速比几乎不影响，3种不同平均节点度的网络的加速比曲线几乎重合，而且各种不同类型的网络之间的加速比变化也很小，加速比曲线几乎接近线性关系。结果表明，本文的并行化ESU算法适用于各种不同类型不同稀疏程度的网络。3．3．4生物网络的实验结果生物网络是一种同时具有无标度和小世界特性的复杂网络［18
用动态规划的节点分配策略，而且各个进程所计算的时间基本相当，满足了负载均衡的要求。图43种节点分配策略的各个进程计算时间Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均节点度的模拟网络的实验结果在这个实验中，本文对前文提到的3类网络模型进行测试，分别是无标度网络模型、小世界网络模型和规则网络模型，每种网络模型都使用motif大小固定为4的并行ESU算法来测试并行性能，测试结果取10个网络结果的平均值，3类网络模型的测试结果如图5所示。图5(a)、(b)、(c)描述了平均节点度为5、10和15的三种模拟网络，分别是无标度网络、小世界网络和规则网络使用并行化ESU算法的并行性能，分析图5的实验结果，网络的平均节点度的变化对并行化ESU的加速比几乎不影响，3种不同平均节点度的网络的加速比曲线几乎重合，而且各种不同类型的网络之间的加速比变化也很小，加速比曲线几乎接近线性关系。结果表明，本文的并行化ESU算法适用于各种不同类型不同稀疏程度的网络。3．3．4生物网络的实验结果生物网络是一种同时具有无标度和小世界特性的复杂网络［18］，同时生物网络也是稀疏网络的一种。在前一节，本文的并行算法在各类模拟网络上表现良好。为了验证本文的并行算法在真实生物网络上是否同样表现良好，本文对前文提到的3类不同节点数不同边数的真实生物网络进行测试，测试使用的motif大小为6，每个生物网络均进行了10次测试，测试结果取其平均值以降低误差，测试结果如表3和图6所示。图5各种不同条件的模拟网络的并行性能Fig．5Pa
【参考文献】：
期刊论文
[1]HashESU:一种生物网络模体识别高效方法[J]. 赵静,钟诚. 小型微型计算机系统. 2015(09)
[2]生物网络模体发现算法研究综述[J]. 覃桂敏,高琳,呼加璐. 电子学报. 2009(10)
本文编号：3450569
【文章来源】：计算机应用. 2019,39(01)北大核心CSCD
【文章页数】：6 页
【部分图文】：
ESU算法示意图Fig．1SchematicdiagramofESUalgorithm
馐?条件下的测试结果进行描述，测试条件为酵母菌蛋白质网络的motif大小为6，并行核数为8，测试结果如图4所描述。图4中，节点分配策略是在不计算子图数的前提下进行节点分配，子图分配策略是指计算子图数，根据子图数对节点分配，子图动态规划则为本文提出的节点分配策略，旨在计算出子图数后，根据子图数动态规划节点与进程号之间的关系。从图中可以得出，使用基于动态规划的节点分配策略明显优于不使用动态规划的节点分配策略，而且各个进程所计算的时间基本相当，满足了负载均衡的要求。图43种节点分配策略的各个进程计算时间Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均节点度的模拟网络的实验结果在这个实验中，本文对前文提到的3类网络模型进行测试，分别是无标度网络模型、小世界网络模型和规则网络模型，每种网络模型都使用motif大小固定为4的并行ESU算法来测试并行性能，测试结果取10个网络结果的平均值，3类网络模型的测试结果如图5所示。图5(a)、(b)、(c)描述了平均节点度为5、10和15的三种模拟网络，分别是无标度网络、小世界网络和规则网络使用并行化ESU算法的并行性能，分析图5的实验结果，网络的平均节点度的变化对并行化ESU的加速比几乎不影响，3种不同平均节点度的网络的加速比曲线几乎重合，而且各种不同类型的网络之间的加速比变化也很小，加速比曲线几乎接近线性关系。结果表明，本文的并行化ESU算法适用于各种不同类型不同稀疏程度的网络。3．3．4生物网络的实验结果生物网络是一种同时具有无标度和小世界特性的复杂网络［18
用动态规划的节点分配策略，而且各个进程所计算的时间基本相当，满足了负载均衡的要求。图43种节点分配策略的各个进程计算时间Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均节点度的模拟网络的实验结果在这个实验中，本文对前文提到的3类网络模型进行测试，分别是无标度网络模型、小世界网络模型和规则网络模型，每种网络模型都使用motif大小固定为4的并行ESU算法来测试并行性能，测试结果取10个网络结果的平均值，3类网络模型的测试结果如图5所示。图5(a)、(b)、(c)描述了平均节点度为5、10和15的三种模拟网络，分别是无标度网络、小世界网络和规则网络使用并行化ESU算法的并行性能，分析图5的实验结果，网络的平均节点度的变化对并行化ESU的加速比几乎不影响，3种不同平均节点度的网络的加速比曲线几乎重合，而且各种不同类型的网络之间的加速比变化也很小，加速比曲线几乎接近线性关系。结果表明，本文的并行化ESU算法适用于各种不同类型不同稀疏程度的网络。3．3．4生物网络的实验结果生物网络是一种同时具有无标度和小世界特性的复杂网络［18］，同时生物网络也是稀疏网络的一种。在前一节，本文的并行算法在各类模拟网络上表现良好。为了验证本文的并行算法在真实生物网络上是否同样表现良好，本文对前文提到的3类不同节点数不同边数的真实生物网络进行测试，测试使用的motif大小为6，每个生物网络均进行了10次测试，测试结果取其平均值以降低误差，测试结果如表3和图6所示。图5各种不同条件的模拟网络的并行性能Fig．5Pa
【参考文献】：
期刊论文
[1]HashESU:一种生物网络模体识别高效方法[J]. 赵静,钟诚. 小型微型计算机系统. 2015(09)
[2]生物网络模体发现算法研究综述[J]. 覃桂敏,高琳,呼加璐. 电子学报. 2009(10)
本文编号：3450569
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3450569.html
