  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).
