{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T16:00:27Z","timestamp":1776096027086,"version":"3.50.1"},"reference-count":58,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":12,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01 GM076485"],"award-info":[{"award-number":["R01 GM076485"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1817231"],"award-info":[{"award-number":["IIS-1817231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>RNA secondary structure prediction is widely used to understand RNA function. Recently, there has been a shift away from the classical minimum free energy methods to partition function-based methods that account for folding ensembles and can therefore estimate structure and base pair probabilities. However, the classical partition function algorithm scales cubically with sequence length, and is therefore prohibitively slow for long sequences. This slowness is even more severe than cubic-time free energy minimization due to a substantially larger constant factor in runtime.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Inspired by the success of our recent LinearFold algorithm that predicts the approximate minimum free energy structure in linear time, we design a similar linear-time heuristic algorithm, LinearPartition, to approximate the partition function and base-pairing probabilities, which is shown to be orders of magnitude faster than Vienna RNAfold and CONTRAfold (e.g. 2.5 days versus 1.3 min on a sequence with length 32 753\u2009nt). More interestingly, the resulting base-pairing probabilities are even better correlated with the ground-truth structures. LinearPartition also leads to a small accuracy improvement when used for downstream structure prediction on families with the longest length sequences (16S and 23S rRNAs), as well as a substantial improvement on long-distance base pairs (500+ nt apart).<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Code: http:\/\/github.com\/LinearFold\/LinearPartition; Server: http:\/\/linearfold.org\/partition.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa460","type":"journal-article","created":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T07:15:05Z","timestamp":1593760505000},"page":"i258-i267","source":"Crossref","is-referenced-by-count":76,"title":["LinearPartition: linear-time approximation of RNA folding partition function and base-pairing probabilities"],"prefix":"10.1093","volume":"36","author":[{"given":"He","family":"Zhang","sequence":"first","affiliation":[{"name":"Baidu Research , Sunnyvale, CA 94089, USA"},{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330, USA"}]},{"given":"Liang","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330, USA"}]},{"given":"David H","family":"Mathews","sequence":"additional","affiliation":[{"name":"Department of Biochemistry & Biophysics, University of Rochester Medical Center , Rochester, NY 48306, USA"},{"name":"Center for RNA Biology, University of Rochester Medical Center , Rochester, NY 48306, USA"},{"name":"Department of Biostatistics & Computational Biology, University of Rochester Medical Center , Rochester, NY 48306, USA"}]},{"given":"Liang","family":"Huang","sequence":"additional","affiliation":[{"name":"Baidu Research , Sunnyvale, CA 94089, USA"},{"name":"School of Electrical Engineering and Computer Science, Oregon State University , Corvallis, OR 97330, USA"}]}],"member":"286","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"2024021913332218300_btaa460-B8265828","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-139","article-title":"Ensemble-based prediction of RNA secondary structures","author":"Aghaeepour","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2024021913332218300_btaa460-B0883913","doi-asserted-by":"publisher","first-page":"i19","DOI":"10.1093\/bioinformatics\/btm223","article-title":"Efficient parameter estimation for RNA secondary structure prediction","author":"Andronescu","year":"2007","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B3","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1016\/S0300-9084(02)01402-5","article-title":"The expanding snoRNA world","volume":"84","author":"Bachellerie","year":"2002","journal-title":"Biochimie"},{"key":"2024021913332218300_btaa460-B4","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2010.09.001","article-title":"Sparse RNA folding: time and space efficient algorithms","volume":"9","author":"Backofen","year":"2011","journal-title":"J. Discrete Algorithms"},{"key":"2024021913332218300_btaa460-B5","doi-asserted-by":"crossref","first-page":"S132","DOI":"10.1121\/1.2017061","article-title":"Trainable grammars for speech recognition","volume":"65","author":"Baker","year":"1979","journal-title":"J. Acoust. Soc. Am"},{"key":"2024021913332218300_btaa460-B6","doi-asserted-by":"crossref","first-page":"1870","DOI":"10.1261\/rna.2125310","article-title":"Probknot: fast prediction of RNA secondary structure including pseudoknots","volume":"16","author":"Bellaousov","year":"2010","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B7","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1093\/bioinformatics\/btk014","article-title":"Local RNA base pairing probabilities in large sequences","volume":"22","author":"Bernhart","year":"2006","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-1-3","article-title":"Partition function and base pairing probabilities of RNA heterodimers","volume":"1","author":"Bernhart","year":"2006","journal-title":"Algorithms Mol. Biol"},{"key":"2024021913332218300_btaa460-B9","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-3-2","article-title":"The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs","volume":"3","author":"Cannone","year":"2002","journal-title":"BMC Bioinformatics"},{"key":"2024021913332218300_btaa460-B10","doi-asserted-by":"crossref","first-page":"i365","DOI":"10.1093\/bioinformatics\/btp212","article-title":"A partition function algorithm for interacting nucleic acid strands","volume":"25","author":"Chitsaz","year":"2009","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B11","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1089\/cmb.2013.0003","article-title":"An efficient algorithm for upper bound on the partition function of nucleic acids","volume":"20","author":"Chitsaz","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2024021913332218300_btaa460-B12","doi-asserted-by":"crossref","first-page":"e1004473","DOI":"10.1371\/journal.pcbi.1004473","article-title":"Rich RNA structure landscapes revealed by mutate-and-map analysis","volume":"11","author":"Cordero","year":"2015","journal-title":"PLoS Comput. Biol"},{"key":"2024021913332218300_btaa460-B13","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1093\/bioinformatics\/btv682","article-title":"AccessFold: predicting RNA-RNA interactions with consideration for competing self-structure","volume":"32","author":"DiChiacchio","year":"2016","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B14","doi-asserted-by":"crossref","first-page":"7280","DOI":"10.1093\/nar\/gkg938","article-title":"A statistical sampling algorithm for RNA secondary","volume":"31","author":"Ding","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/060651100","article-title":"Thermodynamic analysis of interacting nucleic acid strands","volume":"49","author":"Dirks","year":"2007","journal-title":"SIAM Rev"},{"key":"2024021913332218300_btaa460-B16","doi-asserted-by":"crossref","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":"2024021913332218300_btaa460-B17","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1038\/418222a","article-title":"The chemical repertoire of natural ribozymes","volume":"418","author":"Doudna","year":"2002","journal-title":"Nature"},{"key":"2024021913332218300_btaa460-B18","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1038\/35103511","article-title":"Non-coding RNA genes and the modern RNA world","volume":"2","author":"Eddy","year":"2001","journal-title":"Nat. Rev. Genet"},{"key":"2024021913332218300_btaa460-B19","doi-asserted-by":"crossref","first-page":"1769","DOI":"10.1261\/rna.2112110","article-title":"Turning limited experimental information into 3d models of RNA","volume":"16","author":"Flores","year":"2010","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B20","doi-asserted-by":"crossref","first-page":"e0130200","DOI":"10.1371\/journal.pone.0130200","article-title":"Discovery of novel ncRNA sequences in multiple genome alignments on the basis of conserved and stable secondary structures","volume":"10","author":"Fu","year":"2015","journal-title":"PLoS One"},{"key":"2024021913332218300_btaa460-B21","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":"2024021913332218300_btaa460-B22","first-page":"53","author":"Huang","year":"2005"},{"key":"2024021913332218300_btaa460-B23","first-page":"1077","author":"Huang","year":"2010"},{"key":"2024021913332218300_btaa460-B24","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":"2024021913332218300_btaa460-B25","doi-asserted-by":"crossref","first-page":"1104","DOI":"10.1006\/jmbi.1997.0889","article-title":"Assessing the reliability of RNA folding using statistical mechanics","volume":"267","author":"Huynen","year":"1997","journal-title":"J. Mol. Biol"},{"key":"2024021913332218300_btaa460-B26","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1093\/bioinformatics\/btm591","article-title":"Rfold: an exact algorithm for computing local base pairing probabilities","volume":"24","author":"Kiryu","year":"2008","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B27","doi-asserted-by":"crossref","first-page":"3423","DOI":"10.1093\/nar\/gkg614","article-title":"Pfold: RNA secondary structure prediction using stochastic context-free grammars","volume":"31","author":"Knudsen","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B28","doi-asserted-by":"crossref","first-page":"4328","DOI":"10.1038\/s41467-018-06792-z","article-title":"mRNAs and lncRNAs intrinsically form secondary structures with short end-to-end distances","volume":"9","author":"Lai","year":"2018","journal-title":"Nat. Commun"},{"key":"2024021913332218300_btaa460-B29","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1093\/nar\/gks181","article-title":"Global or local? Predicting secondary structure and accessibility in mRNAs","volume":"40","author":"Lange","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B30","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1038\/nsmb1226","article-title":"Potent effect of target structure on microRNA function","volume":"14","author":"Long","year":"2007","journal-title":"Nat. Struct. Mol. Biol"},{"key":"2024021913332218300_btaa460-B31","doi-asserted-by":"crossref","first-page":"1","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":"2024021913332218300_btaa460-B32","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1093\/nar\/gkm920","article-title":"Efficient siRNA selection using hybridization thermodynamics","volume":"36","author":"Lu","year":"2008","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B33","doi-asserted-by":"crossref","first-page":"1805","DOI":"10.1261\/rna.1643609","article-title":"Improved RNA secondary structure prediction by maximizing expected pair accuracy","volume":"15","author":"Lu","year":"2009","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B34","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1089\/106652700750050862","article-title":"RNA pseudoknot prediction in energy-based models","volume":"7","author":"Lyngs\u00f8","year":"2000","journal-title":"J. Comput. Biol"},{"key":"2024021913332218300_btaa460-B35","doi-asserted-by":"crossref","first-page":"5181","DOI":"10.1074\/jbc.REV118.005602","article-title":"Challenges and opportunities in cryo-EM single-particle analysis","volume":"294","author":"Lyumkis","year":"2019","journal-title":"J. Biol. Chem"},{"key":"2024021913332218300_btaa460-B36","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1261\/rna.7650904","article-title":"Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization","volume":"10","author":"Mathews","year":"2004","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B37","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/j.jmb.2006.01.067","article-title":"Revolutions in RNA secondary structure prediction","volume":"359","author":"Mathews","year":"2006","journal-title":"J. Mol. Biol"},{"key":"2024021913332218300_btaa460-B38","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.sbi.2006.05.010","article-title":"Prediction of RNA secondary structure by free energy minimization","volume":"16","author":"Mathews","year":"2006","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2024021913332218300_btaa460-B39","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol"},{"key":"2024021913332218300_btaa460-B40","doi-asserted-by":"crossref","first-page":"7287","DOI":"10.1073\/pnas.0401799101","article-title":"Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure","volume":"101","author":"Mathews","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2024021913332218300_btaa460-B41","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2024021913332218300_btaa460-B42","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1261\/rna.060368.116","article-title":"RNA-puzzles round III: 3D RNA structure prediction of five riboswitches and one ribozyme","volume":"23","author":"Miao","year":"2017","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B43","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","article-title":"Fast algorithm for predicting the secondary structure of single-stranded RNA","volume":"77","author":"Nussinov","year":"1980","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2024021913332218300_btaa460-B44","doi-asserted-by":"crossref","first-page":"D128","DOI":"10.1093\/nar\/gkw1008","article-title":"RNAcentral: a comprehensive database of non-coding RNA sequences","volume":"45","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B45","doi-asserted-by":"crossref","first-page":"i85","DOI":"10.1093\/bioinformatics\/btr215","article-title":"IpKnot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming","volume":"27","author":"Sato","year":"2011","journal-title":"Bioinformatics"},{"key":"2024021913332218300_btaa460-B46","doi-asserted-by":"crossref","first-page":"2232","DOI":"10.1002\/jcc.21806","article-title":"Automated RNA tertiary structure prediction from secondary structure and low-resolution restraints","volume":"32","author":"Seetin","year":"2011","journal-title":"J. Comp. Chem"},{"key":"2024021913332218300_btaa460-B47","doi-asserted-by":"crossref","first-page":"1808","DOI":"10.1261\/rna.053694.115","article-title":"Exact calculation of loop formation probability identifies folding motifs in RNA secondary structures","volume":"22","author":"Sloma","year":"2016","journal-title":"RNA"},{"key":"2024021913332218300_btaa460-B48","doi-asserted-by":"crossref","first-page":"e103","DOI":"10.1093\/nar\/gkq021","article-title":"DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model","volume":"38","author":"Sperschneider","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B49","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1038\/nbt1404","article-title":"The impact of target site accessibility on the design of effective siRNAs","volume":"26","author":"Tafer","year":"2008","journal-title":"Nat. Biotech"},{"key":"2024021913332218300_btaa460-B50","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/jmbi.1999.3001","article-title":"How RNA folds","volume":"293","author":"Tinoco","year":"1999","journal-title":"J. Mol. Biol"},{"key":"2024021913332218300_btaa460-B51","doi-asserted-by":"crossref","first-page":"14719","DOI":"10.1021\/bi9809425","article-title":"Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson Crick base pairs","volume":"37","author":"Xia","year":"1998","journal-title":"Biochemistry"},{"key":"2024021913332218300_btaa460-B52","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1002\/jcc.21633","article-title":"Nucleic acid sequence design via efficient ensemble defect optimization","volume":"32","author":"Zadeh","year":"2011","journal-title":"J. Comp. Chem"},{"key":"2024021913332218300_btaa460-B53","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.sbi.2014.02.001","article-title":"New molecular engineering approaches for crystallographic studies of large RNAs","volume":"26","author":"Zhang","year":"2014","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2024021913332218300_btaa460-B54","doi-asserted-by":"crossref","first-page":"e1541","DOI":"10.1002\/wrna.1541","article-title":"Advances that facilitate the study of large RNA structure and dynamics by nuclear magnetic resonance spectroscopy","volume":"10","author":"Zhang","year":"2019","journal-title":"Wiley Interdiscip. Rev"},{"key":"2024021913332218300_btaa460-B55","article-title":"ThreshKnot: Thresholded ProbKnot for improved RNA secondary structure prediction","author":"Zhang","year":"2019"},{"key":"2024021913332218300_btaa460-B56","doi-asserted-by":"crossref","first-page":"D203","DOI":"10.1093\/nar\/gkv1252","article-title":"Noncode 2016: an informative and valuable data source of long non-coding RNAs","volume":"44","author":"Zhao","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B57","doi-asserted-by":"crossref","first-page":"6168","DOI":"10.1093\/nar\/gkx170","article-title":"A sensitivity analysis of RNA folding nearest neighbor parameters identifies a subset of free energy parameters with the greatest impact on RNA secondary structure prediction","volume":"45","author":"Zuber","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2024021913332218300_btaa460-B58","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i258\/56702419\/bioinformatics_36_supplement1_i258.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i258\/56702419\/bioinformatics_36_supplement1_i258.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T08:41:54Z","timestamp":1708332114000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_1\/i258\/5870487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":58,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa460","relation":{"has-review":[{"id-type":"doi","id":"10.3410\/f.738321972.793576657","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,7]]},"published":{"date-parts":[[2020,7,1]]}}}