Research On Parallelized RNA Secondary Structure Prediction Algorithm On FPGA Platform

With the growing of Bioinformatics, processing and analyzing abilityof bioinformatics data is increasingly demanded. Although algorithms inBioinformatics are relatively not very complicated, the data amount isreally mass, and the core computation usually repeats many times. Somuch parallelism lies in them and can be developed. RNA secondarystructure prediction is just one of such problems. With the growing amountof RNA sequences, existing software solutions on the generalized platformthat limited by the O(n3) complexity are not capable to meet theperformance demand. Therefore, using high performance computingtechnology to solve RNA folding problem is a must. Nowadays,heterogeneous computing on FPGA accelerating platform is an importantresearch area in HPC, so developing parallelism of RNA secondarystructure prediction algorithms on heterogeneous computing platform andthen trying to accelerate it is a hot research area.This thesis first makes a comprehensive discussion and summarize ofthe background and current research situation of RNA secondary structureprediction. Then, focus on the most typical and basic based on MFEmethod, the Nussinov algorithm, makes a deep analysis of its datadependencies, and propose two accelerating architectures based onintra-grid parallelism and inter-grid parallelism respectively. Besides that,we propose a balanced memory structure, which could achieve bettermemory efficiency at long RNA sequences. We implement the twoaccelerator architectures on Xilinx ML605FPGA high performancecomputing platform. We verify the correctness of our accelerating algorithm, and which can achieve a p-times speedup at a p-wayparallelized configuration.