An Efficient Parallel Algorithm for Longest Common Subsequence Problem on GPUs

Abstract

Sequence alignment is an important problem in computational biology and finding the longest common subsequence (LCS) of multiple bi- ological sequences is an essential and effective tech- nique in sequence alignment. A major computational approach for solving the LCS problem is dynamic pro- gramming. Several dynamic programming methods have been proposed to have reduced time and space complexity. As databases of biological sequences be- come larger, parallel algorithms become increasingly important to tackle large size problems. In the mean- time, general-purpose computing on graphics process- ing units (GPGPU) has emerged as a promising tech- nology for cost-effective high performance computing. In this paper, we develop an efficient parallel algo- rithm on GPUs for the LCS problem. We propose a new technique that changes the data dependency in the score table used by dynamic programming algo- rithms to enable higher degrees of parallelism. The algorithm takes advantage of the large number of pro- cessing units and the unique memory-accessing prop- erties of GPUs to achieve high performance. The al- gorithm was implemented on Nvidia 9800GT GPUs and tested on randomly generated sequences of dif- ferent lengths. The experiment results show that the new algorithm is about 6 times faster on GPUs than on typical CPUs and is 3 times faster than an exist- ing efficient parallel algorithm, the diagonal parallel algorithm.