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

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-12-01 出版日期:2014-11-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-12-01 Published:2014-11-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]	杨建锋陈斌李雨轩. 基于点云重构的自监督点云异常检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	薛振华李强黄超. 视觉大模型驱动的像素级图像异常检测模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	蒋畅江向杰何旭颖. 面向机械臂抓取的双目视觉目标定位算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	边小勇胡其仁袁培洋. 多注意力对比学习的红外小目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	李钟华钟庚辛范萍朱恒亮. 通过边界挖掘和背景引导的伪装目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	吴松霖张广朝姚远彭博. 基于判别区域引导的多视图困难气道识别[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	李强白少雄熊源袁薇. 基于视觉大模型隐私保护的监控图像定位[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	薛雅丽徐忠敏刘世豪. 基于多级小波残差网络的重力数据去噪方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	况世雄姚俊波陆佳炜王琪冰肖刚. 基于动态图卷积网络的电梯乘客异常行为数据增强方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	康斌陈斌王俊杰李昱林赵军智咸伟志. 基于多粒度共享语义中心关联的文本到人物检索方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	张庆杨凡方宇涵. 基于多模态信息融合的中文拼写纠错算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	王昊王金伟程鑫张家伟吴昊罗向阳马宾. 彩色图像JPEG重压缩取证综述[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