Coding sequence optimization runs faster and uses less memory
SparseDesign: Scaling Exact Coding-Sequence Design
Data Structures and Algorithms
Summary
Designing DNA sequences that code for the same proteins but fold into specific shapes is very hard and uses lots of computer time and memory. The authors introduce SparseDesign, a new way to cut down the number of possibilities the program checks without missing better solutions. This method speeds up the design process a lot and cuts memory use by more than 20 times on real protein examples. SparseDesign works well in practice, especially for natural proteins, enabling faster and more efficient genetic sequence design.
What this means in practice
- •For biotech software developers: Optimize coding sequences in gene design software more quickly and with lower memory use, enabling larger and more complex sequence engineering tasks.
- •For computational biology teams: Accelerate experiments requiring exact RNA folding and codon usage optimization for synthetic biology and protein engineering projects.
Authors
Hao Lin, Jingjin Yu
Abstract
Exact optimization of synonymous coding sequences under a joint folding-energy and codon-usage objective is limited by expensive dynamic-programming splits and large working sets. \textsc{SparseDesign} applies candidate sparsification to the multiloop recurrence of a Turner~2004 dangle-0 solver over a weighted codon automaton. A direct branch is retained only when it strictly improves on every partitionable or endpoint-unpaired realization of the same endpoint states. We prove equivalence to the dense recurrence in real arithmetic, under an explicit scalar branch-interface assumption. With $N$ automaton states, edge set $E$ and $Z$ retained candidates, multiloop work is $O(N^2+N|E|+NZ)$; worst-case time remains cubic for bounded-width automata and total memory remains quadratic. Endpoint ownership permits parallel candidate construction without locks. While synthetic stress families can benefit little from sparsification and exhibit near-quadratic candidate growth, natural proteins show substantial candidate-count reductions. In our 7,600-task campaign, the 2,000-protein human-table panel has median retention of only 3.53\% at $λ=0$ and 2.15\% at $λ=4$, corresponding to approximately 28.3-fold and 46.4-fold reductions relative to all feasible direct intervals. The primary performance experiments use an AMD EPYC 7313 server. For human Dp427c (11,031 nt, $λ=0$), 16-thread packed \textsc{SparseDesign} achieves five-run medians of 236.54 seconds wall-clock time and 14.43 GiB peak RSS. Compared with the single-thread local dense LinearDesign fork on the same server (4,912 seconds, 402.10 GiB RSS), this gives a 20.8-fold wall-clock speedup and a 27.9-fold peak-memory reduction. On a Core i9-14900KF commodity PC with 64 GiB RAM, the same input, layout and thread count achieve 126.42 seconds and 14.43 GiB RSS.