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

doi:10.11772/j.issn.1001-9081.2014.11.3117

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (11): 3117-3120.DOI: 10.11772/j.issn.1001-9081.2014.11.3117

Previous Articles Next Articles

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

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

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

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

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

Abstract

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.

摘要：

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

CLC Number:

TP391
TP311

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.

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

References

[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]	. Pavement defect detection algorithm with enhanced morphological perception [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	YANG Jianfeng, CHEN Bin, LI Yuxuan. Self-supervised point cloud anomaly detection method based on point cloud reconstruction [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	XUE Zhenhua, LI Qiang, HUANG Chao. Vision foundation model-driven pixel-level image anomaly detection model [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Binocular vision object location algorithm for robot arm grasping [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	. Multi-attention contrastive learning for infrared small target detection [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	LI Zhonghua, ZHONG Gengxin, FAN Ping, ZHU Hengliang. Camouflaged object detection by boundary mining and background guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Multi-view difficult airway recognition based on discriminant region guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Privacy preserving localization of surveillance images based on large vision models [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Gravity data denoising method based on multilevel wavelet residual network#br# #br# [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Data augmentation method for abnormal passenger behavior in elevators based on dynamic graph convolutional network [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Text-based person retrieval method based on multi-granularity shared semantic center association [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	ZHANG Qing, YANG Fan, FANG Yuhan. Chinese Spelling Correction Algorithm Based on Multi-Modal Information Fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	WANG Hao, WANG Jinwei, CHENG Xin, ZHANG Jiawei, WU Hao, LUO Xiangyang, MA Bin. A Review of JPEG Recompression Forensics for Color Images [J]. Journal of Computer Applications, 0, (): 0-0.
[14]	. Distribution adaptation and dynamic curriculum pseudo-labeling framework for semi-supervised fire detection [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	. Multimodal harmful content detection method based on weakly supervised modality semantic enhancement [J]. Journal of Computer Applications, 0, (): 0-0.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics