Computing the Fourier transform of a q-ary function $f:\mathbb{Z}_q^n \to {\mathbb{R}}$, which maps q-ary sequences to real numbers, is an important problem in mathematics with wide-ranging applications in biology, signal processing, and machine learning. Previous studies have shown that, under the sparsity assumption, the Fourier transform can be computed efficiently using fast and sample-efficient algorithms. However, in most practical settings, the function is defined over a more general space—the space of generalized q-ary sequences ${\mathbb{Z}_{{q_1}}} \times {\mathbb{Z}_{{q_2}}} \times \cdots \times {\mathbb{Z}_{{q_n}}}$ — where each ${\mathbb{Z}_{{q_i}}}$ corresponds to integers modulo qi. Herein, we develop GFast, a coding theoretic algorithm that computes the S-sparse Fourier transform of f with a sample complexity of O(Sn), computational complexity of O(SnlogN), and a failure probability that approaches zero as $N = \prod\nolimits_{i = 1}^n {{q_i}} \to \infty $ with S = Nδfor some 0 ≤ δ2) and computational complexity of O(Sn2logN) under the same high probability guarantees. Additionally, we demonstrate that GFast computes the sparse Fourier transform of generalized q-ary functions 8× faster using 16× fewer samples on synthetic experiments, and enables explaining real-world heart disease diagnosis and protein fitness models using up to 13× fewer samples compared to existing Fourier algorithms applied to the most efficient parameterization of the models as q-ary functions.

The growing adoption of machine learning models for biological sequences has intensified the need for interpretable predictions, with Shapley values emerging as a theoretically grounded standard for model explanation. While effective for local explanations of individual input sequences, scaling Shapley-based interpretability to extract global biological insights requires evaluating thousands of sequences—incurring exponential computational cost per query. We introduce SHAP zero, a novel algorithm that amortizes the cost of Shapley value computation across large-scale biological datasets. After a one-time model sketching step, SHAP zero enables near-zero marginal cost for future queries by uncovering an underexplored connection between Shapley values, high-order feature interactions, and the sparse Fourier transform of the model. Applied to models of guide RNA efficacy, DNA repair outcomes, and protein fitness, SHAP zero explains predictions orders of magnitude faster than existing methods, recovering rich combinatorial interactions previously inaccessible at scale. This work opens the door to principled, efficient, and scalable interpretability for black-box sequence models in biology.

Autoregressive models have transformed protein engineering by enabling the generation of novel protein sequences beyond those found in nature. However, their sequential inference introduces significant latency, limiting their utility in high-throughput protein screening. Speculative decoding accelerates generation by employing a lightweight draft model to sample tokens, which a larger target model then verifies and refines. Yet in protein sequence generation, draft models are typically agnostic to the structural and functional constraints of the target protein, leading to biologically implausible outputs and a shift in the likelihood distribution of generated sequences. We introduce SpecMER (Speculative Decoding via k-mer Guidance), a novel framework that incorporates biological, structural, and functional priors using k-mer motifs extracted from multiple sequence alignments. By scoring candidate sequences in parallel and selecting those most consistent with known biological patterns, SpecMER significantly improves sequence plausibility while retaining the efficiency of speculative decoding. SpecMER achieves 24–32% speedup over standard autoregressive decoding, along with higher acceptance rates and improved sequence likelihoods.