Junjie Li’s paper wins the best paper award at the 6th International Conference on Bioinformatics and Computational Biology (BICoB) in Las Vegas. “Optimal Alignment of Three Sequences on a GPU” is co-authored by CISE faculty Sanjay Ranka, Ph.D., and Sartaj Sahni, Ph.D.
Graphics Processing Units (GPUs) were developed originally to meet the computational needs of algorithms for rendering computer graphics. The rapid and enormous growth in sophistication of graphics applications, such as computer games, has resulted in the availability of GPUs that have hundreds of processors and peak performance near a teraflop that sell for up to a few thousand dollars. Although GPUs are optimized for graphics calculations, their low cost per gigaflop has motivated significant research into their efficient use for bioinformatics applications. In this paper, two novel parallel algorithms – LAYERED and SLOPED – are developed to optimally align three gene sequences on a GPA with CUDA support. Experiments conducted using an Nvidia Tesla C2050 GPU show that the SLOPED algorithm delivers a speedup of up to 90 relative to the single core algorithm running on the host CPU when determining the score of the best alignment. This work explored and confirmed the possibility of using GPUs as acceleration devices to speedup bioinformatics applications. The parallelization strategy used in this work can be generalized to solve other dynamic programming problems that have similar computation patterns as well.