title: Parallel algorithms for large-scale biological sequence alignment on Xeon-Phi based clusters.
abstract: BACKGROUND
  Computing 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.
  
  
  RESULTS
  This 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.
  
  
  CONCLUSIONS
  Evaluations 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 .
authors.affiliation: School of Computer Science and Technology, Shandong University, Shunhua Road 1500, Jinan, Shandong, China.
authors.forename: Haidong
authors.initials: H
authors.lastname: Lan
authors.affiliation: School of Computer Science and Technology, Shandong University, Shunhua Road 1500, Jinan, Shandong, China.
authors.forename: Yuandong
authors.initials: Y
authors.lastname: Chan
authors.affiliation: School of Computer Science and Technology, Shandong University, Shunhua Road 1500, Jinan, Shandong, China.
authors.forename: Kai
authors.initials: K
authors.lastname: Xu
authors.affiliation: Johannes Gutenberg University, Mainz, Germany.
authors.forename: Bertil
authors.initials: B
authors.lastname: Schmidt
authors.affiliation: School of Computer Science, National University of Defense Technology, Changsha, Hunan, China.
authors.forename: Shaoliang
authors.initials: S
authors.lastname: Peng
authors.affiliation: School of Computer Science and Technology, Shandong University, Shunhua Road 1500, Jinan, Shandong, China. weiguo.liu@sdu.edu.cn.
authors.forename: Weiguo
authors.initials: W
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D030561:Databases, Nucleic Acid; D030562:Databases, Protein; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment; D012984:Software
chemical_list: D011506:Proteins
keywords: Dynamic programming; Multiple sequence alignment; Pairwise sequence alignment; Smith-Waterman; Xeon Phi clusters