Myers Bit-Parallel Algorithm for Edit Distance

The Myers bit-parallel algorithm accelerates edit distance and approximate sequence alignment calculations by exploiting word-level parallelism inherent in modern computer processors. By translating the incremental differences of dynamic programming matrices into compact bit vectors, the algorithm computes entire columns of the alignment grid using single-cycle bitwise and arithmetic operations. This technique reduces the classic Levenshtein distance time complexity from \(O(nm)\) to \(O(nm/w)\), where \(n\) and \(m\) are sequence lengths and \(w\) is the computer word size (typically 64 bits), yielding substantial speedups for high-throughput bioinformatics and text searching applications.

The Dynamic Programming Bottleneck

Standard sequence alignment relies on dynamic programming (DP), building an \((n+1) \times (m+1)\) matrix \(D\) where each cell \(D[i,j]\) represents the edit distance between sequence prefixes. Calculating each cell sequentially requires computing minimums across insertions, deletions, and substitutions:

\[D[i,j] = \min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + \text{cost})\]

Because each cell directly depends on its left, top, and top-left neighbors, traditional processors must evaluate these calculations one element at a time, resulting in \(O(nm)\) computational steps and significant CPU cache usage.

The Adjacent Delta Property

Gene Myers recognized that full integer matrices contain redundant data. In an edit distance matrix, adjacent cells differ by at most one unit:

Because the change between adjacent cells is constrained to three states, these differences can be encoded into binary states rather than multi-byte integers.

Encoding Matrix Deltas into Bit Vectors

Myers represents an entire column of the DP table using bit vectors, where individual bit positions correspond to row indices:

If neither the positive nor negative bit is set at index \(i\), the delta is zero. Storing deltas this way fits 64 consecutive rows of the alignment matrix directly into a single 64-bit CPU register.

Binary Arithmetic and Carry Propagation

The core breakthrough of the Myers algorithm is using standard binary addition to simulate score propagation across cells:

  1. Character Matching: A bitwise AND between the pattern mask for the incoming target character and the current vector identifies match opportunities.
  2. Carry-Based Propagation: The addition of binary vectors causes carry bits to ripple from lower-order bits to higher-order bits. This natural hardware mechanism matches how diagonal substitutions and vertical deletions propagate scores down a DP column.
  3. State Transition Logic: A series of logical operators (AND, OR, XOR, NOT) and bitwise shifts update \(VP\), \(VN\), \(HP\), and \(HN\) in parallel.

Because binary addition ripples through a 64-bit integer within a single CPU cycle, the processor resolves 64 dynamic programming subproblems simultaneously.

Primary Drivers of Performance Acceleration