Killing Decoy Structures: Choosing the Fewest Experiments That Rule Out Alternative Conformations

When structural biologists fit a protein model to experimental data, the data rarely pin down a single answer. Measurements such as a medium-resolution cryo-electron microscopy (cryo-EM) map, a handful of chemical cross-links, or a few distance measurements are averages over millions of molecules. Many different structures, or mixtures of structures, can reproduce them equally well. Software testing has a mature answer to the analogous problem. Many candidate programs can pass a weak test suite, and the remedy is to generate deliberately wrong "mutant" programs that slip through, then select the smallest set of extra tests that catches every one of them. We propose to carry that loop over to structure determination. First, actively generate decoy structures that fit the current data yet differ from the current best answer. Then choose the fewest additional measurements that separate all of these hypotheses from one another, posed as a set-cover problem and solved exactly where possible.

The practical stakes are that each extra cross-linking, spin-labeling, or NMR measurement costs real lab time. The scientific stakes are that the field's best-known failure mode is quietly missing minor functional states. A method that says "these six residue pairs, and no fewer, are needed to tell apart every conformation compatible with your map" would turn the known ambiguity of ensemble data into a concrete experimental plan. The central claim to test is the following. Selecting measurements so that every pair of plausible hypotheses is separated, a worst-case coverage criterion, recovers low-population states better than selecting by expected information gain. That gap should be largest when the hypotheses come from an adversarial decoy search rather than from ordinary posterior sampling.

What exists and what is missing

The Bayesian view of structure determination treats structure as a posterior over conformations given data, a forward model, and a physical prior. That view is well established. Bayesian Modeling of Biomolecular Assemblies with Cryo-EM Maps estimates noise and data weights jointly with structure. A unifying probabilistic framework for analyzing residual dipolar couplings does the same for NMR alignment parameters. We reuse this machinery to define how strongly a candidate measurement discriminates two hypotheses. We do not modify it.

Three papers motivate the gap. Principles of protein structural ensemble determination stresses that distinct ensembles can fit averaged data equally well, which makes validation ambiguous. Bayesian methods in integrative structure modeling notes that Markov chain Monte Carlo (MCMC) sampling gets trapped and fails to visit modes separated by high energy barriers. Multiscale guidance of protein structure prediction with heterogeneous cryo-EM data (CryoBoltz) documents single-state collapse in AI structure predictors. Taken together, these imply that the alternatives one should worry about are exactly the ones a standard sampler will not show you.

CryoBoltz also supplies our decoy generator. It steers a pretrained diffusion model (a generator that produces structures by gradually denoising random coordinates) toward agreement with a density map, without retraining. It does this through diffusion posterior sampling, which adds a data-fit gradient at each denoising step. CryoBoltz draws samples independently and has no notion of covering the space of alternatives. We add a repulsion term that pushes each new sample away from structures already found, while it still has to fit the data.

The selection side borrows directly from test-suite distillation. Semantic Evaluation for Text-to-SQL with Distilled Test Suites generates "neighbor" queries that are almost but not quite correct. It then greedily keeps about 42 of 1,000 fuzzed databases that still expose them. VeriScale: Adversarial Test-Suite Scaling for Verifiable Code Generation does the same with adversarial mutant programs. Is Your Code Generated by ChatGPT Really Correct? uses greedy set cover to compress an 80× test expansion without losing defect detection. Automated Regression Testing Using Constraint Programming shows that exact constraint-programming formulations of the same reduction solve industrial instances quickly. They are competitive with a commercial integer solver and beat SAT-based tools. Our key difference from all of these is that in software the correct program is known, so tests only need to separate it from mutants. In structure determination the true ensemble is unknown, so every pair of hypotheses must be separated.

The closest structural-biology idea, maximum parsimony in Bonomi et al., selects a minimal set of conformations. We instead select a minimal set of measurements. One minimizes the explanation; the other minimizes the evidence needed to decide among explanations.

Core Claim

Let $H_1,\dots,H_K$ be hypotheses. Each is a conformation or small weighted ensemble that fits the current data within noise. Let $m$ range over candidate measurements, such as a residue pair for a cross-link or a distance measurement. Using the Bayesian forward model, we say measurement $m$ separates $H_i$ from $H_j$ when the predicted averaged observables differ by more than $\kappa$ noise standard deviations:

$$\left|\langle f_m \rangle_{H_i} - \langle f_m \rangle_{H_j}\right| > \kappa\, \sigma_m .$$

Here $f_m$ is the forward model for measurement $m$, $\langle\cdot\rangle_H$ averages over the hypothesis's conformations, $\sigma_m$ is the noise level for $m$, and $\kappa$ sets the required margin (we use $\kappa=3$ and vary it). The universe of goals is the set of all hypothesis pairs. Each measurement covers the pairs it separates, and we seek the smallest set of measurements covering every pair. In the testing literature this is a minimum test-collection or identification problem, which is NP-hard. We solve it with greedy cover and, for instance sizes in the low thousands of pairs, with an exact constraint-programming model following Gotlieb et al.

We claim this design recovers minor states more reliably than information-gain designs for two reasons. Information gain is dominated by high-probability hypotheses, so a 10%-population state contributes little to the average. And hypotheses produced by a repulsive decoy search include alternatives that posterior samples would never contain.

Research Program

