基于消息传递接口的大规模生物网络比对并行化算法

doi:10.11772/j.issn.1001-9081.2014.11.3117

计算机应用 ›› 2014, Vol. 34 ›› Issue (11): 3117-3120.DOI: 10.11772/j.issn.1001-9081.2014.11.3117

• 2014年全国开放式分布与并行计算学术年会(DPCS 2014)论文 • 上一篇下一篇

基于消息传递接口的大规模生物网络比对并行化算法

束俊辉¹,张武¹,²,薛倩斐¹,谢江²,³

1. 上海大学计算机工程与科学学院,上海 200444;
2. 上海大学高性能计算中心,上海 200444
3. 上海大学计算机工程与科学学院,上海 200444

收稿日期:2014-07-22 修回日期:2014-07-30 出版日期:2014-11-01 发布日期:2014-12-01
通讯作者: 束俊辉
作者简介:束俊辉(1990-),男,上海人,硕士研究生,主要研究方向: 生物信息学、高性能计算;张武(1957-),男,江西武宁人,教授,博士, CCF会员,主要研究方向: 高性能计算、生物信息学、计算流体学;薛倩斐(1989-),女,浙江建德人,硕士研究生,主要研究方向:生物信息学、高性能计算;谢江(1971-),女,湖北恩施人,副教授,博士,CCF会员,主要研究方向: 生物信息学、高性能计算。
基金资助:
国家自然科学基金资助项目;高等学校博士学科点专项科研基金资助项目;上海市科学技术委员会重点科研项目

Parallel alignment algorithm of large scale biological networks based on message passing interface

SHU Junhui¹,ZHANG Wu¹,²,XUE Qianfei¹,XIE Jiang²,³

1. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China;
2. High Performance Computing Center, Shanghai University, Shanghai 200444, China
3. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China

Received:2014-07-22 Revised:2014-07-30 Online:2014-11-01 Published:2014-12-01
Contact: SHU Junhui
Supported by:
Project supported by the National Natural Science Foundation of China

摘要/Abstract

摘要：

为有效降低生物网络比对算法的时间复杂度,提出一种基于可扩展的蛋白质相互作用网络比对(SPINAL)算法的消息传递接口(MPI)并行化实现方法。该方法将MPI并行化思想运用在SPINAL算法中,在多核环境中采用并行排序代替算法原本的排序方式,并结合负载均衡策略合理分配任务。实验结果表明,与未使用并行排序以及负载均衡策略相比,该方法在处理大规模生物网络比对时能有效地缩短计算时间,提高运算效率,对于不同组比对数据都有较为稳定的优化保障,具有良好的可扩展性。

Abstract:

In order to reduce the time complexity of biological networks alignment, an implementation for large scale biological networks alignment based on Scalable Protein Interaction Network Alignment (SPINAL) in Message Passing Interface (MPI) program was proposed. Based on MPI, the SPINAL algorithm combined with parallelization method was applied into this approach. Instead of serial algorithm, parallel sorting algorithm was used in multi-core environment. Load balancing strategy was chosen to assign tasks reasonably. In the processing of large scale biological networks alignment, the experiment shows that, compared with the algorithm without parallelization and load balancing strategy, this proposed algorithm can reduce the runtime and improve computation efficiency effectively.

中图分类号:

TP391
TP311

束俊辉张武薛倩斐谢江. 基于消息传递接口的大规模生物网络比对并行化算法[J]. 计算机应用, 2014, 34(11): 3117-3120.

SHU Junhui ZHANG Wu XUE Qianfei XIE Jiang. Parallel alignment algorithm of large scale biological networks based on message passing interface[J]. Journal of Computer Applications, 2014, 34(11): 3117-3120.

参考文献

