A Fast Hardware Implementation of STON Algorithm for Comparing 3-D Structure of Proteins in FPGA

A Fast Hardware Implementation of STON Algorithm for Comparing 3-D Structure of Proteins in FPGA

Abstract

Protein is an important molecule that performs a wide scope of functions in biological systems. Protein structures change little during evolution and structural comparison provides more accurate information about the evolution history. Therefore, comparing three-dimensional structure of proteins is one of the most fundamental problems in bioinformatics. In recent years, various algorithms have been proposed to solve this problem efficiently. The proposed algorithms are very time-consuming due to high complexity of these structures. In this paper, an FPGA-based hardware accelerator is proposed for the first time to speed-up the execution of a high-performance algorithm, called STON. Two classes of approaches are used to reduce the execution time of the algorithm, namely, coarse-grain and fine-grain. In the coarse-grain approach, due to the independency of for-loop cycles, parallelism is used for the iterations of these loops. In the fine-grain approach, the square root, division and trigonometry functions are performed in a fast mode. A software/hardware co-design of the algorithm was implemented based on two different Xilinx FPGA devices from Vertex family. An average speed-up of 10x is achieved compared to the software execution.

References