Research Article
No access
Published Online: 26 March 2024

DERNA Enables Pareto Optimal RNA Design

Publication: Journal of Computational Biology
Volume 31, Issue Number 3

Abstract

The design of an RNA sequence v that encodes an input target protein sequence w is a crucial aspect of messenger RNA (mRNA) vaccine development. There are an exponential number of possible RNA sequences for a single target protein due to codon degeneracy. These potential RNA sequences can assume various secondary structure conformations, each with distinct minimum free energy (MFE), impacting thermodynamic stability and mRNA half-life. Furthermore, the presence of species-specific codon usage bias, quantified by the codon adaptation index (CAI), plays a vital role in translation efficiency. While earlier studies focused on optimizing either MFE or CAI, recent research has underscored the advantages of simultaneously optimizing both objectives. However, optimizing one objective comes at the expense of the other. In this work, we present the Pareto Optimal RNA Design problem, aiming to identify the set of Pareto optimal solutions for which no alternative solutions exist that exhibit better MFE and CAI values. Our algorithm DEsign RNA (DERNA) uses the weighted sum method to enumerate the Pareto front by optimizing convex combinations of both objectives. We use dynamic programming to solve each convex combination in O(|w|3) time and O(|w|2) space. Compared with a CDSfold, previous approach that only optimizes MFE, we show on a benchmark data set that DERNA obtains solutions with identical MFE but superior CAI. Moreover, we show that DERNA matches the performance in terms of solution quality of LinearDesign, a recent approach that similarly seeks to balance MFE and CAI. We conclude by demonstrating our method's potential for mRNA vaccine design for the SARS-CoV-2 spike protein.

Get full access to this article

View all available purchase options and get full access to this article.

REFERENCES

Cohen, B., and Skiena, S. 2003. Natural selection and algorithmic design of mRNA. J. Comput. Biol. 10, 419–432.
Cohon, J.L. 2004. Multiobjective Programming and Planning, volume 140. Courier Corporation.
Crommelin, D.J., Anchordoquy, T.J., Volkin, D.B., et al. 2021. Addressing the cold reality of mRNA vaccine stability. J. Pharm. Sci. 110, 997–1001.
Das, I., and Dennis, J.E. 1997. A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems. Struct. Optim. 14, 63–69.
Das, I., and Dennis, J.E. 1998. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J. Optim. 8, 631–657.
Ding, Y., Tang, Y., Kwok, C.K., et al. 2014. In vivo genome-wide profiling of RNA secondary structure reveals novel regulatory features. Nature 505, 696–700.
Freier, S.M., Kierzek, R., Jaeger, J.A., et al. 1986. Improved free-energy parameters for predictions of RNA duplex stability. Proc. Natl Acad. Sci. U. S. A. 83, 9373–9377.
Gingold, H., and Pilpel, Y. 2011. Determinants of translation efficiency and accuracy. Mol. Syst. Biol. 7, 481.
Grüning, B., Dale, R., Sjödin, A., et al. 2018. Bioconda: Sustainable and comprehensive software distribution for the life sciences. Nat. Methods, 15, 475–476.
Gustafsson, C., Govindarajan, S., and Minshull, J. 2004. Codon bias and heterologous protein expression. Trends Biotechnol. 22, 346–353.
He, Q., Gao, H., Tan, D., et al. 2022. mRNA cancer vaccines: Advances, trends and challenges. Acta Pharm. Sin. B, 12, 2969–2989.
Hofacker, I.L., Fontana, W., Stadler, P.F., et al. 1994. Fast folding and comparison of RNA secondary structures. Monatsh. Chem. 125, 167–167.
Huang, Y., Yang, C., Xu, X.-f., et al. 2020. Structural and functional properties of SARS-CoV-2 spike protein: Potential antivirus drug development for COVID-19. Acta Pharmacol. Sin. 41, 1141–1149.
Jaeger, J.A., Turner, D. H., and Zuker, M. 1989. Improved predictions of secondary structures for RNA. Proc. Natl Acad. Sci. U. S. A. 86, 7706–7710.
Kleinkauf, R., Mann, M., and Backofen, R. 2015. antaRNA: Ant colony-based RNA sequence design. Bioinformatics 31, 3114–3121.
Kozak, M. 1999. Initiation of translation in prokaryotes and eukaryotes. Gene 234, 187–208.
Lyngso, R.B., Zuker, M., and Pedersen, C. 1999. Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics 15, 440–445.
Mahase, E. 2020. Covid-19: Moderna vaccine is nearly 95% effective, trial involving high risk and elderly people shows. BMJ 371, m4471.
Mathews, D.H., Sabina, J., Zuker, M., et al. 1999. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol. 288, 911–940.
Mathews, D.H., Disney, M.D., Childs, J.L., et al. 2004. Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc. Natl Acad. Sci. U. S. A. 101, 7287–7292.
Mauger, D.M., Cabral, B.J., Presnyak, V., et al. 2019. mRNA structure regulates protein expression through changes in functional half-life. Proc. Natl Acad. Sci. U. S. A. 116, 24075–24083.
Meo, S., Bukhari, I., Akram, J., et al. 2021. COVID-19 vaccines: Comparison of biological, pharmacological characteristics and adverse effects of Pfizer/BioNTech and Moderna vaccines. Eur. Rev. Med. Pharmacol. Sci. 25, 1663–1669.
Nakamura, Y., Gojobori, T., and Ikemura, T. 2000. Codon usage tabulated from international DNA sequence databases: Status for the year 2000. Nucleic Acids Res. 28, 292–292.
Poznanović, S., Barrera-Cruz, F., Kirkpatrick, A., et al. 2020. The challenge of RNA branching prediction: A parametric analysis of multiloop initiation under thermodynamic optimization. J. Struct. Biol. 210, 107475.
Presnyak, V., Alhusaini, N., Chen, Y.-H., et al. 2015. Codon optimality is a major determinant of mRNA stability. Cell 160, 1111–1124.
Salvatori, G., Luberto, L., Maffei, M., et al. 2020. SARS-CoV-2 spike protein: An optimal immunological target for vaccines. J. Transl. Med. 18, 222.
Saule, C., and Giegerich, R. 2015. Pareto optimization in algebraic dynamic programming. Algorithms Mol. Biol. 10, 1–20.
Sharp, P.M., and Li, W.-H. 1987. The codon adaptation index-a measure of directional synonymous codon usage bias, and its potential applications. Nucleic Acids Res. 15, 1281–1295.
Shine, J., and Dalgarno, L. 1975. Determinant of cistron specificity in bacterial ribosomes. Nature 254, 34–38.
Terai, G., Kamegai, S., and Asai, K. 2016. CDSfold: An algorithm for designing a protein-coding sequence with the most stable secondary structure. Bioinformatics 32, 828–834.
The UniProt Consortium. 2022. UniProt: The universal protein knowledgebase in 2023. Nucleic Acids Res. 51(D1), D523–D531.
Tuller, T., and Zur, H. 2015. Multiple roles of the coding sequence 5’ end in gene expression regulation. Nucleic Acids Res. 43, 13–28.
Tuller, T., Waldman, Y.Y., Kupiec, M., et al. 2010. Translation efficiency is determined by both codon bias and folding energy. Proc. Natl Acad. Sci. U. S. A. 107, 3645–3650.
Turner, D.H., Sugimoto, N., and Freier, S.M. 1988. RNA structure prediction. Annu. Rev. Biophys. Biophys. Chem. 17, 167–192.
Vishweshwaraiah, Y.L., and Dokholyan, N.V. 2022. mRNA vaccines for cancer immunotherapy. Front. Immunol. 13:1029069.
Wan, Y., Qu, K., Zhang, Q.C., et al. 2014. Landscape and variation of RNA secondary structure across the human transcriptome. Nature 505, 706–709.
Wayment-Steele, H.K., Kim, D.S., Choe, C.A., et al. 2021. Theoretical basis for stabilizing messenger RNA through secondary structure design. Nucleic Acids Res. 49, 10604–10617.
Weinberg, D.E., Shah, P., Eichhorn, S.W., et al. 2016. Improved ribosome-footprint and mRNA measurements provide insights into dynamics and regulation of yeast translation. Cell Rep. 14, 1787–1799.
Zadeh, L. 1963. Optimality and non-scalar-valued performance criteria. IEEE Trans. Automat. Contr. 8, 59–60.
Zhang, H., Zhang, L., Lin, A., et al. 2023. Algorithm for optimized mRNA design improves stability and immunogenicity. Nature 621, 396–403.
Zuker, M., and Stiegler, P. 1981. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9, 133–148.

