{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T07:00:25Z","timestamp":1776322825735,"version":"3.50.1"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T00:00:00Z","timestamp":1752537600000},"content-version":"vor","delay-in-days":14,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2330737"],"award-info":[{"award-number":["2330737"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2009071"],"award-info":[{"award-number":["2009071"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The task of designing optimized messenger RNA (mRNA) sequences has received much attention in recent years, thanks to breakthroughs in mRNA vaccines during the COVID-19 pandemic. Because most previous work aimed to minimize the minimum free energy (MFE) of the mRNA in order to improve stability and protein expression, which only considers one particular structure per mRNA sequence, millions of alternative conformations in equilibrium are neglected. More importantly, we prefer an mRNA to populate multiple stable structures and be flexible among them during translation when the ribosome unwinds it.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Therefore, we consider a new objective to minimize the ensemble free energy of an mRNA, which includes all possible structures in its Boltzmann ensemble. However, this new problem is much harder to solve than the original MFE optimization. To address the increased complexity of this problem, we introduce EnsembleDesign, a novel algorithm that employs continuous relaxation to optimize the expected ensemble free energy over a distribution of candidate sequences. EnsembleDesign extends both the lattice representation of the design space and the dynamic programming algorithm from LinearDesign to their probabilistic counterparts. Our algorithm consistently outperforms LinearDesign in terms of ensemble free energy, especially on long sequences. Interestingly, as byproducts, our designs also enjoy lower average unpaired probabilities (which correlates with degradation) and flatter Boltzmann ensembles (more flexibility between conformations).<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Our code is available on: https:\/\/github.com\/LinearFold\/EnsembleDesign.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf245","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T13:02:53Z","timestamp":1752584573000},"page":"i391-i400","source":"Crossref","is-referenced-by-count":2,"title":["EnsembleDesign: messenger RNA design minimizing ensemble free energy via probabilistic lattice parsing"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9925-7874","authenticated-orcid":false,"given":"Ning","family":"Dai","sequence":"first","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4804-0825","authenticated-orcid":false,"given":"Tianshuo","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1141-9479","authenticated-orcid":false,"given":"Wei Yu","family":"Tang","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2907-6557","authenticated-orcid":false,"given":"David H","family":"Mathews","sequence":"additional","affiliation":[{"name":"Department of Biochemistry and Biophysics, University of Rochester Medical Center , Rochester, NY 14642,","place":["United States"]},{"name":"Center for RNA Biology, University of Rochester Medical Center , Rochester, NY 14642,","place":["United States"]},{"name":"Department of Biostatistics and Computational Biology, University of Rochester Medical Center , Rochester, NY 14642,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6444-7045","authenticated-orcid":false,"given":"Liang","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330,","place":["United States"]},{"name":"Department of Biochemistry and Biophysics, Oregon State University , Corvallis, OR 97330,","place":["United States"]}]}],"member":"286","published-online":{"date-parts":[[2025,7,15]]},"reference":[{"key":"2025071509024487000_btaf245-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1056\/NEJMoa2035389","article-title":"Efficacy and safety of the mRNA-1273 SARS-CoV-2 vaccine","volume":"384","author":"Baden","year":"2021","journal-title":"N Engl J Med"},{"key":"2025071509024487000_btaf245-B2","first-page":"143","article-title":"On formal properties of simple phrase structure grammars","volume":"14","author":"Bar-Hillel","year":"1961","journal-title":"STUF Lang Typol Universals"},{"key":"2025071509024487000_btaf245-B3","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1089\/10665270360688101","article-title":"Natural selection and algorithmic design of mRNA","volume":"10","author":"Cohen","year":"2003","journal-title":"J Comput Biol"},{"key":"2025071509024487000_btaf245-B4","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2022"},{"key":"2025071509024487000_btaf245-B5","doi-asserted-by":"publisher","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","article-title":"CONTRAfold: RNA secondary structure prediction without physics-based models","volume":"22","author":"Do","year":"2006","journal-title":"Bioinformatics"},{"key":"2025071509024487000_btaf245-B6","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1038\/nature04530","article-title":"Endonucleolytic cleavage of eukaryotic mRNAs with stalls in translation elongation","volume":"440","author":"Doma","year":"2006","journal-title":"Nature"},{"key":"2025071509024487000_btaf245-B7","doi-asserted-by":"crossref","DOI":"10.18653\/v1\/W16-5901","article-title":"Inside-outside and forward-backward algorithms are just backprop (tutorial paper). In:","author":"Eisner","year":"2016","journal-title":"Proceedings of the Workshop on Structured Prediction for NLP"},{"key":"2025071509024487000_btaf245-B8","doi-asserted-by":"crossref","first-page":"e0137859","DOI":"10.1371\/journal.pone.0137859","article-title":"RNA thermodynamic structural entropy","volume":"10","author":"Garcia-Martin","year":"2015","journal-title":"PLoS One"},{"key":"2025071509024487000_btaf245-B9","author":"Huang","year":"2008"},{"key":"2025071509024487000_btaf245-B10","doi-asserted-by":"crossref","first-page":"i295","DOI":"10.1093\/bioinformatics\/btz375","article-title":"LinearFold: linear-time approximate RNA folding by 5\u2019-to-3\u2019 dynamic programming and beam search","volume":"35","author":"Huang","year":"2019","journal-title":"Bioinformatics"},{"key":"2025071509024487000_btaf245-B11","doi-asserted-by":"publisher","author":"Krueger","year":"2024","DOI":"10.1101\/2024.05.29.594436"},{"key":"2025071509024487000_btaf245-B12","doi-asserted-by":"crossref","first-page":"1536","DOI":"10.1038\/s41467-022-28776-w","article-title":"Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics","volume":"13","author":"Leppek","year":"2022","journal-title":"Nat Comm"},{"key":"2025071509024487000_btaf245-B13","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1186\/1748-7188-6-26","article-title":"Viennarna package 2.0","volume":"6","author":"Lorenz","year":"2011","journal-title":"Algorithms Mol Biol"},{"key":"2025071509024487000_btaf245-B14","doi-asserted-by":"crossref","first-page":"e14","DOI":"10.1093\/nar\/gkad1168","article-title":"Differentiable partition function calculation for RNA","volume":"52","author":"Matthies","year":"2024","journal-title":"Nucleic Acids Res"},{"key":"2025071509024487000_btaf245-B15","doi-asserted-by":"crossref","first-page":"24075","DOI":"10.1073\/pnas.1908052116","article-title":"mRNA structure regulates protein expression through changes in functional half-life","volume":"116","author":"Mauger","year":"2019","journal-title":"Proc Natl Acad Sci U S A"},{"key":"2025071509024487000_btaf245-B16","doi-asserted-by":"crossref","first-page":"2603","DOI":"10.1056\/NEJMoa2034577","article-title":"Safety and efficacy of the BNT162b2 mRNA covid-19 vaccine","volume":"383","author":"Polack","year":"2020","journal-title":"N Engl J Med"},{"key":"2025071509024487000_btaf245-B17","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1093\/bioinformatics\/btv678","article-title":"CDSfold: an algorithm for designing a protein-coding sequence with the most stable secondary structure","volume":"32","author":"Terai","year":"2016","journal-title":"Bioinformatics"},{"key":"2025071509024487000_btaf245-B18","first-page":"D523. D531","article-title":"Uniprot: the universal protein knowledgebase in 2023","volume":"51","author":"The UniProt Consortium","year":"2022","journal-title":"Nucleic Acids Res"},{"key":"2025071509024487000_btaf245-B19","doi-asserted-by":"crossref","first-page":"D280","DOI":"10.1093\/nar\/gkp892","article-title":"NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure","volume":"38","author":"Turner","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2025071509024487000_btaf245-B20","doi-asserted-by":"crossref","first-page":"10604","DOI":"10.1093\/nar\/gkab764","article-title":"Theoretical basis for stabilizing messenger RNA through secondary structure design","volume":"49","author":"Wayment-Steele","year":"2021","journal-title":"Nucleic Acids Res"},{"key":"2025071509024487000_btaf245-B21","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1038\/s41586-020-2008-3","article-title":"A new coronavirus associated with human respiratory disease in China","volume":"579","author":"Wu","year":"2020","journal-title":"Nature"},{"key":"2025071509024487000_btaf245-B22","doi-asserted-by":"crossref","first-page":"870","DOI":"10.1016\/j.cell.2015.02.003","article-title":"Ribosome excursions during mRNA translocation mediate broad branching of frameshift pathways","volume":"160","author":"Yan","year":"2015","journal-title":"Cell"},{"key":"2025071509024487000_btaf245-B23","doi-asserted-by":"crossref","first-page":"i258","DOI":"10.1093\/bioinformatics\/btaa460","article-title":"LinearPartition: linear-time approximation of RNA folding partition function and base-pairing probabilities","volume":"36","author":"Zhang","year":"2020","journal-title":"Bioinformatics"},{"key":"2025071509024487000_btaf245-B24","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/s41586-023-06127-z","article-title":"Algorithm for optimized mRNA design improves stability and immunogenicity","volume":"621","author":"Zhang","year":"2023","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/Supplement_1\/i391\/63745640\/btaf245.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/Supplement_1\/i391\/63745640\/btaf245.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T13:02:56Z","timestamp":1752584576000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/41\/Supplement_1\/i391\/8199398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,1]]},"references-count":24,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2025,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf245","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,7]]},"published":{"date-parts":[[2025,7,1]]}}}