Aligning Against an Adversary: Equilibrium Solvers Built on the Alignment Dynamic Program

Sequence alignment scores two strings, such as a DNA read and a reference, by finding the cheapest path through a grid of matches, insertions and deletions. That answer depends on scoring parameters (substitution costs, gap penalties, per-base error assumptions) that are usually wrong in some unknown way. This is especially true for divergent proteins and for noisy long reads. We propose to treat alignment as a two-player game. One player picks a probability distribution over alignment paths. An adversary picks the worst plausible scoring from a bounded uncertainty set. The resulting equilibrium alignment hedges against misspecified scoring instead of betting on one parameter setting.

The idea is tractable because of a structural fact from game-solving research. Multiplicative-weights learning over the exponentially many paths of a sequential decision tree can be run implicitly, at the cost of one dynamic-programming pass per iteration (Kernelized Multiplicative Weights for 0/1-Polyhedral Games). Applied to the alignment grid, that pass is the ordinary forward-backward computation, and GPU alignment kernels already run it at trillions of cell updates per second. The cost of computing a robust alignment therefore reduces to one number: how many DP passes the equilibrium solver needs. That is exactly the quantity the equilibrium-search literature has learned to shrink.

Core Claim

We claim three things. First, an entropy-regularized aligner-versus-scoring-adversary game has a unique equilibrium. Second, fast first-order game solvers reach it in a few tens of forward-backward passes, where each aligner step is a Gibbs (Boltzmann) distribution over paths and each adversary step is a cheap sort. Third, decoding this equilibrium gives alignments that are more accurate than single-scoring posterior decoding when the scoring model is misspecified: divergent protein pairs and high-error reads.

The new piece is the adversary's side. When the adversary only mixes over a handful of global substitution matrices, the game collapses to a low-dimensional dual problem, and simple mixture-weight search solves it just as well. We treat that case as a baseline, not a contribution. The game machinery only earns its place when the adversary controls position-specific score perturbations under a budget. That is the natural model of uncertain base qualities or locally unreliable regions, and it gives an adversary set with as many dimensions as the read has positions.

Here is the setup. Let $\mu$ be a distribution over monotone paths $\pi$ in the alignment grid of sequences $x$ and $y$. Let $s_e$ be the nominal score of grid edge $e$. Let $\delta$ be the adversary's perturbation, drawn from a convex set $D$, for example per-read-position penalties bounded by $b$ with total budget $B$. The game is

$$\max_{\mu}\ \min_{\delta \in D}\ \mathbb{E}_{\pi\sim\mu}\Big[\sum_{e\in\pi}(s_e+\delta_e)\Big] + \tau H(\mu),$$

where $H$ is entropy and $\tau>0$ is a temperature.

For fixed $\delta$, the aligner's best response is the Gibbs distribution $\mu(\pi)\propto \exp(\sum_{e\in\pi}(s_e+\delta_e)/\tau)$. This is exactly the posterior a pair hidden Markov model (a probabilistic model that generates both sequences jointly) computes by forward-backward. In game-theoretic terms, this posterior is a quantal response, the smoothed best response that underlies a quantal response equilibrium.

For fixed edge marginals $m$, the adversary's best response places its budget on the positions carrying the most path mass. Because the adversary minimizes a linear function of $m$ over $D$, this takes a sort, not a second DP.

The problem is not a shortest path. The adversary's inner minimum is concave in $\mu$, so spreading probability mass across paths genuinely pays. That is why a saddle-point solver is needed.

Research Program

We will build a solver whose only heavy operation is a banded forward-backward pass over the grid. This mirrors how KOMWU replaces enumeration over extensive-form strategy vertices with recursive kernel evaluations. KOMWU supplies the method: because the payoff is linear in edges, optimistic multiplicative weights over paths stays in product form, so each aligner update is a Gibbs distribution with accumulated edge scores.

We will compare three update rules on the aligner side:

The entropy term matters twice. It is the modeling choice that recovers ordinary posterior decoding when the budget is zero. It also makes the equilibrium unique, which removes the uniqueness assumption behind KOMWU's linear last-iterate guarantee. That assumption is flagged as an open limitation of that paper.

Last-iterate convergence also matters practically, which motivates using the analyses of regret-matching last iterates by Cai et al.. Without it, the solver must keep and average marginals over the full band across iterations.

The edit-distance scalability literature enters as a hard constraint and as a source of the oracle, not as a co-equal theme. Each iteration must be an anti-diagonal wavefront pass of the kind Accelign and LOGAN optimize. We will reuse a fixed band so that iterations run in lockstep without the warp divergence LOGAN reports for score-dependent X-drop bands.

We also test one pruning idea borrowed from EVPA, which permanently removes provably dominated poker actions before solving. In our setting, grid cells whose equilibrium marginal stays below a threshold for several consecutive iterations are dropped from the band. This shrinks later passes without re-introducing data-dependent control flow.

The analysis deliverable is a convergence bound stated in DP passes rather than abstract iterations, as a function of $\tau$ and the budget $B$. We will check it against measured pass counts.

Prior alignment work plays two roles. Yoon's message-passing alignment motivates the proposal. It replaces pair-HMM dynamic programming with iterated local confidence updates and reports gains on divergent BAliBASE sets. Its update rule, however, is heuristic, carries a hand-tuned coupling $\lambda$, has no convergence rate, and assumes a fixed scoring model. Our method differs in that the iteration is a game solver with a stated rate, and the object it converges to is defined by robustness to scoring error rather than by a smoothing heuristic.

