GPU Accelerated Biological Sequence Alignment

To improve the biological sequence alignment in accuracy and efficiency,a GPU accelerated Smith-Waterman algorithm is proposed.The algorithm uses diamond-shaped data layout to fully utilize the parallel processing capability of commodity GPUs.With a batched query technique,biological sequences with hundreds of millions units can be processed.The maximum match score computation is optimized with tree-based reduction.The algorithm has been implemented on an NVIDIA GeForce GTX 285 GPU,and tested with multiple sequences under various length.Experiment results show that,in comparison with the CPU based serial algorithms,the proposed algorithm improves the overall performance up to 120 times.