Natural Selection and Algorithmic Design of mRNA
Abstract
Messenger RNA (mRNA) sequences serve as templates for proteins according to the triplet code, in which each of the 4(3) = 64 different codons (sequences of three consecutive nucleotide bases) in RNA either terminate transcription or map to one of the 20 different amino acids (or residues) which build up proteins. Because there are more codons than residues, there is inherent redundancy in the coding. Certain residues (e.g., tryptophan) have only a single corresponding codon, while other residues (e.g., arginine) have as many as six corresponding codons. This freedom implies that the number of possible RNA sequences coding for a given protein grows exponentially in the length of the protein. Thus nature has wide latitude to select among mRNA sequences which are informationally equivalent, but structurally and energetically divergent. In this paper, we explore how nature takes advantage of this freedom and how to algorithmically design structures more energetically favorable than have been built through natural selection. In particular: (1) Natural Selection--we perform the first large-scale computational experiment comparing the stability of mRNA sequences from a variety of organisms to random synonymous sequences which respect the codon preferences of the organism. This experiment was conducted on over 27,000 sequences from 34 microbial species with 36 genomic structures. We provide evidence that in all genomic structures highly stable sequences are disproportionately abundant, and in 19 of 36 cases highly unstable sequences are disproportionately abundant. This suggests that the stability of mRNA sequences is subject to natural selection. (2) Artificial Selection--motivated by these biological results, we examine the algorithmic problem of designing the most stable and unstable mRNA sequences which code for a target protein. We give a polynomial-time dynamic programming solution to the most stable sequence problem (MSSP), which is asymptotically no more complex than secondary structure prediction. We show that the corresponding least stable sequence problem (LSSP) is NP-complete, and develop two heuristics for the construction of such sequences. We have implemented these algorithms, and present experimental results placing the high/low stability sequences in context with both wildtype and random encodings. Our implementation has already been applied to the design of RNA "code-words" creating little or no secondary structure in RNA computing (Brenneman and Condon, 2001; Marathe et al., 2001), and we anticipate a variety of other applications of this work to sequence design problems (Skiena, 2001).
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Two previous studies also tackled optimal-stability mRNA design via dynamic programming, but their algorithms are complicated, not generalizable and less efficient.
“Two previous studies22,23 also tackled the problem of optimal-stability mRNA design (that is, our objective 1) via dynamic programming, but their algorithms are complicated, not generalizable and less efficient.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [22]
Cohen et al. only optimize stability without considering codon optimality.
“First, Cohen et al. only optimize stability without considering codon optimality.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [22]
Cohen et al. and CDSfold do not have any graph-theoretic or formal representation of the design space.
“By contrast, Cohen et al. and CDSfold extend the standard Zuker algorithm with the consideration of amino acid constraints, and they do not have any graph-theoretic or formal representation of the design space.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [22]
The stability-only version of this work reduced the mRNA design problem to lattice parsing, resulting in a simpler and more efficient algorithm than previous specifically-designed algorithms.
“By contrast, the stability-only version of our work reduced the mRNA design problem to the classical computational linguistics problem of lattice parsing, resulting in a much simpler and more efficient algorithm that is vastly different from the specifically-designed algorithms such as the one described in Cohen et al.22 and CDSfold23.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [22]
Cites
Mathews, D. H., Sabina, J., Zuker, M., & Turner, D. H. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1999.2700 · Cited by 3,795 · see citing works
Fast folding and comparison of RNA secondary structures
Hofacker, I. L., Fontana, W., Stadler, P. F., Bonhoeffer, S., Tacker, M., & Schuster, P. M. (1994) · Monatshefte für Chemie - Chemical Monthly · doi:10.1007/bf00818163 · Cited by 2,314 · see citing works
Improved Estimation of Secondary Structure in Ribonucleic Acids
Tinoco, I., Borer, P. N., Dengler, B., Levine, M., Uhlenbeck, O. C., Crothers, D. M., & Gralla, J. D. (1973) · Nature New Biology · doi:10.1038/newbio246040a0 · Cited by 2,270 · see citing works
Bruijn, D. N. D. (1946) · TU/e Research Portal · Cited by 1,289 · see citing works
De Novo Protein Design: Fully Automated Sequence Selection
Dahiyat, B. I., & Mayo, S. L. (1997) · Science · doi:10.1126/science.278.5335.82 · Cited by 1,142 · see citing works
Algorithms and Thermodynamics for RNA Secondary Structure Prediction: A Practical Guide
Zuker, M., Mathews, D. H., & Turner, D. H. (1999) · Springer eBooks · doi:10.1007/978-94-011-4485-8_2 · Cited by 1,139 · see citing works
Improved predictions of secondary structures for RNA.
Jaeger, J. A., Turner, D. H., & Zuker, M. (1989) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.86.20.7706 · Cited by 817 · see citing works
Turner, D. H., Sugimoto, N., & Freier, S. M. (1988) · Annual Review of Biophysics and Biophysical Chemistry · doi:10.1146/annurev.bb.17.060188.001123 · Cited by 652 · see citing works
Consensus temporal order of amino acids and evolution of the triplet code
Trifonov, E. N. (2000) · Gene · doi:10.1016/s0378-1119(00)00476-5 · Cited by 327 · see citing works
The origins of life: from the birth of life to the origin of language
(1999) · Choice Reviews Online · doi:10.5860/choice.37-0933 · Cited by 270 · see citing works
On Combinatorial DNA Word Design
Marathe, A., Condon, A., & Corn, R. M. (2001) · Journal of Computational Biology · doi:10.1089/10665270152530818 · Cited by 234 · see citing works
Workman, C. T. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.24.4816 · Cited by 218 · see citing works
mRNAs have greater negative folding free energies than shuffled or codon choice randomized sequences
Seffens, W. S. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.7.1578 · Cited by 201 · see citing works
Good, I. J. (1946) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-21.3.167 · Cited by 200 · see citing works
Design of multistable RNA molecules
Christoph Flamm, A., Hofacker, I. L., Maurer‐Stroh, S., Stadler, P. F., & Zehl, M. (2001) · RNA · doi:10.1017/s1355838201000863 · Cited by 164 · see citing works
Oxender, D. L., Zurawski, G., & Yanofsky, C. (1979) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.76.11.5524 · Cited by 140 · see citing works
An energy model that predicts the correct folding of both the tRNA and the 5S RNA molecules
Papanicolaou, C., Gouy, M., & Ninio, J. (1984) · Nucleic Acids Research · doi:10.1093/nar/12.1part1.31 · Cited by 123 · see citing works
Forsdyke, D. R., & Mortimer, J. R. (2000) · Gene · doi:10.1016/s0378-1119(00)00472-8 · Cited by 104 · see citing works
Pseudoknots in RNA secondary structures
Lyngsø, R. B., & Pedersen, C. N. S. (2000) · doi:10.1145/332306.332551 · Cited by 104 · see citing works
Gradients in nucleotide and codon usage along Escherichia coli genes
Hooper, S. D. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.18.3517 · Cited by 72 · see citing works
Internal loops in RNA secondary structure prediction
Lyngsø, R. B., Zuker, M., & Pedersen, C. N. S. (1999) · doi:10.1145/299432.299490 · Cited by 46 · see citing works
Skiena, S. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.suppl_1.s253 · Cited by 25 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Hearing silence: non-neutral evolution at synonymous sites in mammals
Chamary, J., Parmley, J. L., & Hurst, L. D. (2006) · Nature Reviews Genetics · doi:10.1038/nrg1770 · Cited by 827 · see citing works
Algorithm for optimized mRNA design improves stability and immunogenicity
Zhang, H., Zhang, L., Lin, A., Xu, C., Li, Z., Liu, K., Liu, B., Ma, X., Zhao, F., Jiang, H., et al. (2023) · Nature · doi:10.1038/s41586-023-06127-z · Cited by 498 · see citing works
Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics
Leppek, K., Byeon, G. W., Kladwang, W., Wayment-Steele, H. K., Kerr, C. H., Xu, A. F., Kim, D. S., Topkar, V. V., Choe, C., Rothschild, D., et al. (2022) · Nature Communications · doi:10.1038/s41467-022-28776-w · Cited by 399 · see citing works
Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics
Leppek, K., Byeon, G. W., Kladwang, W., Wayment-Steele, H. K., Kerr, C. H., Xu, A. F., Kim, D. S., Topkar, V. V., Choe, C., Rothschild, D., et al. (2021) · doi:10.1101/2021.03.29.437587 · Cited by 399 · see citing works
Chamary, J., & Hurst, L. D. (2005) · Genome biology · doi:10.1186/gb-2005-6-9-r75 · Cited by 332 · see citing works
Theoretical basis for stabilizing messenger RNA through secondary structure design
Wayment-Steele, H. K., Kim, D. S., Choe, C. A., Nicol, J. J., Wellington-Oguri, R., Watkins, A. M., Parra Sperberg, R. A., Huang, P.-S., Participants, E., & Das, R. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab764 · Cited by 197 · see citing works
How do synonymous mutations affect fitness?
Parmley, J. L., & Hurst, L. D. (2007) · BioEssays · doi:10.1002/bies.20592 · Cited by 142 · see citing works
Computational Tools and Algorithms for Designing Customized Synthetic Genes
Gould, N., Hendy, O., & Papamichail, D. (2014) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2014.00041 · Cited by 97 · see citing works
Chamary, J., & Hurst, L. D. (2004) · Molecular Biology and Evolution · doi:10.1093/molbev/msh087 · Cited by 94 · see citing works
Comparative context analysis of codon pairs on an ORFeome scale
Moura, G., Pinheiro, M., Silva, R., Miranda, I., Afreixo, V., Dias, G., Freitas, A., Oliveira, J. L., & Santos, M. A. (2005) · Genome Biology · doi:10.1186/gb-2005-6-3-r28 · Cited by 90 · see citing works
Design of RNAs: comparing programs for inverse RNA folding
Churkin, A., Retwitzer, M. D., Reinharz, V., Ponty, Y., Waldispühl, J., & Barash, D. (2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbw120 · Cited by 81 · see citing works
Kis, Z. (2022) · Pharmaceutics · doi:10.3390/pharmaceutics14020430 · Cited by 83 · see citing works
Purine loading, stem-loops and Chargaff's second parity rule
Forsdyke, D. R., & Bell, S. J. (2004) · Applied Bioinformatics · doi:10.2165/00822942-200403010-00002 · Cited by 53 · see citing works
Computational design of mRNA vaccines
Kim, Y.-A., Mousavi, K., Yazdi, A. K., Zwierzyna, M., Cardinali, M., Fox, D. M., Peel, T., Coller, J., Aggarwal, K., & Maruggi, G. (2023) · Vaccine · doi:10.1016/j.vaccine.2023.07.024 · Cited by 47 · see citing works
Selection Acts on DNA Secondary Structures to Decrease Transcriptional Mutagenesis
Hoede, C., Denamur, É., & Tenaillon, O. (2006) · PLoS Genetics · doi:10.1371/journal.pgen.0020176 · Cited by 41 · see citing works
Clote, P. (2005) · Journal of Computational Biology · doi:10.1089/cmb.2005.12.83 · Cited by 39 · see citing works
Wu, X., Jia, W., Zhang, J., Li, X., Pan, C., Lei, C., Chen, H., Dang, R., & Lan, X. (2014) · Small Ruminant Research · doi:10.1016/j.smallrumres.2014.09.002 · Cited by 26 · see citing works
Second eigenvalue of the Laplacian matrix for predicting RNA conformational switch by mutation
Barash, D. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth157 · Cited by 26 · see citing works
incaRNAfbinv: a web server for the fragment-based design of RNA sequences
Retwitzer, M. D., Reinharz, V., Ponty, Y., Waldispühl, J., & Barash, D. (2016) · Nucleic Acids Research · doi:10.1093/nar/gkw440 · Cited by 18 · see citing works
DERNA Enables Pareto Optimal RNA Design
Gu, X., Qi, Y., & El-Kebir, M. (2024) · Journal of Computational Biology · doi:10.1089/cmb.2023.0283 · Cited by 14 · see citing works
POSITIVE DARWINIAN SELECTION: DOES THE COMPARATIVE METHOD RULE?
Forsdyke, D. R. (2007) · Journal of Biological Systems · doi:10.1142/s0218339007002039 · Cited by 13 · see citing works
In Silico Design of Small RNA Switches
Avihoo, A., Gabdank, I., Shapira, M., & Barash, D. (2007) · IEEE Transactions on NanoBioscience · doi:10.1109/tnb.2007.891894 · Cited by 13 · see citing works
mRNA folding algorithms for structure and codon optimization
Ward, M., Richardson, M. O. G., & Metkar, M. (2025) · Briefings in Bioinformatics · doi:10.1093/bib/bbaf386 · Cited by 10 · see citing works
LinearDesign: Efficient Algorithms for Optimized mRNA Sequence DesignPreprint
Zhang, H., Zhang, L., Li, Z., Liu, K., Liu, B., Mathews, D. H., & Huang, L. (2020) · arXiv (Cornell University) · Cited by 8 · see citing works
Codon optimization by 0-1 linear programming
Arbib, C., Pınar, M. Ç., Rossi, F., & Tessitore, A. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2020.104932 · Cited by 5 · see citing works
Two Proteins for the Price of One: The Design of Maximally Compressed Coding Sequences
Wang, B., Papamichail, D., Mueller, S., & Skiena, S. (2006) · Lecture notes in computer science · doi:10.1007/11753681_31 · Cited by 4 · see citing works
Self-citationSynthetic Biology Approaches for Vaccine Development
Shen, S. H., Futcher, B., Yang, C., & Wimmer, E. (2014) · Wiley-VCH eBooks · doi:10.1002/3527600906.mcb.20120059 · Cited by 3 · see citing works
Dai, N., Zhou, T., Tang, W. Y., Mathews, D. H., & Huang, L. (2025) · Bioinformatics · doi:10.1093/bioinformatics/btaf245 · Cited by 4 · see citing works
Two proteins for the price of one: the design of maximally compressed coding sequences
Wang, B., Papamichail, D., Mueller, S., & Skiena, S. (2006) · Natural Computing · doi:10.1007/s11047-006-9031-7 · Cited by 2 · see citing works
Self-citationJu, Y.-R., Cho, L.-S., & Lu, C. L. (2025) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbbio.2025.3596771 · Cited by 1 · see citing works
RNA design: update on computational frameworks and programs for inverse RNA folding
Mukherjee, S., Zakh, R., Churkin, A., & Barash, D. (2026) · Briefings in Bioinformatics · doi:10.1093/bib/bbag327 · Cited by 1 · see citing works
Designing RNA Secondary Structures in Coding Regions
Yeasmin, R., & Skiena, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30191-9_28 · Cited by 1 · see citing works
Self-citationWard, M., Richardson, M. O. G., Lin, H., Stamm, M., Wright, K., Kim, A., Bicknell, A. A., Ahmed, N., Jones, A. K., Davis, J. W., et al. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.01.23.701221 · Cited by 1 · see citing works
Analysis and design of genomic sequences
Papamichail, D. (2007) · SUNY Digital Repository Support (State University of New York System)
A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem
Cho, L.-S., Chang, K.-W., & Lu, C. L. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-0218-9_24
Fine-scale structural information substantially improves mRNA therapeutic stability prediction
Yi, S., Ali, S. E., Jadeja, Y., Davis, J. W., & Metkar, M. (2026) · Molecular Therapy — Nucleic Acids · doi:10.1016/j.omtn.2026.102960
- Authors
- Cohen, B., & Skiena, S.
- Affiliations
- New Jersey Institute of Technology (US)
- Stony Brook University (US)
- ORCID
- Skiena, Steven
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2003-06
- Volume
- 10
- Issue
- 3-4
- Pages
- 419-432
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- OpenAlex
- W2039590841
- Cited by
- 35
- References
- 22
- Citations by year
- 2026: 3 · 2025: 4 · 2024: 1 · 2023: 2 · 2022: 2 · 2021: 1 · 2020: 2 · 2016: 2 · 2014: 3 · 2012: 1
- FWCI
- 1.15
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of Computational Biology (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Keywords
- codon usage, synonymous codons, mRNA stability, natural selection, selective breeding, NP-completeness, dynamic programming, RNA secondary structure, codon redundancy, microbial genomes
- MeSH terms
- Algorithms, Data Interpretation, Statistical, Nucleic Acid Conformation, RNA, Messenger, Selection, Genetic, Sequence Analysis, RNA, Evolution, Molecular, Computational Biology
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
