Skip to main content


Integer-scoring global sequence alignment algorithm

Trainee Achievements

Integer-scoring global sequence alignment algorithm

IGERT trainees Joshua Loving and Yozen Hernandez have developed the first general integer-scoring global sequence alignment algorithm based on bit-parallelism, which exploits the inherent parallelism in computer logic calculations. 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. Integer-scoring schemes, which are widely used, assign integer weights for match, mismatch, and insertion/deletion or indel. The method depends on structural properties of the relationship between adjacent scores in the scoring matrix and they utilize these properties to construct a class of efficient algorithms, each designed for a particular set of weights. This work has been accepted to the Combinatorial Pattern Matching 2013 conference to be held in July 2013.