Shifted Hamming Distance constrains the scope. Its documented degradation above roughly 15% error tells us that the high-error regime is where cheap filters fail. This is where a hedged, more expensive verification step could be worth ten to thirty DP passes. We restrict the claim to that regime and to divergent proteins, and do not claim benefits for clean short reads.

Baselines

The naive reference point is a single Needleman–Wunsch or Smith–Waterman alignment under the nominal scoring, run on the same GPU wavefront kernel. It costs one pass. Its throughput anchors the cost axis: Accelign reports up to 16.1 TCUPS for global alignment on one Blackwell GPU, and LOGAN reports 181.6 GCUPS on a V100 for X-drop. All our costs will be reported as multiples of this pass on identical hardware.

The strongest existing method on the accuracy question is posterior (maximum expected accuracy) decoding under a pair-HMM with the nominal scoring. We add Yoon's message-passing variant, which reports up to 0.23 higher sensitivity and 0.19 higher positive predictive value than a pair-HMM on BAliBASE 3.0, and 2.3 to 2.5 times lower runtime at $\lambda=0.25$. The file reports only these relative gains; for absolute pair-HMM or message-passing sensitivity on BAliBASE there is no reported result found on Lacuna. We will therefore re-run both ourselves. The pair-HMM will be run at its best temperature, tuned on the same held-out split and with the same number of tuning trials we give our own $\tau$ and $B$.

Beating these baselines means higher sensitivity and predictive value on the divergent reference sets and under injected misspecification. We will not count matched accuracy on clean data as a win.

The third baseline isolates the need for a game solver. It is Lagrangian mixture search: grid or subgradient search over weights on $K$ global scoring matrices, followed by posterior decoding under the mixed scoring. This baseline solves the global-only game exactly. Our method must beat it specifically when the adversary has position-level freedom.

Two ablations complete the set. The first sets $B=0$, which reduces our solver to the pair-HMM and checks the implementation. The second runs the same game with a plain, non-optimistic multiplicative-weights update, in the spirit of CFR. This isolates whether the accelerated equilibrium solvers are what keeps the pass count practical.

Why not just…?

Why not just tune the scoring matrix per dataset? Tuning helps when the misspecification is global and a labeled tuning set exists. It cannot hedge against error that varies by position within a single read, such as a noisy stretch of a nanopore read. It also offers no guarantee on the pairs it was not tuned for. We include a tuned-nominal pair-HMM as a baseline. The injected-misspecification experiment, where error is concentrated in random windows unseen at tuning time, is designed to show whether tuning closes the gap.

Why not just search over mixtures of a few substitution matrices? This is a real threat, and for a purely global adversary it is equivalent to our game: the inner problem dualizes into a $K$-dimensional concave search where each step is one DP pass. We therefore do not claim anything for that setting. We run mixture search as a baseline and expect it to tie there. The proposal lives or dies on the budgeted position-level adversary, which has no low-dimensional dual.

Why not just marginalize over scoring uncertainty in a Bayesian pair-HMM? Averaging over a prior on scores computes an expected-case alignment. That is the right answer if the prior is right, and the wrong one when errors cluster adversarially. We will run the averaged model with the same uncertainty set sampled as a prior. If it matches the equilibrium on realistically clustered errors, the game adds nothing, and we will report that.

Why not just solve the saddle point as a linear program? The regularized problem is not linear. Its unregularized version is a flow program with on the order of $MN$ variables plus budget constraints. The sparsified LP work shows that off-the-shelf LP scales poorly without heavy structure-specific compression. We will still run a commercial or open LP on short pairs as an exactness check, and report where it runs out of memory or time relative to the pass-based solver.

Proposed Experiments

The first decisive check is about convergence and cost. On pairwise projections of the BAliBASE 3.0 reference sets RV11 through RV50, and on simulated reads from E. coli at 5% to 25% error, we will measure exploitability (the adversary's gain from deviating) as a function of forward-backward passes. We will do this for optimistic multiplicative weights, Magnetic Mirror Descent, Predictive RM+, and the plain-update ablation. The claim survives only if the accelerated solvers reach small exploitability within roughly thirty passes and the plain update needs many times more. If every solver needs hundreds of passes, the method is too expensive, and we will say so.

The second check is about accuracy under misspecification. On BAliBASE's low-identity sets we will compare sensitivity and predictive value of equilibrium-decoded alignments against the naive, pair-HMM, message-passing, Bayesian-averaged and mixture-search baselines. For simulated long reads, where the true alignment is known, we will vary how concentrated the injected errors are, from uniform to windowed bursts. We will report alignment accuracy against error concentration. The prediction is that the equilibrium's advantage over averaging and tuning grows with concentration and vanishes when errors are uniform. A flat curve would refute the robustness motivation.

The third check is about throughput. We will implement the solver on a fixed-band anti-diagonal kernel and report wall-clock per pair and effective cell updates per second, as multiples of the single-pass baseline. We will compare this with and without EVPA-style marginal pruning, which tests whether pruning low-mass cells cuts later passes enough to bring total cost near a small constant multiple of one alignment.