The well-known Smith–Waterman algorithm is a high-sensitivity method for local sequence alignment. Unfortunately, the Smith–Waterman algorithm has quadratic time complexity, which makes it computationally demanding for large protein databases. In this paper, we present OSWALD, a portable, fully functional and general implementation to accelerate Smith–Waterman database searches in heterogeneous platforms based on Altera’s FPGA. OSWALD exploits OpenMP multithreading and SIMD computing through SSE and AVX2 extensions on the host while taking advantage of pipeline and vectorial parallelism by way of OpenCL on the FPGAs. Performance evaluations on two different heterogeneous architectures with real amino acid datasets show that OSWALD is competitive in comparison with other top-performing Smith–Waterman implementations, attaining up to 442 GCUPS peak with the best GCUPS/watts ratio.
GotohO (1982) An improved algorithm for matching biological sequences. Journal of Molecular Biology162: 705–708.
7.
IgualFDJaraLMGómez-PérezJI. (2014) A power measurement environment for PCIe accelerators. Computer Science – Research and Development30(2): 115–124.
8.
IsaMBenkridKClaytonT. (2011) An FPGA-based parameterised and scalable optimal solutions for pairwise biological sequence analysis. In: 2011 NASA/ESA conference on adaptive hardware and systems, San Diego, CA, 6–9 June 2011, pp.344–351. New York: IEEE.
9.
HowesLMunshiA (2014) The OpenCL Specification, version 2.0. Beaverton, OR: Khronos Group.
10.
LiTIShumWTruongK (2007) 160-fold acceleration of the Smith–Waterman algorithm using a field programmable gate array (FPGA). BMC Bioinformatics8: I85.
11.
LipmanDPearsonW (1985) Rapid and sensitive protein similarity searches. Science227: 1435–1441.
12.
LiuYSchmidtB (2014) SWAPHI: Smith–Waterman protein database search on Xeon Phi coprocessors. In: IEEE 25th international conference on application-specific systems, architectures and processors, ASAP 2014, Zurich, Switzerland, 18–20 June 2014, pp.184–185. New York: IEEE.
13.
LiuYMaskellDLSchmidtB (2009) CUDASW++: optimizing Smith–Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Research Notes2(1): 1–10.
14.
LiuYSchmidtBMaskellDL (2010) CUDASW++2.0: enhanced Smith–Waterman protein database search on CUDS-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Research Notes3(1): 1–12.
15.
LiuYTranTTLauenrothF. (2014) SWAPHI-LS: Smith–Waterman algorithm on Xeon Phi coprocessors for long DNA sequences. In: 2014 IEEE international conference on cluster computing, CLUSTER 2014, Madrid, Spain, 22–26 September 2014, pp.257–265. New York: IEEE.
16.
LiuYWirawanASchmidtB (2013) CUDASW++ 3.0: accelerating Smith–Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics14(1): 1–10.
17.
QiuJEkanayakeJGunarathneT. (2010) Hybrid cloud and cluster computing paradigms for life science applications. BMC Bioinformatics11(Suppl 12): S3.
18.
ReindersJJeffersJ (2014) Power analysis on the Intel® Xeon PhiTM coprocessor. In: High Performance Parallelism Pearls, Volume 1: Multicore and Many-Core Programming Approaches. Boston: Morgan Kaufmann, pp.xli–xliv.
RucciEDe GiustiANaioufM. (2014) Smith–Waterman algorithm on heterogeneous systems: a case study. In: 2014 IEEE international conference on cluster computing (CLUSTER), Madrid, 22–26 September 2014, pp.323–330, New York: IEEE.
21.
RucciEGarciaCBotellaG. (2015a) Smith–Waterman protein search with OpenCL on an FPGA. In: Trustcom/BigDataSE/ISPA, 2015 IEEE, Helsinki, 20–22 August 2015vol. 3. pp.208–213.
22.
RucciEGarcíaCBotellaG.. (2015b) An energy-aware performance analysis of SWIMM: Smith–Waterman implementation on Intel’s Multicore and Manycore architectures. Concurrency and Computation: Practice and Experience27(18): 5517–5537.
23.
SettleSO (2014) High-performance dynamic programming on FPGAS with OpenCL. In: IEEE High Performance Extreme Computing Conference, Waltham, MA, 10–12 September 2013, pp. 1–6. New York: IEEE.
24.
SmithTFWatermanMS (1981) Identification of common molecular subsequences. Journal of Molecular Biology147(1): 195–197.
25.
WeaverNMarkovskiyYPatelY. (2003) Post-placement C-slow retiming for the xilinx virtex FPGA. In: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on field programmable gate arrays, Monterey, CA, 23–25 February 2003, pp.185–194. New York, NY, USA: ACM.
26.
YamaguchiYTsoiHLukW (2011) FPGA-based Smith–Waterman algorithm: analysis and novel design. In: KochAKrishnamurthyRMcAllisterJetal. (eds.) Reconfigurable Computing: Architectures, Tools and Applications, Lecture Notes in Computer Science, volume 6578. Berlin: Springer, pp.181–192.
