Bit-Parallel Computation of Local Similarity Score Matrices with Unitary Weights
Heikki Hyyrö and Gonzalo Navarro
Local similarity computation between two sequences permits detecting all
the relevant alignments present between subsequences thereof. A well-known
dynamic programming algorithm works in time O(mn), m and n
being the lengths of the subsequences. The algorithm is rather slow when
applied over many sequence pairs. In this paper we present the first
bit-parallel computation of the score matrix, for a simplified choice of scores.
If the computer word has w bits,
then the resulting algorithm works in O(mn\log\min(m,n,w)/w) time,
achieving up to 8-fold speedups in practice. Some DNA comparison applications
use precisely the simplified scores we handle, and thus our algorithm is
directly applicable. In others, our method can be used as a raw filter to
discard most of the strings, so the classical algorithm can be focused only on
the substring pairs that can yield relevant results.