Parallel alignment algorithm of large scale biological networks based on message passing interface
SHU Junhui1,ZHANG Wu1,2,XUE Qianfei1,XIE Jiang2,3
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
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.
[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.
2014, Vol. 34 
