title: Graphics processing unit-based alignment of protein interaction networks.
abstract: Network alignment is an important bridge to understanding human protein-protein interactions (PPIs) and functions through model organisms. However, the underlying subgraph isomorphism problem complicates and increases the time required to align protein interaction networks (PINs). Parallel computing technology is an effective solution to the challenge of aligning large-scale networks via sequential computing. In this study, the typical Hungarian-Greedy Algorithm (HGA) is used as an example for PIN alignment. The authors propose a HGA with 2-nearest neighbours (HGA-2N) and implement its graphics processing unit (GPU) acceleration. Numerical experiments demonstrate that HGA-2N can find alignments that are close to those found by HGA while dramatically reducing computing time. The GPU implementation of HGA-2N optimises the parallel pattern, computing mode and storage mode and it improves the computing time ratio between the CPU and GPU compared with HGA when large-scale networks are considered. By using HGA-2N in GPUs, conserved PPIs can be observed, and potential PPIs can be predicted. Among the predictions based on 25 common Gene Ontology terms, 42.8% can be found in the Human Protein Reference Database. Furthermore, a new method of reconstructing phylogenetic trees is introduced, which shows the same relationships among five herpes viruses that are obtained using other methods.
authors.affiliation: School of Computer Engineering and Science, Shanghai University, Shanghai, People's Republic of China. jiangx@shu.edu.cn.
authors.forename: Jiang
authors.initials: J
authors.lastname: Xie
authors.affiliation: School of Computer Engineering and Science, Shanghai University, Shanghai, People's Republic of China.
authors.forename: Zhonghua
authors.initials: Z
authors.lastname: Zhou
authors.affiliation: School of Computer Engineering and Science, Shanghai University, Shanghai, People's Republic of China.
authors.forename: Jin
authors.initials: J
authors.lastname: Ma
authors.affiliation: School of Computer Engineering and Science, Shanghai University, Shanghai, People's Republic of China.
authors.forename: Chaojuan
authors.initials: C
authors.lastname: Xiang
authors.affiliation: Department of Mathematics, Center for Mathematical and Computational Biology, University of California at Irvine, California, USA.
authors.forename: Qing
authors.initials: Q
authors.lastname: Nie
authors.affiliation: School of Computer Engineering and Science, Shanghai University, Shanghai, People's Republic of China.
authors.forename: Wu
authors.initials: W
authors.lastname: Zhang
mesh_terms: D003196:Computer Graphics / Q000295:instrumentation*; D003198:Computer Simulation; D004867:Equipment Design; D019544:Equipment Failure Analysis; D000069550:Machine Learning; D008954:Models, Biological; D010363:Pattern Recognition, Automated / Q000379:methods*; D025941:Protein Interaction Mapping / Q000379:methods*; D020543:Proteome / Q000378:metabolism*; D012815:Signal Processing, Computer-Assisted / Q000295:instrumentation*; D015398:Signal Transduction / Q000502:physiology*
chemical_list: D020543:Proteome