Methods that infer contacts or structure from a set of related sequences only see what the alignment shows them. A multiple sequence alignment (MSA) is a grid that lines up the corresponding positions of related protein or RNA sequences. These methods look for pairs of columns that mutate together, since such pairs tend to touch in the folded molecule. When distant homologs are shifted by even one position, that joint-mutation signal disappears. The usual repair step is iterative refinement: split the sequences into two groups, realign them, keep the result if the score improves. This step keeps no record of what it has already tried. Combinatorial optimization learned long ago that search without memory gets stuck going in circles. It also learned that the best memory is not a list of recent moves but a record of whether a variable's neighborhood has changed since the variable last moved. That idea is called configuration checking.
We propose a discrete local search over alignments in which that neighborhood is defined by predicted structure. Each block of an aligned sequence can be shifted only if one of its predicted contact or base-pair partners has itself been realigned since the block last moved. In two sentences: alignment refinement should remember what it has tried, and the right memory for alignments is the one that respects which positions are physically coupled. We test whether this produces more correct alignments and better downstream contact maps on low-identity families, at the same number of objective evaluations as memoryless or annealing-based search.
Core Claim
Gradient-based alignment learning showed that structure-aware feedback can improve alignments. It also showed the danger. End-to-end learning of multiple sequence alignments with differentiable Smith-Waterman replaced the hard maximum in dynamic-programming alignment with a smooth one, so that contact-prediction or AlphaFold2 losses could train a learned alignment module. Its gains were modest: a median AUC improvement of 0.007 over MLM-GREMLIN on protein families and 0.02 on 17 Rfam RNA families. Its AlphaFold2-confidence variant produced "adversarial" alignments that were self-inconsistent and biologically nonsensical. That paper motivates the proposal and also constrains it.
Searching over hard alignments guarantees that every candidate is a valid, transitively consistent MSA. It does not, by itself, stop an objective from being exploited. We therefore make two separate design choices. The first is the objective: a homology-anchored score that never uses a downstream neural predictor's confidence. The second is the memory: configuration checking keyed to the predicted contact graph.
Our claim is about the second choice. At a matched evaluation budget, contact-keyed configuration checking recovers reference alignments and downstream contacts better than three alternatives: memoryless refinement, simulated annealing, and plain move-tabu search, all over the same moves and objective. The advantage should be largest in the under-25%-identity regime, where the alignment-bottleneck literature locates the failure.
Research Program
The search state is a hard MSA. A move takes one sequence, or a guide-tree subgroup, and shifts a contiguous ungapped segment left or right by a few positions, rebalancing the flanking gaps. A larger move swaps the register of a whole segment against a different anchor. Moves are chosen in two stages, borrowed from Two New Local Search Strategies for Minimum Vertex Cover, which picks what to remove and what to add separately to cut evaluation cost from multiplicative to additive. We first pick a segment, then its shift. The segment is chosen by best-from-multiple-selection sampling, taken from Two Efficient Local Search Algorithms for Maximum Weight Clique Problem: sample $k$ candidates and keep the best.
The objective for an alignment $A$ is
$$F(A) = \mathrm{SP}(A) + \lambda\, \mathrm{C}(A) - \mu\, \mathrm{G}(A),$$
where:
- $\mathrm{SP}(A)$ is the standard sum-of-pairs substitution score, which keeps the search anchored to sequence homology;
- $\mathrm{C}(A)$ counts how many predicted contacts or base pairs, mapped through the alignment, land on the same column pairs across sequences;
- $\mathrm{G}(A)$ is an affine gap penalty;
- $\lambda$ and $\mu$ are weights tuned on BAliBASE 3.0, the split MSACompro used for training.
For proteins, the contacts come from per-sequence predicted contact maps, as in MSACompro, which built its posterior matrices from predicted secondary structure, solvent accessibility, and contacts. For RNA, they come from single-sequence base-pair probabilities, in the spirit of PicXAA-R. Using predictions made independently of the alignment avoids a circular trap. Otherwise the alignment could create spurious co-variation, and then reward itself for it.
The memory rule transfers strong configuration checking from the clique solver in Two Efficient Local Search Algorithms for Maximum Weight Clique Problem. There, a vertex dropped from the clique may return only after a neighbor has been added. Here, a segment that has just been shifted is frozen until at least one of its predicted structural partners, in any sequence, has been realigned. Segments with no predicted partners fall back to a short move-tabu tenure.
Two further rules handle escapes and stale information. An aspiration rule, as in Double Configuration Checking in Stochastic Local Search for Satisfiability, overrides the freeze for any move that beats the best $F$ seen so far. Long-run counters record how often each segment's structural term was violated. These counters bias segment sampling and decay by a factor $\rho<1$ when their average passes a threshold, mirroring NuMVC's edge-weight forgetting.
The intuition is specific to alignment. Coupled positions should change register together. A segment that moves while its partners stay put will usually move straight back, which is exactly the two-state cycling that memoryless refinement suffers from.
Before building the full system, we will measure whether the problem actually exists. We will run MSACompro-style memoryless refinement under $F$ and hash every visited alignment. The question is what fraction of objective evaluations land on previously visited states, or on states differing only in contact-free segments. If this fraction is negligible on low-identity families, memory has nothing to fix, and we stop or redirect.
Baselines
The naive reference point is the starting progressive alignment, with no refinement, fed directly to the downstream contact predictor. Every method starts from that same alignment. Next is memoryless randomized refinement in the style of MSACompro: random subgroup split, profile realignment, accept if $F$ improves. It uses our objective, so it isolates search strategy from scoring. MSACompro itself is also run unchanged as the strongest existing structure-aware aligner. Its reported SABmark SABRE result relative to MSAProbs is sum-of-pairs 0.853 and true-column 0.780 (MSACompro), and the full method should at least match it.
For RNA, the strongest aligner in the file is PicXAA-R. It reports a 6–7% sum-of-pairs improvement over MXSCARNA on BraliSub and LocalExtR and outperforms the other tested schemes below 60% identity on BRAliBase 2.1. We run it, and also use its output as an alternative starting point, to test whether our search can repair its greedily fixed skeletons. For the gradient-based alternative we run SMURF from End-to-end learning of multiple sequence alignments with differentiable Smith-Waterman on its own protein and Rfam families, where the reported reference is its median AUC gain over MLM-GREMLIN quoted above.
The two decisive ablations share our move set, objective, and starting alignment, so only the memory differs. One is simulated annealing with a tuned cooling schedule. The other is plain tabu search whose tenure lists moves, not structural neighborhoods. The full method also gets a "random-graph" ablation, in which configuration checking uses a shuffled contact graph with the same degree distribution. If that ablation performs equally well, the gain comes from generic memory, not from structure.
All search methods receive the same number of objective evaluations, the same number of random seeds, and the same hyperparameter tuning budget on BAliBASE 3.0. Beating a baseline means a statistically significant improvement in true-column score on held-out low-identity cases, together with no loss in downstream long-range contact precision, paired across families.
Why not just…?
Why not just use simulated annealing or random restarts over the same moves? This is the most serious threat. Annealing escapes local optima without any memory, and with a generous budget it may match tabu search. The matched-evaluation comparison and the shuffled-contact-graph ablation settle it. In SAT, configuration checking does beat strong memoryless solvers: DCCASat solved 93 of 250 SC13 threshold instances against 81 for probSAT (Double Configuration Checking in Stochastic Local Search for Satisfiability). That evidence does not transfer automatically to alignments, however. If annealing ties our method, we will report that the alignment landscape is not cycle-dominated and that the objective, not the memory, carries the gain.
Why not just plug the structural objective into existing memoryless refinement? MSACompro already refines alignments using structural features, so the gap might be closed by better scoring alone. The hashed-revisit diagnostic answers this directly. The memoryless-refinement baseline under the identical $F$ measures how much of the remaining error is due to search rather than scoring.
Why not just make alignment differentiable and backpropagate? Petti et al. tried this. The AlphaFold2-driven variant produced nonsensical alignments, and the coevolution-driven variant gave small AUC gains. Separately, Discrete Tabu Search for Graph Matching found that continuous relaxations lose accuracy when rounded, whereas discrete tabu search held 100% accuracy at deformation noise 0.25. We do not claim discreteness alone prevents objective exploitation. That is why AlphaFold2 confidence is kept out of the objective entirely and used only as a held-out check.
Why not just widen the band or drop bad sequences? REAPR's banded realignment (Structure-based whole-genome realignment reveals many novel noncoding RNAs) assumes the input alignment is roughly right. The register-swap move exists precisely for errors larger than a band can reach. We will report what fraction of the corrected segments moved farther than a typical band would allow. Dropping sequences discards the homologs that low-identity families can least afford to lose, but we include a subsampling control on the CASP targets to check this.
Proposed Experiments
Alignment accuracy is measured on BAliBASE 3.0 low-identity references, SABmark SABRE, and BRAliBase 2.1 binned by identity, using sum-of-pairs and true-column scores against the curated references.
Downstream value is measured in two ways. For proteins, we feed each method's alignments to plmDCA and score long-range top-10 contact precision on the 89 CASP11 targets. There, Protein contact prediction from amino acid co-evolution using convolutional networks for graph-valued images reports 0.686 for plmConv, 0.594 for MetaPSICOV, and 0.536 for plmDCA on its own alignments. Our target is to raise plmDCA's number by changing only the alignment. We will also report whether the gain persists when the downstream model is plmConv, as a check that a stronger predictor does not simply absorb alignment errors. For RNA, we use the 17 Rfam families from the SMURF study and score base-pair AUC under a fixed co-evolution model.
The adversarial check runs AlphaFold2 on a handful of CASP14 domains using alignments that were never optimized for it. No per-domain RMSD numbers were found on Lacuna for the SMURF comparison, so this check is reported as paired confidence and RMSD changes, not against a quoted figure. Across all runs we plot objective gain against reference true-column gain. A rising objective with flat or falling reference accuracy would flag exploitation even in discrete space.
The decisive outcomes are three. First, the revisit fraction must be substantial for memory to matter. Second, contact-keyed configuration checking must beat both annealing and the shuffled-graph ablation in the under-25%-identity bins. Third, those alignment gains must carry through to contact precision.
References
- End-to-end learning of multiple sequence alignments with differentiable Smith-Waterman
- Two New Local Search Strategies for Minimum Vertex Cover
- Two Efficient Local Search Algorithms for Maximum Weight Clique Problem
- MSACompro: protein multiple sequence alignment using predicted secondary structure, solvent accessibility, and residue-residue contacts
- PicXAA-R: Efficient structural alignment of multiple RNA sequences using a greedy approach
- Double Configuration Checking in Stochastic Local Search for Satisfiability
- Discrete Tabu Search for Graph Matching
- Structure-based whole-genome realignment reveals many novel noncoding RNAs
- Protein contact prediction from amino acid co-evolution using convolutional networks for graph-valued images