LinearPartition: linear-time approximation of RNA folding partition function and base-pairing probabilities
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
Motivation: 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. Results: 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 nt). 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). Availability and implementation: Code: http://github.com/LinearFold/LinearPartition; Server: http://linearfold.org/partition. Supplementary information: Supplementary data are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lorenz, R., Bernhart, S. H., Höner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P. F., & Hofacker, I. L. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-26 · Cited by 5,098
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 · cited 4×
“But our work differs from those efforts in the following ways: (i) our dynamic programming is left-to-right and theirs are bottom-up; (ii) our work guarantees linear runtime while theirs cannot; (iii) our search is inexact while theirs are exact.”
InfluentialSelf-citationXia, T., SantaLucia, J., Burkard, M. E., Kierzek, R., Schroeder, S. J., Jiao, X., Cox, C., & Turner, D. H. (1998) · Biochemistry · doi:10.1021/bi9809425 · Cited by 1,140
The chemical repertoire of natural ribozymes
Doudna, J. A., & Cech, T. R. (2002) · Nature · doi:10.1038/418222a · Cited by 745
NONCODE 2016: an informative and valuable data source of long non-coding RNAs
Zhao, Y., Li, H., Fang, S., Kang, Y., wu, W., Hao, Y., Li, Z., Bu, D., Sun, N., Zhang, M. Q., et al. (2016) · Nucleic Acids Research · doi:10.1093/nar/gkv1252 · Cited by 643
RNA Pseudoknot Prediction in Energy-Based Models
Lyngsø, R. B., & Pedersen, C. N. S. (2000) · Journal of Computational Biology · doi:10.1089/106652700750050862 · Cited by 359
LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search
Huang, L., Zhang, H., Deng, D., Zhao, K., Liu, K., Hendrix, D. A., & Mathews, D. H. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz375 · Cited by 207
Self-citation
Cited by
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., Sperberg, R. A. P., Huang, P.-S., Participants, E., & Das, R. (2020) · doi:10.1101/2020.08.22.262931 · Cited by 199
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
Multiple sequence alignment-based RNA language model and its application to structural inference
Zhang, Y., Lang, M., Jiang, J., Gao, Z., Xu, F., Litfin, T., Chen, K., Singh, J., Huang, X., Song, G., et al. (2024) · Nucleic Acids Research · doi:10.1093/nar/gkad1031 · Cited by 112
Differentiable partition function calculation for RNA
(2023) · doi:10.1093/nar/gkad1168 · Cited by 15
sincFold: end-to-end learning of short- and long-range interactions in RNA secondary structure
(2024) · doi:10.1093/bib/bbae271 · Cited by 14
mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers
Alevras, D., Metkar, M., Yamamoto, T., Kumar, V., Friedhoff, T., Park, J.-E., Takeori, M., LaDue, M., Davis, W., & Galda, A. (2024) · 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00064 · Cited by 14
Fukunaga, T., & Hamada, M. (2022) · Bioinformatics Advances · doi:10.1093/bioadv/vbac078 · Cited by 5
sincFold: end-to-end learning of short- and long-range interactions in RNA secondary structure
Bugnon, L. A., Di Persia, L., Gerard, M., Raad, J., Prochetto, S., Fenoy, E., Chorostecki, U., Ariel, F., Stegmayer, G., & Milone, D. H. (2023) · doi:10.1101/2023.10.10.561771 · Cited by 2
Metadata
- Authors
- Zhang, H., Zhang, L., Mathews, D. H., & Huang, L.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2020-07-01
- Volume
- 36
- Issue
- Supplement_1
- Pages
- i258-i267
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W3043664941
- Cited by
- 83
- References
- 7
- FWCI
- 2.77
- Type
- journal article
- Language
- en
- Open access
- hybrid
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.