A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm

Abstract. Mapping of next-generation sequencing data and other pro-cessor-intensive sequence comparison applications have motivated a con-tinued search for high efficiency sequence alignment algorithms. In one approach, which exploits the inherent parallelism in computer logic cal-culations, individual cells in an alignment scoring matrix are represented as bits in a computer word and the calculation of scores is emulated by a series of bit operations comprised of AND, OR, XOR, complement, shift, and addition. Bit-parallelism has been successfully applied to the Longest Common Subsequence (LCS) and edit-distance problems, pro-ducing solutions which are significantly faster than standard implementa-tions. But, the intensive mental effort required to produce these solutions, which are closely tied to special properties of the problems, has limited efforts to extend bit-parallelism to more general scoring schemes. In this paper, we give the first bit-parallel solution for general, integer-scoring global alignment. Integer-scoring schemes, which are widely used, assign integer weights for match, mismatch, and insertion/deletion or indel. Our method depends on structural properties of the relationship between adjacent scores in the scoring matrix. We utilize these properties to construct a class of efficient algorithms, each designed for a particular set of weights, and we introduce a standard for characterizing the effi-ciency in terms of the average number of bit-operations per cell of the original scoring matrix