Parallel algorithms for large-scale biological sequence alignment on Xeon-Phi based clusters

BMC Bioinformatics

Research

Bertil Schmidt¹  Kai Xu²  Haidong Lan²  Yuandong Chan²  Weiguo Liu²  Shaoliang Peng³ 

[1] Johannes Gutenberg University, Mainz, Germany;School of Computer Science and Technology, Shandong University, Shunhua Road 1500, Jinan, Shandong, China;School of Computer Science, National University of Defense Technology, Changsha, Hunan, China;

关键词: Smith-Waterman;    Dynamic programming;    Pairwise sequence alignment;    Multiple sequence alignment;    Xeon Phi clusters;   

DOI  :  10.1186/s12859-016-1128-0

来源: Springer

【 摘 要 】

BackgroundComputing alignments between two or more sequences are common operations frequently performed in computational molecular biology. The continuing growth of biological sequence databases establishes the need for their efficient parallel implementation on modern accelerators.ResultsThis paper presents new approaches to high performance biological sequence database scanning with the Smith-Waterman algorithm and the first stage of progressive multiple sequence alignment based on the ClustalW heuristic on a Xeon Phi-based compute cluster. Our approach uses a three-level parallelization scheme to take full advantage of the compute power available on this type of architecture; i.e. cluster-level data parallelism, thread-level coarse-grained parallelism, and vector-level fine-grained parallelism. Furthermore, we re-organize the sequence datasets and use Xeon Phi shuffle operations to improve I/O efficiency.ConclusionsEvaluations show that our method achieves a peak overall performance up to 220 GCUPS for scanning real protein sequence databanks on a single node consisting of two Intel E5-2620 CPUs and two Intel Xeon Phi 7110P cards. It also exhibits good scalability in terms of sequence length and size, and number of compute nodes for both database scanning and multiple sequence alignment. Furthermore, the achieved performance is highly competitive in comparison to optimized Xeon Phi and GPU implementations. Our implementation is available at https://github.com/turbo0628/LSDBS-mpi.

【 授权许可】

CC BY   
© The Author(s) 2016