Long DNA sequences with a strong non-repetition guarantee are workhorses of DNA nanotechnology and single-cell barcoding: we want strands in which no window of length $q$ (a $q$-gram) — and crucially also its Watson-Crick reverse complement, since DNA hybridizes as a double strand — occurs twice. The cleanest construction treats each $q$-gram as an edge in a De Bruijn graph and reads the sequence off an Euler tour, a closed walk using every edge exactly once. The catch is a hard parity discontinuity. For odd $q$, no DNA word can equal its own reverse complement, the collapsed quotient graph is perfectly balanced, and a linear-time tour provably achieves the theoretical length maximum Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs. For even $q$, self-complementary $q$-grams exist, promote self-hybridization, and must be excised — and excising them unbalances the graph, forcing further deletions to restore Eulerian degree balance. The minimum such deletion set is an open problem: the best analytical construction is provably suboptimal, and the exact integer linear program (ILP) becomes intractable beyond $q = 8$.
Two further gaps compound this. First, deletions are not interchangeable: some $q$-grams are biophysically far worse than others (extreme GC content, hairpin propensity, off-target melting behavior), yet the existing formulation treats the deletion problem as purely topological. Second, the relevant theory papers report no empirical results at all — the ILP paper explicitly contains no datasets Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs, a pattern repeated across neighboring theory work such as the bi-criteria bandit resilience framework, which proves $\tilde{O}(\delta^{2/3}N^{1/3}T^{2/3})$ regret bounds with zero benchmark evaluations A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback. This proposal closes all three gaps at once: it embeds a tunable aggregation operator directly into the edge-deletion objective, builds a scalable solver for the paired-edge Eulerization problem, and submits the whole pipeline to the biophysical and scalability benchmarks that this literature has avoided.
Core Claim
The claim is that even-$q$ Eulerization by deletion should be solved as a weighted, multi-criteria problem in which each candidate deletion is scored by a parameterized aggregation of biophysical criteria, and that this reformulation simultaneously makes the problem more tractable (min-cost-flow structure instead of monolithic ILP) and more useful (near-maximal sequences with measurably better thermodynamic profiles). Concretely, each edge $e$ (a $q$-gram) carries $r$ normalized badness scores $c_1(e),\dots,c_r(e)$ — hairpin propensity, GC deviation from target, melting-temperature deviation — aggregated by a power mean, a single formula that recovers the arithmetic mean at $\alpha = 1$ and the worst single criterion as $\alpha \to \infty$:
$$\Phi_\alpha(e) = \left(\tfrac{1}{r}\sum_{j=1}^{r} c_j(e)^{\alpha}\right)^{1/\alpha}.$$
The exponent $\alpha$ is a dial between compensatory deletion (bad on average) and non-compensatory deletion (bad on any one criterion suffices, so a severe hairpin risk cannot be bought off with good GC content). The deletion set $D$ must restore in/out degree balance and strong connectivity on the De Bruijn quotient graph under the physical pairing constraint that a $q$-gram and its Watson-Crick partner are deleted together, and the objective trades deletion cardinality against the aggregate retained-edge penalty, so a single budget knob positions the design on the length-versus-quality frontier. This replaces the rigid "objective versus hard constraint" coupling of the resilience framework A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback with a continuous, user-steerable trade-off.
The aggregation machinery is transplanted from domains where it has already earned empirical validation: power means beat linear scoring for summarization evaluation, lifting Spearman correlation with human judgments from 0.169 to 0.2417 on TAC-08 Power mean pyramid scores for summarization evaluation, and power-mean aggregate dissimilarity with $\alpha = -5$ captures disjoint, non-convex query regions that linear scoring cannot FALCON: Feedback Adaptive Loop for Content-Based Retrieval. Notably, the optimal exponent in the summarization setting fell between the geometric and arithmetic means — evidence that the right point on the compensatory dial is domain-specific and must be tuned, not assumed. For the known physical coupling in DNA (GC content shifts melting temperature, which shifts hairpin free energy), a second variant swaps the power mean for a Heronian mean, whose parameters $(s,t)$ score pairwise criterion interactions Some q-Rung Dual Hesitant Fuzzy Heronian Mean Operators with Their Application to Multiple Attribute Group Decision-Making, with Muirhead means available for higher-order interactions Pythagorean Fuzzy Interaction Muirhead Means with Their Application to Multi-Attribute Group Decision-Making. These operators have never left stylized decision-matrix examples; wiring them into a graph traversal pipeline is exactly the transfer this proposal tests.
Research Program
The program has three components. First, the formulation work: write the paired-edge degree-balance constraints as a circulation problem on the imbalance structure of the quotient graph and investigate whether the constraint matrix is totally unimodular. If it is, the unweighted minimum deletion problem — the open problem left by the analytical construction in Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs — is solvable in polynomial time by min-cost flow, and the weighted variant with $\Phi_\alpha$ costs is a min-cost flow with millions of variables but strongly polynomial algorithms, which is precisely what makes $q \ge 12$ feasible where the ILP's $4^q$-scale variable count (over $1.6\times 10^7$ at $q=12$) is not. If pairing constraints break integrality, the linear relaxation still yields a certified lower bound on the deletion count, which is more than the current state of the art offers. Second, the solver: a flow-based exact mode for the pure topological problem, plus a greedy paired-deletion heuristic with local repair for the full biophysical objective, both followed by a standard Euler tour and partitioning into oligos in the style of seqwalk Scalable design of orthogonal DNA barcode libraries. Third, the evaluation discipline: every claim is reported as a measured number — sequence length, deletion count, NUPACK thermodynamic scores, wall-clock time, memory — following the stance that asymptotic guarantees without finite-sample measurements are exactly the gap this literature keeps falling into, from nearly-linear graph partitioning A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning to the resilience framework above.
Baselines
The naive reference point is the analytical construction from the ILP paper Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs: it produces valid even-$q$ sequences but is proven by its own authors to delete more edges than necessary, and it selects deletions with no biophysical information at all. Beating it means strictly fewer deletions (equivalently, longer sequences) at every even $q$ from 4 to 14, at any runtime. The strongest exact competitor is the same paper's ILP, which is optimal where it terminates; it was only run for $q = 2$ through $8$, and for even $q > 4$ it already falls short of the naive theoretical bound. No reported result found on Lacuna for the ILP's exact even-$q$ deletion counts, so we will reproduce them ourselves on identical graphs for $q \le 8$ and use them as ground truth; matching the ILP optimum at equal deletion count while running orders of magnitude faster, and staying correct at $q \ge 12$ where the ILP does not terminate, counts as beating it. The strongest scalable competitor is seqwalk Scalable design of orthogonal DNA barcode libraries, which generated over $10^6$ SSM-satisfying 25-nt barcodes in under 20 seconds under 1 GB of memory, roughly two orders of magnitude more sequences than DeLOB, which needed nearly 100 GB for a smaller library; we will run seqwalk ourselves on the same hardware at matched library size and compare NUPACK thermodynamic metrics, runtime, and memory — seqwalk will likely win raw speed, so the fair comparison is combined yield-and-thermodynamics, since its authors concede it does not model off-target hybridization energies. The strongest biophysical competitor is the Improved Chaos Whale optimizer with NUPACK validation, which achieved sequence quality with the $i$ value consistently close to 1 and beat rival metaheuristics on roughly 75% of 23 benchmark functions Stable DNA Sequence Over Close-Ending and Pairing Sequences Constraint — we rerun it under the same NUPACK evaluation budget. Finally, the key ablation runs our identical solver and tuning protocol with $\alpha = 1$ and a tuned weighted sum instead of the power mean, and with uniform penalties (pure topology); this isolates whether the parameterized aggregation itself, rather than the flow-based solver or the biophysical scoring, earns any improvement. All methods get the same tuning protocol as the power-mean pyramid study, which tuned its exponent on a held-out split before testing Power mean pyramid scores for summarization evaluation.
Why not just…?
Why not just run the ILP with a modern solver? Because the scaling is structural, not implementational: the formulation has a variable per $q$-gram, over $1.6 \times 10^7$ at $q = 12$, and the original work reports that for even $q > 4$ the optimum already falls short of the theoretical bound Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs. The ILP also cannot encode power-mean or Heronian penalties without destroying linearity. That said, for $q \le 8$ the ILP is simply better, and we use it as ground truth rather than pretend otherwise.
Why not just use a fixed weighted sum of criteria? This is the most serious alternative, and we treat it as a real threat rather than argue it away. The transferable evidence says parameterization pays: the power mean beat the linear Pyramid combination on every correlation metric on TAC-08 (Spearman 0.2417 versus 0.169) Power mean pyramid scores for summarization evaluation, and linear scoring cannot represent the disjunctive geometries that $\alpha = -5$ captures in retrieval FALCON: Feedback Adaptive Loop for Content-Based Retrieval. But that evidence is from other domains. The decisive experiment is in this proposal: the $\alpha = 1$ ablation with an equally tuned weight vector, run at the same evaluation budget. If the weighted sum matches the power mean on combined length-and-thermodynamics metrics, we will report that honestly, and the contribution narrows to the scalable paired-deletion solver plus a useful negative result on aggregation expressivity in combinatorial pruning.
Why not just throw a metaheuristic or reinforcement learning at NUPACK directly? The Improved Chaos Whale optimizer does exactly this and produces thermodynamically sound sequences Stable DNA Sequence Over Close-Ending and Pairing Sequences Constraint, and the greedy-policy approach for expensive multi-objective combinatorial optimization Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization, with its public codebase snu-mllab/GreedyPolicyForMOCO, needed 1.69× fewer expensive queries than top baselines on RFP design — precisely because such queries are costly. These methods may win on raw NUPACK score, but they offer no structural guarantee on sequence length, $q$-uniqueness, or parity, and they spend evaluations our graph traversal gets for free by construction. We compare at matched NUPACK evaluation budget and report both structure-aware and score-only outcomes.
Why not just use seqwalk, since it is already fast and scalable? Because it solves a different, weaker problem: sequence symmetry minimization via Hamiltonian paths, with no reverse-complement quotient, no even-$q$ parity analysis, and — by its authors' own admission — no thermodynamic modeling Scalable design of orthogonal DNA barcode libraries. The experiment that settles it: run both at matched library size and measure NUPACK hairpin and cross-hybridization scores. Likewise, continuous generative approaches such as Dirichlet flow matching, which reached an MSE of 0.0269 on promoter design Dirichlet Flow Matching with Applications to DNA Sequence Design, optimize fitness but abandon the discrete non-repetition guarantees entirely; they are a complementary tool, not a substitute for the guarantee we need.
Proposed Experiments and Decisive Checks
Experiment one establishes ground truth: for even $q \in \{2,\dots,8\}$ on the DNA alphabet, compare our flow-based pure-topological mode against the reproduced ILP optimum and the analytical construction, reporting deletion counts, achieved lengths against the theoretical bound, and runtime. Experiment two tests scale: for $q \in \{10, 12, 14\}$, where the ILP does not finish, compare deletion counts against the analytical construction and the LP-relaxation lower bound, and measure wall-clock and memory against seqwalk's reported regime. Experiment three is the biophysical test: partition the resulting tours into oligo libraries and evaluate in NUPACK — hairpin probability, cross-hybridization, melting-temperature variance, and an $i$-value-style composite as used in the whale-optimizer study — against seqwalk and ICW libraries at matched size, with all aggregation parameters tuned on a held-out split of $q$ values and library instances. Experiment four is the decisive check on the core claim: a full sweep of $\alpha$ including the $\alpha = 1$ tuned-weighted-sum and uniform-penalty ablations, pre-registered so that the interpretation is fixed in advance — if non-linear aggregation does not beat the tuned linear baseline, that result is itself the finding, and the headline shifts to the solver. The proposal succeeds if it delivers near-minimal even-$q$ deletion sets at $q$ values no exact method can reach, sequences whose thermodynamic measurements beat the scalable baselines at matched length, and a clean, honest answer on whether parameterized aggregation earns its keep inside a combinatorial graph algorithm.
References
- Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs
- A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback
- Power mean pyramid scores for summarization evaluation
- FALCON: Feedback Adaptive Loop for Content-Based Retrieval
- Some q-Rung Dual Hesitant Fuzzy Heronian Mean Operators with Their Application to Multiple Attribute Group Decision-Making
- Pythagorean Fuzzy Interaction Muirhead Means with Their Application to Multi-Attribute Group Decision-Making
- Scalable design of orthogonal DNA barcode libraries
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Stable DNA Sequence Over Close-Ending and Pairing Sequences Constraint
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization
- Dirichlet Flow Matching with Applications to DNA Sequence Design