#28 · Tools & infrastructure

Lossless k-mer compression and GPU phylogenetics cut memory and runtime at scale

The dominant thread is engineering for scale in sequence analysis: reducing memory footprint and runtime through data representation and algorithm design rather than new biological models. kmcomp applies lossless block compression with O(1) row access and TSP-based column reordering, reported to halve Logan-Search petabyte index storage. DIPPER uses GPU divide-and-conquer with on-the-fly distances to reach O(N log N) time and O(N) memory for inputs numbering in the millions. FILTR, a DSL and compiler, separates dynamic-programming recurrence rules from pruning and scheduling and emits C++, addressing a related but distinct concern of code generation. What is new across these items is the decoupling of specification from optimization, with explicit complexity bounds and random row access treated as design targets.