Abstract:
Multiple Sequence Alignment (MSA), which has been an active research area for a long time, is a computational task that is used in the field of bioinformatics. MSA for proteins involves the process of aligning three or more amino acid sequences. The outputs of this task provide further information for other areas in bioinformatics such as homology searches, phylogenetic analysis and protein structure prediction. The al gorithmic solutions for MSA can mainly be split into three groups: Direct approach, progressive approaches and iterative approaches. H4MSA is one of the iterative ap proaches in the literature, that uses multi-objective optimization and a type of genetic algorithm (GA) to solve the MSA problem. In this work, a hardware acceleration is proposed for the MSA tasks and H4MSA is selected as the test algorithm. The acceleration is accomplished by designing a hardware block for the evaluation of weighted sum of pairs score (WSPS), which is a commonly used scoring function in MSA applications and also used as an objective function in the H4MSA algorithm. The entire application is built in a CYCLONE V SOC device, where the hardware is implemented in the FPGA fabric and the test algorithm is run on the CPU core of the device. For testing the design, 12 different sequence sets from a well-known database are used, and the results show that the accelerated version of the algorithm achieves speedups of 1.7x to 20x over the CPU version.