The pipeline has three stages, all built from existing pieces. Decoy generation runs CryoBoltz-style guided diffusion on Boltz-1. The guidance has two parts: a data-fit term against the available map or restraints, and a repulsion term on pairwise structural distance to previously accepted samples. A sample is accepted as a decoy only if its likelihood under the current data stays within a tolerance of the best fit. That makes it a genuine alternative explanation rather than noise. To keep $K$ manageable, decoys are grouped into hypotheses by clustering, and small mixtures are fitted where the data are ensemble averages.

Measurement scoring computes predicted observables for every candidate residue pair under every hypothesis. We use cross-link compatibility (Cα distance under linker length) and inter-residue distances for spin-label or NMR-style restraints, each with its own noise model.

Selection then solves the cover. Iteration is part of the design: after the selected measurements are "collected" (simulated in benchmarks), inference reruns and new decoys are sought, mirroring VeriScale's repeat-until-no-mutant-survives loop. We will also study the analysis question the cover answers for free. When some hypothesis pairs cannot be separated by any available measurement type, the method reports a certified ambiguity. That is a statement Bonomi et al. call for but no current tool produces.

Baselines

The naive reference point is random selection of the same number of measurements from the candidate pool, with results averaged over many draws. A second simple reference is the heuristic many labs use in practice: rank residue pairs by the variance of their predicted distance across current posterior samples and take the top ones. Both run on identical candidate pools and budgets.

The strongest competitor is greedy Bayesian optimal experimental design, which adds at each step the measurement with the largest expected information gain about the hypothesis label under the posterior weights. It is the principled standard for this question and has the same inputs. To make the comparison fair, it receives exactly the same hypothesis pool as our method, including the decoys, the same forward and noise models, and the same measurement budget. We found no reported result on Lacuna for information-gain measurement selection on any of the structural benchmarks below, so all numbers will be produced by us.

The decisive ablation crosses two factors. The hypothesis source is either standard posterior samples (MCMC or unguided CryoBoltz) or the repulsive decoy search. The selection rule is either information gain or pairwise cover. This two-by-two design separates the contribution of decoy generation from that of the coverage criterion. A further ablation compares greedy against exact constraint-programming covers, which tells us whether exactness buys smaller designs. A last variant weights cover goals by hypothesis probability, which moves the criterion toward information gain and locates the crossover.

We count as beating the strongest baseline any result where, at equal budget, cover selection recovers the minor state within 2 Å all-atom RMSD in significantly more trials than information gain, or reaches the same recovery rate with fewer measurements. Population error for the dominant state must not worsen in either case.

Why not just…?

Why not just use expected information gain? This is the real threat, and the proposal is designed to be settled by it. Information gain is optimal on average under correct posterior weights. Our argument is that the weights are exactly what is wrong when samplers miss modes, a failure documented by Habeck and by CryoBoltz. The two-by-two ablation decides it. If information gain on the decoy-augmented pool matches pairwise cover, the contribution reduces to decoy generation, and we will report it that way.

Why not just collect more of the same data or higher-resolution maps? Averaged observables stay averaged at any resolution. Two ensembles with the same mean density remain indistinguishable, which is the under-determination Bonomi et al. describe. In our experiments, increasing the simulated map resolution while holding the population mixture fixed shows whether minor-state recovery improves without orthogonal measurements.

Why not just cluster the ensemble and pick measurements that separate cluster centers? Done carefully, this is nearly our selection step. Our method in fact clusters decoys into hypotheses. What it adds is twofold: the hypotheses come from a search for alternatives rather than from the sampler's own output, and the measurement choice comes with a guarantee that every pair is separated at a stated noise margin. The variance-ranking baseline approximates the centroid approach. If it matches cover selection, the coverage formalism is not earning its place.

Proposed Experiments

All benchmarks use hidden ground truth. We simulate a degenerate starting dataset, let each method choose a budget of 2 to 20 measurements, simulate those measurements with realistic noise, rerun inference, and score recovery.

The first setting uses the STP10 transporter synthetic maps from CryoBoltz. We build two-state mixtures of inward- and outward-facing conformations with the minor state at 5 to 30% population, and blur the maps until diffusion posterior sampling alone returns mostly the major state. The reference point is that CryoBoltz reports about 1.0 Å all-atom RMSD for both states when guided by separate state maps. Our question is how many and which added measurements restore that accuracy from a single mixed map.

The second setting uses the SARS-CoV-2 spike opening intermediates from Determination of intermediate state structures in the opening pathway of SARS-CoV-2 spike using cryo-electron microscopy as a multi-state ground truth with more than two hypotheses, which stresses the pairwise cover.

The third setting uses the intrinsically disordered ensemble PED00151 from the Protein Ensemble Database. It is a deliberate stress test where states are not discrete. There the expected outcome is that the cover reports many inseparable pairs and loses its advantage, consistent with Bonomi et al.'s recommendation that parsimony suits low-entropy systems.

Metrics are minor-state recovery rate at 2 Å RMSD, state-population error, measurements needed to reach 90% recovery, and the fraction of hypothesis pairs left certified-inseparable.

The decisive check is the STP10 sweep over minor-state population. Our claim predicts that the advantage of cover over information gain grows as the minor population shrinks, and that the advantage appears mainly when decoys come from the repulsive search. If neither pattern appears, the core claim is false.