Linear-Time Algorithms for RNA Structure Prediction

Overview

Journal Methods Mol Biol

Specialty Molecular Biology

Date 2023 Jan 27

PMID 36705896

Authors

He Zhang

Liang Zhang

Kaibo Liu

Sizhen Li

David H Mathews

Liang Huang

Affiliations

Soon will be listed here.

Abstract

RNA secondary structure prediction is widely used to understand RNA function. Existing dynamic programming-based algorithms, both the classical minimum free energy (MFE) methods and partition function methods, suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications. Inspired by incremental parsing for context-free grammars in computational linguistics, we designed linear-time heuristic algorithms, LinearFold and LinearPartition, to approximate the MFE structure, partition function and base pairing probabilities. These programs are orders of magnitude faster than Vienna RNAfold and CONTRAfold on long sequences. More interestingly, LinearFold and LinearPartition lead to more accurate predictions on the longest sequence families for which the structures are well established (16S and 23S Ribosomal RNAs), as well as improved accuracies for long-range base pairs (500 + nucleotides apart). This chapter provides protocols for using LinearFold and LinearPartition for secondary structure prediction.

Citing Articles

SARS-CoV-2 CoCoPUTs: analyzing GISAID and NCBI data to obtain codon statistics, mutations, and free energy over a multiyear period.

Padhiar N, Ghazanchyan T, Fumagalli S, DiCuccio M, Cohen G, Ginzburg A Virus Evol. 2025; 11(1):veae115.

PMID: 39882309 PMC: 11776705. DOI: 10.1093/ve/veae115.

mRNA vaccine sequence and structure design and optimization: Advances and challenges.

Jin L, Zhou Y, Zhang S, Chen S J Biol Chem. 2024; 301(1):108015.

PMID: 39608721 PMC: 11728972. DOI: 10.1016/j.jbc.2024.108015.

References

Bachellerie J, Cavaille J, Huttenhofer A . The expanding snoRNA world. Biochimie. 2002; 84(8):775-90. DOI: 10.1016/s0300-9084(02)01402-5. View

Bellaousov S, Mathews D . ProbKnot: fast prediction of RNA secondary structure including pseudoknots. RNA. 2010; 16(10):1870-80. PMC: 2941096. DOI: 10.1261/rna.2125310. View

Bernhart S, Hofacker I, Stadler P . Local RNA base pairing probabilities in large sequences. Bioinformatics. 2005; 22(5):614-5. DOI: 10.1093/bioinformatics/btk014. View

Clote P, Ponty Y, Steyaert J . Expected distance between terminal nucleotides of RNA secondary structures. J Math Biol. 2011; 65(3):581-99. DOI: 10.1007/s00285-011-0467-8. View

Ding Y, Lawrence C . A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 2003; 31(24):7280-301. PMC: 297010. DOI: 10.1093/nar/gkg938. View

Do C, Woods D, Batzoglou S . CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics. 2006; 22(14):e90-8. DOI: 10.1093/bioinformatics/btl246. View

Doudna J, Cech T . The chemical repertoire of natural ribozymes. Nature. 2002; 418(6894):222-8. DOI: 10.1038/418222a. View

Eddy S . Non-coding RNA genes and the modern RNA world. Nat Rev Genet. 2001; 2(12):919-29. DOI: 10.1038/35103511. View

Huang L, Zhang H, Deng D, Zhao K, Liu K, Hendrix D . LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search. Bioinformatics. 2019; 35(14):i295-i304. PMC: 6681470. DOI: 10.1093/bioinformatics/btz375. View

10.

Kerpedjiev P, Hammer S, Hofacker I . Forna (force-directed RNA): Simple and effective online RNA secondary structure diagrams. Bioinformatics. 2015; 31(20):3377-9. PMC: 4595900. DOI: 10.1093/bioinformatics/btv372. View

11.

Kiryu H, Kin T, Asai K . Rfold: an exact algorithm for computing local base pairing probabilities. Bioinformatics. 2007; 24(3):367-73. DOI: 10.1093/bioinformatics/btm591. View

12.

Knudsen B, Hein J . Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. 2003; 31(13):3423-8. PMC: 169020. DOI: 10.1093/nar/gkg614. View

13.

Lange S, Maticzka D, Mohl M, Gagnon J, Brown C, Backofen R . Global or local? Predicting secondary structure and accessibility in mRNAs. Nucleic Acids Res. 2012; 40(12):5215-26. PMC: 3384308. DOI: 10.1093/nar/gks181. View

14.

Leija-Martinez N, Casas-Flores S, Cadena-Nava R, Roca J, Mendez-Cabanas J, Gomez E . The separation between the 5'-3' ends in long RNA molecules is short and nearly constant. Nucleic Acids Res. 2014; 42(22):13963-8. PMC: 4267660. DOI: 10.1093/nar/gku1249. View

15.

Li T, Reidys C . The Rainbow Spectrum of RNA Secondary Structures. Bull Math Biol. 2018; 80(6):1514-1538. DOI: 10.1007/s11538-018-0411-9. View

16.

Lu Z, Gloor J, Mathews D . Improved RNA secondary structure prediction by maximizing expected pair accuracy. RNA. 2009; 15(10):1805-13. PMC: 2743040. DOI: 10.1261/rna.1643609. View

17.

Lyumkis D . Challenges and opportunities in cryo-EM single-particle analysis. J Biol Chem. 2019; 294(13):5181-5197. PMC: 6442032. DOI: 10.1074/jbc.REV118.005602. View

18.

Mathews D . Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization. RNA. 2004; 10(8):1178-90. PMC: 1370608. DOI: 10.1261/rna.7650904. View

19.

Mathews D . Revolutions in RNA secondary structure prediction. J Mol Biol. 2006; 359(3):526-32. DOI: 10.1016/j.jmb.2006.01.067. View

20.

Mathews D, Turner D . Prediction of RNA secondary structure by free energy minimization. Curr Opin Struct Biol. 2006; 16(3):270-8. DOI: 10.1016/j.sbi.2006.05.010. View