Design Of Algorithm Accelerator For Biological Molecule Structure Prediction

The structure prediction of biological macromolecules is an important research area in bioinformatics with significant theoretical and practical values. With the continuous development of gene sequencing technology, the size of RNA and protein sequence databases are expanding rapidly. The existing structure determination technology can not meet the growing demand of the development of sequence databases, therefor, the prediction of biological macromolecules based on the sequence information becomes a promising method in bioinformatics. The support demand from the high-performance computing for predicting the spatial structure of biological macromolecules is becoming very urgent because of high computational complexity and increasing demand of processing abilities. Recently the design of algorithm accelerator based on FPGA (Field Programmable Gate Arrays) is becoming one important direction in high-performance computing, which can adapt to diverse bioinformatics algorithms. The research of accelerating algorithm on FPGA chips has very comprehensive prospects in bioinformatics applications.We implemented the accelerator design and research by choosing typical structure prediction algorithm in the field of bioinformatics. For the RNA secondary structure prediction, we selected an algorithm with high complexity both in time and space which can predict pseudoknot, a very common and important substructure in RNA secondary structure. In the accelerator design, several strategies such as abstraction and parallelism of computing pipeline, data reuse, optimized chip data loading, and the compressive storage of parameter values have been used, which result in a speedup more than 5x over the original software. For prediction of the protein structure, a classical secondary structure prediction algorithm was selected to be implemented on FPGA. We proposed a strategy for parallel parameters query with multiple access ports. The whole computing process is pipelined to achieve parallel processing of multiple sequences. Besides, we have done some optimization on general multi-core platforms and compared the performance with our FPGA accelerator. At last, we have designed a multi-level parallel search tree for the prediction of tertiary protein structure based on HP-lattice model, which is a first design step for the tertiary structure prediction.