Information & Authors

Information

Published In

cover image Journal of Computational Biology
Journal of Computational Biology
Volume 31Issue Number 3March 2024
Pages: 179 - 196
PubMed: 38416637

History

Published online: 26 March 2024
Published in print: March 2024
Published ahead of print: 27 February 2024

Permissions

Request permissions for this article.

Authors

Affiliations

Xinyu Gu
Department of Computer Science and University of Illinois Urbana-Champaign, Urbana, Illinois, USA.
Department of Computer Science and University of Illinois Urbana-Champaign, Urbana, Illinois, USA.
Department of Computer Science and University of Illinois Urbana-Champaign, Urbana, Illinois, USA.
Cancer Center at Illinois, University of Illinois Urbana-Champaign, Urbana, Illinois, USA.

Notes

An earlier version of this article was published in WABI 2023 (doi: 10.4230/LIPIcs.WABI.2023.21).
Address correspondence to: Dr. Mohammed El-Kebir, Department of Computer Science, University of Illinois Urbana-Champaign, 201 N Goodwin Avenue, Urbana, IL 61801, USA [email protected]

Authors' Contributions

X.G.: Conceptualization, implementation, and formal analysis. Y.Q.: Conceptualization and formal analysis. M.E.-K.: Conceptualization, validation, and writing—review and editing.

Author Disclosure Statement

The authors declare they have no conflicting financial interests.

Funding Information

M.E-K. was supported by the National Science Foundation (CCF-2046488) as well as funding from the Cancer Center at Illinois.

Metrics & Citations

Metrics

Citations

Export citation

Select the format you want to export the citations of this publication.

View Options

Access content

To read the fulltext, please use one of the options below to sign in or purchase access.

Society Access

If you are a member of a society that has access to this content please log in via your society website and then return to this publication.

Restore your content access

Enter your email address to restore your content access:

Note: This functionality works only for purchases done as a guest. If you already have an account, log in to access the content to which you are entitled.

View options

PDF/EPUB

View PDF/EPUB

Full Text

View Full Text

Figures

Tables

Media

Share

Share

Copy the content Link

Share on social media

Back to Top