Bit-parallel alignment with substitution scoring

Large sequence data sets generated by high-throughput biology experiments have motivated development of more efficient sequence comparison algorithms. Bit-parallel alignment offers one approach to dealing with these large data sets. Bit-parallel alignment algorithms use bits in computer words to represent alignment scores within a single row of the alignment scoring matrix and use logic operations and addition to compute the scores in the next row. Recently, we developed BitPAl, a very fast, general method for bit-parallel global alignment when there is a single match and mismatch value. In this paper we address global alignment using substitution scoring, such as BLOSUM substitution scoring commonly used for protein sequences or transition-transversion scoring used for DNA sequences. Substitution scoring assigns a potentially different substitution weight to every pair of alphabet characters. We present a new approach based on partial sums of adjacent score differences. It runs in time O(mn log W/W ) where W is the number of values that are stored in a computer word (in our implementation, w/8 where w is the length of a computer word). Except for a pre-processing step, the running time does not depend on the substitution weights. In experiments reported here, our algorithm is over eight times faster than standard iterative dynamic programming and 30% faster than an accelerated SIMD version of dynamic programming.