Source-linked AI summary
Algorithm for Optimized mRNA Design Improves Stability and Immunogenicity
He Zhang, Liang Zhang, Ang Lin, Congcong Xu, Ziyu Li, Kaibo Liu, Boxiang Liu, Xiaopin Ma, Fanfan Zhao, Weiguo Yao, Hangwen Li, David H. Mathews, Yujian Zhang, Liang Huang
TL;DR
mRNA design must address instability and the enormous synonymous-codon search space. LinearDesign applies lattice parsing with weighted DFAs to jointly optimize stability and codon usage, achieving practical runtimes and stronger experimental responses than a codon-optimized benchmark. Its in vivo antibody-response mechanism remains a hypothesis because functional half-lives beyond 24 hours were not measured.
Problem
The mRNA design problem has a prohibitively large search space, while effective design requires jointly optimizing stability and codon optimality.
Source: Formulations and Algorithms · p. 6, Discussion · p. 12Method
LinearDesign reduces mRNA design to lattice parsing over DFA representations and weighted DFAs, jointly optimizing stability and codon optimality without enumeration.
Source: Formulations and Algorithms · p. 6, Discussion · pp. 12–13Results
10.7 minutes for the SARS-CoV-2 Spike protein, with practical O(n^2) scaling, while the resulting vaccines elicited up to 23× higher antibody responses in vivo than the codon-optimized benchmark.
Source: Discussion · p. 13Takeaways & Limitations
LinearDesign enables exploration of highly stable and efficient mRNA designs beyond the previously reachable design space.
Source: Discussion · pp. 12–13The authors suspect longer functional half-lives beyond 24 hours explain higher antibody responses, but this mechanism was not directly measured.
Source: In vitro and In vivo Experimental… · p. 12
Abstract
from arXiv · showhide
Messenger RNA (mRNA) vaccines are being used for COVID-19, but still suffer from the critical issue of mRNA instability and degradation, which is a major obstacle in the storage, distribution, and efficacy of the vaccine. Previous work showed that optimizing secondary structure stability lengthens mRNA half-life, which, together with optimal codons, increases protein expression. Therefore, a principled mRNA design algorithm must optimize both structural stability and codon usage to improve mRNA efficiency. However, due to synonymous codons, the mRNA design space is prohibitively large, e.g., there are $\sim\!10^{632}$ mRNAs for the SARS-CoV-2 Spike protein, which poses insurmountable challenges to previous methods. Here we provide a surprisingly simple solution to this hard problem by reducing it to a classical problem in computational linguistics, where finding the optimal mRNA is akin to finding the most likely sentence among similar sounding alternatives. Our algorithm, named LinearDesign, takes only 11 minutes for the Spike protein, and can jointly optimize stability and codon usage. Experimentally, without chemical modification, our designs substantially improve mRNA half-life and protein expression in vitro, and dramatically increase antibody response by up to 23$\times$ in vivo, compared to the codon-optimized benchmark. Our work enables the exploration of highly stable and efficient designs that are previously unreachable and is a timely tool not only for vaccines but also for mRNA medicine encoding all therapeutic proteins (e.g., monoclonal antibodies and anti-cancer drugs).
Formulations and Algorithms
LinearDesign represents synonymous codon choices as a DFA and uses lattice parsing to find stable mRNAs without enumerating candidates. Weighted DFAs incorporate codon optimality so stability and codon usage can be optimized jointly.
Design Space Representation
- Each amino acid’s codon choices form a DFA, and concatenated paths represent all mRNA sequences encoding the target protein.Source: Formulations and Algorithms · p. 6
Objective 1 (Stability): Lattice Parsing
- Lattice parsing folds all sequences in the mRNA DFA simultaneously and selects the sequence with the lowest minimum folding free energy.Source: Formulations and Algorithms · pp. 4, 6
Linear-time Approximation
- Exact lattice parsing has worst-case O(n^3) time but scales O(n^2) in practical applications, while beam search provides a linear-time approximation.Source: Formulations and Algorithms · pp. 6–7
Adding Objective 2 (Codon Optimality): Lattice Parsing with Weighted DFAs
- Weighted DFAs assign each codon c a path cost −log w(c), making total path cost proportional to −log CAI for joint optimization with stability.Source: Formulations and Algorithms · p. 7
- The joint optimization is a weighted intersection between the stochastic grammar for stability and the weighted DFA for codon optimality.Source: Formulations and Algorithms · p. 7
In silico Results and Analysis
LinearDesign efficiently explores the stability–codon-optimality trade-off and identifies designs on the feasibility limit. Exact search scales quadratically in practice, while beam search accelerates long-sequence design with small reported error.
Runtime
- Exact LinearDesign scales quadratically with mRNA length in practical applications, and CAI integration is only ∼15% slower than MFE-only search.Source: In silico Results and Analysis · pp. 7–8
- The beam-search approximation error on the Spike protein is 1.2%, and the reported error stabilizes as sequence length increases.Source: In silico Results and Analysis · pp. 8–9
Stability–CAI Trade-off
- With GC-favoring human codon preferences, conventional codon optimization improves stability only slightly because codon and stability directions are largely orthogonal.Source: In silico Results and Analysis · p. 9
- For Spike and eGFP, LinearDesign finds the lowest MFE for each CAI and the highest CAI for each MFE, forming the feasibility limit.Source: In silico Results and Analysis · p. 9
- The optimally stable designs have MFEs 1.8× lower than optimal-CAI designs and mostly double-stranded secondary structures.Source: In silico Results and Analysis · p. 9
- With AU-rich codon preferences, codon optimization instead worsens stability.Source: In silico Results and Analysis · p. 9
In vitro and In vivo Experimental Results
Experiments with unmodified Spike mRNAs found that lower-MFE LinearDesign sequences were more chemically stable and generally expressed more protein than the codon-optimized baseline. In mice, LinearDesign vaccines produced substantially stronger antibody and T-cell responses.
UTR Compatibility
- Stable designs formed fewer base pairs with commonly used UTRs, suggesting effectiveness independent of UTR choice.Source: In vitro and In vivo Experimental… · p. 10
Chemical Stability
- Lower-MFE designs degraded more slowly than the codon-optimized baseline during storage in buffer.Source: In vitro and In vivo Experimental… · p. 10
- After day 4, design a retained 36.9% intact mRNA versus 2.8% for baseline h, while design g retained 18.1%.Source: In vitro and In vivo Experimental… · p. 10
Cellular Protein Expression
- After 24 hours in HEK-293 cells, 5 of 7 LinearDesign molecules showed substantially higher Spike protein expression than benchmark h.Source: In vitro and In vivo Experimental… · p. 11
- Designs d and g were 1.5× and 1.4× better than benchmark h, while the lowest-MFE design a was also 1.5× better.Source: In vitro and In vivo Experimental… · p. 11
In vivo Immunogenicity
- LinearDesign-generated vaccines elicited high binding IgG and neutralizing antibodies, whereas benchmark h induced none or low neutralizing antibodies.Source: In vitro and In vivo Experimental… · p. 12
- Vaccines containing LinearDesign mRNAs induced a robust Th1-biased antigen-specific T-cell response, unlike the benchmark comparison.Source: In vitro and In vivo Experimental… · p. 12
- Designs a–d produced 9∼20× higher neutralizing antibody titers and 19∼23× higher Spike-specific binding-antibody OD values than baseline h.Source: In vitro and In vivo Experimental… · p. 12
Discussion
The discussion presents LinearDesign as an efficient solution to the enormous mRNA design space, jointly optimizing stability and codon optimality. The resulting designs outperform codon-optimization benchmarks across vaccine-relevant attributes and extend to broader mRNA medicine applications.
Motivation
- The prohibitively large mRNA search space makes jointly optimizing structural stability and codon usage extremely challenging.The paper frames this challenge as especially important for vaccine development.Source: Discussion · p. 12
Method
- LinearDesign reformulates mRNA design as lattice parsing over deterministic finite automata, enabling joint optimization of stability and codon optimality.Weighted DFAs support codon-optimality objectives, and the framework can accommodate non-standard genetic codes.Source: Discussion · pp. 12–13
- O(n^2) scaling and a 10.7-minute runtime for the SARS-CoV-2 Spike protein make the approach practical for long mRNA sequences.An O(n)-time approximate variant is also provided to further accelerate design for long sequences.Source: Discussion · p. 13
Experimental results
- LinearDesign sequences surpassed the commonly used codon-optimization benchmark in chemical stability, translation efficiency, and immunogenicity.The sequences were comprehensively characterized, and four of seven designs showed large antibody improvements.Source: Discussion · p. 13
- 9∼20× increases in neutralizing antibody titers and 19∼23× increases in binding antibody levels were observed over the benchmark.These results were reported for four of seven designs.Source: Discussion · p. 13
Implications
- Without chemical modification, the designed mRNAs showed high stability, translation efficiency, and immunogenicity, while the algorithm remains compatible with chemical modification.The authors describe this compatibility as orthogonal, conditional on an available corresponding energy model.Source: Discussion · p. 13
- LinearDesign enables exploration of previously inaccessible stable and efficient sequences for vaccines and therapeutic proteins such as monoclonal antibodies and anti-cancer drugs.The paper presents it as a general and principled method for mRNA molecule design.Source: Discussion · p. 13
Methods
LinearDesign represents synonymous mRNA candidates with automata and reduces joint stability–codon optimization to weighted lattice parsing. The method combines RNA folding objectives with codon optimality while retaining practical computational scaling.
Joint optimization
- The joint objective combines minimum folding energy with a scaled codon-adaptation term controlled by λ.CAI is scaled because it remains bounded while MFE generally grows with sequence length.Source: §1 Details of LinearDesign Algorithm · pp. 18–19
Candidate representation
- A DFA concatenating amino-acid codon representations encodes all mRNA sequences that translate into a given protein.Each codon DFA uses nucleotide-labeled paths, and concatenation represents complete synonymous candidates.Source: §1 Details of LinearDesign Algorithm · p. 19
Stability optimization
- Lattice parsing extends CKY from one RNA sequence to all sequences represented by the mRNA DFA, finding the lowest-energy structure and corresponding sequence.RNA folding is represented by a weighted context-free grammar, whose derivation weights encode folding energy.Source: §1 Details of LinearDesign Algorithm · p. 20
Joint optimization
- LinearDesign solves the harder joint optimization of stability and codon optimality, including constraints such as adjacent codon-pair preferences.The DFA framework is described as general and extendable to additional coding constraints.Source: §1 Details of LinearDesign Algorithm · p. 24
Experimental outcome
- The designs improve chemical stability and protein expression in vitro, while corresponding vaccines elicit up to 23× higher antibody responses in vivo.These results are reported without chemical modification relative to the codon-optimized benchmark.Source: §1 Details of LinearDesign Algorithm · p. 24
Supplementary Figures and Tables
Figure S1 illustrates word-lattice parsing in natural-language processing through a sentence DFA, grammar, single-sentence parsing, and optimal-versus-non-optimal parses.
Panel A
- Panel A shows a word lattice, or sentence DFA, used for speech recognition.The lattice represents alternative word sequences for parsing.Source: Figure S1 · p. 28
Panel B
- Panel B presents a simplified language grammar used with the lattice.The grammar supplies the structural rules for parsing candidate sentences.Source: Figure S1 · p. 28
Panel C
- Panel C depicts single-sentence parsing with between-word indices as a special case of word-lattice parsing.This panel connects ordinary sentence parsing to the more general lattice representation.Source: Figure S1 · p. 28
Panel D
- Panel D compares the best parse for the optimal sentence “I like this meal” with the best parse for the non-optimal sentence “alike this veal”.Dashed blue arcs indicate the optimal parse, while dashed light-blue arcs indicate the non-optimal parse.Source: Figure S1 · p. 28
D mRNA DFA
The design algorithm represents synonymous mRNA candidates compactly with DFAs and uses lattice parsing to optimize folding stability, while weighted DFAs incorporate codon optimality. Beam pruning makes the joint search tractable across the candidate space.
D mRNA DFA
- An mRNA DFA compactly represents candidate sequences by composing codon DFAs, including a stop codon and coding constraints.The construction uses n = 3·(|p| + 1) as the mRNA length and builds a CAI-integrated DFA.Source: Figure S2 · p. 29, D mRNA DFA · p. 30
- Lattice parsing replaces a fixed input string with a DFA, allowing RNA folding grammars to identify the lowest-cost sequence and structure across candidates.Each string index becomes a DFA state, and spans correspond to paths between states.Source: Figure S2 · p. 29, D mRNA DFA · p. 29
- Joint stability and codon optimality are encoded by integrating CAI costs into the dynamic-programming updates over DFA states and spans.The algorithm minimizes combined weights and returns the best sequence–structure pair by backtrace.Source: D mRNA DFA · p. 31, Figure S3
- Beam pruning retains the top-b prefix-scoring states at each position, removing lower-scoring alternatives from the search.This pruning step is used in LinearDesign to control the number of states carried forward.Source: D mRNA DFA · pp. 31–32
- The framework can represent extended codons, modified nucleotides, alternative genetic codes, avoided codons, adjacent codon pairs, and restriction-enzyme recognition sequences.These constraints are represented through modified DFA constructions and codon partitions.Source: Figure S6 · p. 33, Figure S7 · p. 34