Fast aligners for long sequences split the problem into pieces. They first find short, confident exact matches ("anchors"), then run a small, sensitive alignment inside each gap between anchors. Inside every gap, and again when deciding which anchors to trust, these aligners collapse several goals into one weighted score. Those goals include "don't break the protein reading frame," "don't anchor on a repeat," and "maximize similarity." A single weighted score lets a large similarity gain buy a biologically unacceptable frameshift, and nobody can say in advance how much of the higher priority was traded away. We propose to replace that score with a priority order that carries an explicit, interpretable allowance. The aligner may give up at most δ units of the top-priority objective, for example at most one extra frameshift, to gain on the next objective. It must never give up more.
The technical point that makes this practical is a small exactness result. When objectives add up along an alignment path, a dynamic program can find the best-scoring path among all paths within δ of the optimal primary value. It does this exactly, in one pass, by keeping at each cell only the candidate partial paths whose primary value is within δ of that cell's best. The cost is roughly (δ+1) times that of an ordinary alignment. This turns lexicographic optimization with slack, which the reinforcement learning literature treats as a learned, approximate procedure, into an exact operator. That operator can be dropped into both tiers of an anchor-partitioned aligner.
Core Claim
Let each alignment path $\pi$ have a primary score $F_1(\pi)$ and a secondary score $F_2(\pi)$. Both are sums of per-step contributions and both are maximized. Let $F_1^*$ be the best achievable primary score. We want
$$\pi^\dagger = \arg\max_{\pi:\, F_1(\pi) \ge F_1^* - \delta} F_2(\pi).$$
Lemma. Suppose $\pi^\dagger$ passes through a dynamic-programming cell $v$. Write $b_v$ for the best primary score of any prefix path ending at $v$. Because all prefixes ending at $v$ share the same possible suffixes, the prefix of $\pi^\dagger$ has primary score at least $b_v - \delta$.
It is therefore safe to keep, at each cell, one best secondary score for each primary value in $[b_v-\delta, b_v]$. When the primary score is an integer count, such as frameshifts or non-unique anchors, that is at most $\delta+1$ entries per cell.
At $\delta=0$ this reduces to the ⟨T,T⟩ lexicographic semiring of Lexicographic Semirings for Exact Automata Encoding of Sequence Models. That work used strict two-level weights to make ordinary shortest-path search reproduce language-model backoff exactly. It had no slack, and it did not apply the idea to alignment. With δ>0, the relaxed selection is not a semiring. The lemma is what restores optimal substructure.
The empirical claim follows from this. In anchor-partitioned alignment of diverged coding sequences and repeat-rich regions, slack-lexicographic selection gives better frame preservation and fewer false anchors than a weight-tuned scalar score. It does so at matched similarity, and its δ transfers across datasets without re-tuning, which a weight does not.
Research Program
The lexicographic line of work supplies the objective form. Bounded slack comes from Lexicographic MDPs (Multi-Objective MDPs with Conditional Lexicographic Reward Preferences) and the tolerance-based lexicographic bandit of Lexicographic Multi-Objective Reinforcement Learning. Both works name slack calibration as open, and both solve by iterative value estimation. Here the decision space is a known alignment lattice, so we solve exactly and treat calibration as an empirical question with interpretable units. The general-purpose tiered optimizers BoTier and Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems motivate the priority structure. They are black-box methods and exploit no dynamic-programming structure, so we do not use them as methods.
The alignment side supplies the pipeline:
- Anchor stage. Anchors of logarithmic length, which Near-Linear Time Edit Distance for Indel Channels proves are unique with high probability under random sequence and low divergence.
- Recursive refinement. Gap-by-gap refinement in the style of GLASS (Human and mouse gene structure).
- Known failure modes. The file records two. Anchors become non-unique in repetitive or skewed sequence, where the Ganesh–Sy guarantees require ρ ≤ 0.03 and uniform composition. Scalar aligners over-align unrelated sequence, which Fast Statistical Alignment documents.
We build a two-tier aligner with the lemma applied at each tier.
Anchor chaining is itself a longest-chain dynamic program over candidate anchors.
- Primary objective: minus the number of anchors in the chain whose k-mer occurs more than once in either sequence.
- Secondary objective: total anchored length.
- Slack $\delta_A$ counts how many repeat anchors may be admitted to extend coverage.
Gap filling uses an affine-gap alignment whose state is extended by gap length modulo 3, which triples the states.
- Primary objective: minus the number of frame-disrupting indel runs inside annotated or predicted coding intervals.
- Secondary objective: the usual substitution and gap score.
- Slack $\delta_G$ counts extra frameshifts.
We will prove the lemma formally, including the affine-gap case. We will then measure how often the frontier actually reaches δ+1 entries, which gives the real overhead as opposed to the worst case.
Calibration of δ gets its own study, since it is the open problem both lexicographic papers flag. We compare three settings:
- δ fixed from domain units, for example δ_G = 0 or 1;
- δ chosen on the 12 training pairs of the human–mouse set;
- δ set per instance from the instance's own optimum $F_1^*$.
Baselines
The naive reference is the same anchor-partitioned pipeline with a single scalar score. It uses standard affine-gap scoring, with no frame term and no repeat term. This is the configuration most tiered aligners in the file effectively use, and it tells us whether the extra objectives matter at all.
The strongest competitor on this question is the same pipeline with a weighted-sum score, $F_2 + wF_1$, at both tiers. We sweep w over a log grid on the 12 training pairs, with the same number of configurations evaluated as for δ, and the same anchors, data and compute. This baseline isolates the claim that priority-with-slack beats a tuned trade-off. We report both methods as full curves of frame preservation versus alignment identity. Beating it means two things:
- The δ-curve dominates or matches the w-curve on held-out pairs, with at least one operating point strictly better on frame preservation at equal identity.
- The training-selected δ loses less when moved to simulated high-divergence and repeat-injected data than the training-selected w does.
The strongest existing systems are the two points of reference from the file. For the human–mouse pairs, GLASS with its gene-prediction layer reports 95% nucleotide sensitivity and 97% specificity. It also reports 94% of internal coding exons with both boundaries perfect, and 26 false exons versus 68 for GENSCAN (Human and mouse gene structure). These are exon-prediction figures, not raw alignment accuracy. We will re-run GLASS-style recursive anchoring as a baseline and compare on our alignment-level exon-boundary metric. No reported alignment-level exon-boundary accuracy was found on Lacuna for any aligner on this set.
For over-alignment, FSA reports aligning only about 4–5% of random unrelated sequence, where traditional programs align about 95% (Fast Statistical Alignment). FSA also reports a mis-alignment rate below 50% in the SABmark twilight zone. We run FSA on the same inputs.
The key ablations apply slack-lexicographic selection at only one tier, and strict lexicographic selection (δ=0, the Roark semiring) at both. The δ=0 ablation isolates slack as the new ingredient rather than priority ordering, which already exists.
Why not just…?
Why not just put a very large weight on the primary objective? For integer objectives, a large enough weight reproduces strict δ=0 lexicographic selection exactly, so that case gains nothing from our operator; our δ=0 ablation is precisely this. A moderate weight allows trade-offs, but the amount of primary objective given up depends on how large the secondary gains happen to be on each instance. It cannot promise "at most one extra frameshift." Prioritized Optimal Control reports this kind of weight tuning causing conditioning problems and needing many iterations, 75 against 18 for the prioritized solver. That is a different domain, so it motivates rather than settles the question. This is the real threat. If the tuned-w curve matches the δ curve and w transfers as well as δ across divergence levels, the accuracy claim fails, and only the guarantee remains. The weighted-sum baseline and transfer test are designed to show which is true.
Why not just impose an absolute budget, such as "at most K frameshifts per alignment"? This constraint-based variant tracks a counter per cell at similar cost, so it is a fair competitor. The difference is that it is anchored to a fixed number rather than to each instance's own optimum. A pair of genes that truly needs three frameshifts, perhaps from an annotation error or a pseudogene, is then either infeasible or forced into a K large enough to be loose everywhere else. We run the fixed-K variant alongside δ. If a single K performs as well as δ across gene lengths and divergence levels, we will report that the relative formulation adds nothing.
Why not just generate the top-k scalar alignments and re-rank them by frame preservation? This is cheap. The concern is that frame-preserving alternatives can differ from the scalar optimum at many gap positions, so they may lie far down the ranked list. We measure, on held-out pairs, how large k must be before re-ranking recovers the slack-lexicographic answer, and compare runtimes at that k. If modest k suffices, the operator's value reduces to an efficiency argument, and we will say so.
Proposed Experiments
Simulation with exact ground truth. We evolve codon-structured sequences under an indel channel with divergence ρ from 0.01 to 0.15, spanning the ρ ≤ 0.03 regime of the Ganesh–Sy analysis and beyond it. Frameshifts are rare but nonzero, and tandem repeats and AT-skew are injected at controlled rates. Metrics are:
- column-level alignment accuracy against the true alignment;
- frame-preservation rate;
- fraction of chains containing a non-unique anchor;
- wall-clock time and the observed frontier size.
The decisive check is whether the scalar and slack-lexicographic curves separate as ρ and repeat density rise. They should be nearly identical in the easy regime. If they separate nowhere, the proposal is not worth pursuing further.
Real orthologs. On the 105 held-out human–mouse GenBank pairs, we measure:
- the fraction of annotated exon boundaries whose aligned partner is an orthologous exon boundary;
- in-frame alignment of coding exons;
- identity.
We run all baselines above, with every method's single hyperparameter chosen on the 12 training pairs.
Over-alignment control. Following FSA's protocol, we align shuffled and unrelated sequence pairs and report the fraction of residues aligned, with the FSA figure of about 4–5% as the reference. The prediction is that repeat-penalizing anchor chaining alone cuts false anchoring substantially. We do not expect it to reach FSA's posterior-based level, and we will report whichever outcome occurs.
Generality check outside biology. We run a smaller transfer test on the lattice of Candidate Soups using its official code (Candidate_Soups, art_e44a5dd2cf104a62911e8c0692c08520), on WMT'14 English–German and WMT'16 English–Romanian. Candidate Soups builds a lattice over the gaps between agreed-upon anchors from several translation candidates and picks paths with a single greedy autoregressive score. It reports an average gain of 2.5 to 2.9 BLEU with a 7.6x to 11.5x speedup over the standard Transformer. We replace the greedy scalar with exact slack-lexicographic search:
- primary objective: number of candidates supporting each chosen token;
- secondary objective: autoregressive log-probability.
We report BLEU and speed. Success means matching or exceeding Candidate Soups' BLEU at comparable speed. This test is secondary. It asks only whether the same exact operator helps in a second anchor-partitioned lattice, and a null result here would not undercut the genomic claim.
References
- Lexicographic Semirings for Exact Automata Encoding of Sequence Models
- Multi-Objective MDPs with Conditional Lexicographic Reward Preferences
- Lexicographic Multi-Objective Reinforcement Learning
- BoTier: Multi-Objective Bayesian Optimization with Tiered Composite Objectives
- Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels
- Near-Linear Time Edit Distance for Indel Channels
- Human and mouse gene structure: comparative analysis and application to exon prediction
- Fast Statistical Alignment
- Prioritized optimal control
- Candidate Soups: Fusing Candidate Results Improves Translation Quality for Non-Autoregressive Translation
- art_e44a5dd2cf104a62911e8c0692c08520