NBEAM: How I Wrote an Ultra-Fast DNA Sequence Alignment Algorithm in JavaScript

Abstraction: Bitwise-optimized ungapped degenerate DNA sequence alignment in JavaScript

Key points:

• NBEAM (Nucleotide Bitwise Exhaustive Alignment Mapping) encodes 8 degenerate nucleotides per 32-bit integer using 4 bits each (A=1000, T=0100, G=0010, C=0001); degenerate symbols use bitwise OR (W = A|T = 1100)
• Nucleotide matching uses bitwise AND — any non-zero result is a match; allows comparing 8 positions per CPU cycle
• ArrayBuffers (Uint32Array) used for binary data; bit-shifting aggregates 8 match flags into a single byte for lookup in a 256-entry table
• Achieves 6-7x speedup over naive string comparison; 100M nucleotides at 25% match: 233ms vs 1249ms naive on 2.4GHz (2015)
• Time complexity remains O(n²) — speed gain is from constant-factor optimization via bit parallelism, not algorithmic improvement
• Full library NtSeq available on GitHub (keithwhor/NtSeq); MIT licensed; does not implement substitution matrices

Connections: Google V8 · Bioinformatics · Sequence Alignment · Bit Manipulation

Source: https://medium.com/@keithwhor/nbeam-how-i-wrote-an-ultra-fast-dna-sequence-alignment-algorithm-in-javascript-c199e936da