[1]SINGH R, XU J, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences, 2008, 105(35): 12763-12768.
[2]MEMISEVIC V, PRZULJ N. C-GRAAL: common-neighbors-based global graph alignment of biological networks[J]. Integrative Biology, 2012, 4(7): 734-743.
[3]EL-KEBIR M, HERINGA J, KLAU G W. Lagrangian relaxation applied to sparse global network alignment[C]// PRIB 2011: Proceedings of the 6th IAPR International Conference on Pattern Recognition in Bioinformatics, LNCS 7036. Berlin: Springer-Verlag, 2011: 225-236.
[4]XIE J, ZHANG S, WEN T, et al. A querying method with feedback mechanism for protein interaction network[C]// Proceedings of the 2011 First IEEE International Conference on Healthcare Informatics, Imaging and Systems Biology. Piscataway: IEEE Press, 2011: 351-358.
[5]ALADAQ A E, ERTEN C. SPINAL: scalable protein interaction network alignment [J]. Bioinformatics, 2013, 29(7): 917-924.
[6]GUO XL, GAO L, CHEN X. Models and algorithms for alignment of biological networks[J]. Journal of Software,2010,21(9):2089-2106.(郭杏莉, 高琳, 陈新. 生物网络比对的模型与算法[J].软件学报, 2010, 21(9): 2089-2106.)
[7]CHINDELEVITCH L, LIAO C S, BERGER B. Local optimization for global alignment of protein interaction networks[EB/OL]. [2013-10-10]. http://psb.stanford.edu/psb-online/proceedings/psb10/chindelevitch.pdf.
[8]KUCHAIEV O, PRSULJ N. Integrative network alignment reveals large regions of global network similarity in yeast and human[J]. Bioinformatics, 2011, 27(10): 1390-1396.
[9]ZASLAVSKIY M, BACH F, VERT J P. Global alignment of protein-protein interaction networks by graph matching methods[J]. Bioinformatics, 2009, 25(12): i259-1267.
[10]ALTSCHUL S F, GISH W, MILLER W, et al. Basic local alignment search tool[J]. Journal of Molecular Biology, 1990, 215(3): 403-410.
[11]SHI H, SCHAEFFER J. Parallel sorting by regular sampling[J]. Journal of Parallel and Distributed Computing, 1992, 14(4): 361-372.
[12]PARK D, SINGH R, BAYM M, et al. IsoBase: a database of functionally related proteins across PPI networks[J]. Nucleic Acids Research, 2011, 39(Database issue): D295-D300.

[1]	吴军欧阳艾嘉张琳. 基于影响度的统计显著序列模式挖掘算法[J]. 计算机应用, 0, (): 0-0.
[2]	张璐方春祝铭. 基于Res2Net-YOLACT和融合特征的室内跌倒检测算法[J]. 计算机应用, 0, (): 0-0.
[3]	殷雨昌王洪元陈莉冯尊登肖宇. 基于单标注样本的多损失学习与联合度量视频行人重识别[J]. 计算机应用, 0, (): 0-0.
[4]	胡军许正康刘立钟福金张清华. 融合多粒度社区信息的网络嵌入方法[J]. 计算机应用, 0, (): 0-0.
[5]	李润泽孙雪姣. 基于时间条件提取序列的数据流偏好查询[J]. 计算机应用, 0, (): 0-0.
[6]	罗圣钦陈金怡李洪均. 基于注意力机制的多尺度残差UNet实现乳腺癌灶分割[J]. 计算机应用, 0, (): 0-0.
[7]	曹一珉蔡磊高敬阳. 基于生成对抗网络的基因数据生成方法[J]. 计算机应用, 0, (): 0-0.
[8]	陈冲闫珠赵继轩何为梁华庆. 基于集合经验模态分解和长短期记忆网络的催化裂化装置NOx排放预测[J]. 计算机应用, 0, (): 0-0.
[9]	徐光柱林文杰陈莎匡婉雷帮军周军. U-Net与自适应阈值脉冲耦合神经网络相结合的眼底血管分割方法[J]. 计算机应用, 0, (): 0-0.
[10]	杨鼎康黄帅王顺利翟鹏李一丹张立华. 基于对抗生成网络和网络集成的面部表情识别方法EE-GAN[J]. 计算机应用, 0, (): 0-0.
[11]	李讷徐光柱雷帮军马国亮石勇涛. 交通道路行驶车辆车标识别算法[J]. 计算机应用, 0, (): 0-0.
[12]	孟杰王莉杨延杰廉飚. 基于多模态深度融合的虚假信息检测[J]. 计算机应用, 0, (): 0-0.
[13]	秦庭威赵鹏程秦品乐曾建朝柴锐黄永琦. 基于残差注意力机制的点云配准算法[J]. 计算机应用, 0, (): 0-0.
[14]	鲁永帅唐英杰马鑫然. 基于深度特征融合的无纺布低对比度浆丝缺陷检测方法[J]. 计算机应用, 0, (): 0-0.
[15]	王宇航周永霞吴良武. 基于高斯函数的池化算法[J]. 计算机应用, 0, (): 0-0.

基于消息传递接口的大规模生物网络比对并行化算法

Parallel alignment algorithm of large scale biological networks based on message passing interface

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics