LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search
Open accessAbstract
Motivation: Predicting the secondary structure of an ribonucleic acid (RNA) sequence is useful in many applications. Existing algorithms [based on dynamic programming] suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications. Results: We present a novel alternative O(n3)-time dynamic programming algorithm for RNA folding that is amenable to heuristics that make it run in O(n) time and O(n) space, while producing a high-quality approximation to the optimal solution. Inspired by incremental parsing for context-free grammars in computational linguistics, our alternative dynamic programming algorithm scans the sequence in a left-to-right (5′-to-3′) direction rather than in a bottom-up fashion, which allows us to employ the effective beam pruning heuristic. Our work, though inexact, is the first RNA folding algorithm to achieve linear runtime (and linear space) without imposing constraints on the output structure. Surprisingly, our approximate search results in even higher overall accuracy on a diverse database of sequences with known structures. More interestingly, it leads to significantly more accurate predictions on the longest sequence families in that database (16S and 23S Ribosomal RNAs), as well as improved accuracies for long-range base pairs (500+ nucleotides apart), both of which are well known to be challenging for the current models. Availability and implementation: Our source code is available at https://github.com/LinearFold/LinearFold, and our webserver is at http://linearfold.org (sequence limit: 100 000nt). Supplementary information: Supplementary data are available at Bioinformatics online.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The left-to-right dynamic programming is equivalent to the bottom-up version but explores the search space incrementally from left to right.
“Inspired by our previous work, LinearFold21, we further developed a left-to-right dynamic programming, which is equivalent to the above bottom-up version but explores the search space incrementally from left to right”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [21]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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 · cited 4× · see citing works
“Widely used systems such as RNAstructure (Mathews and Turner, 2006), Vienna RNAfold (Lorenz etal.”
MethodInfluentialMathews, 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 1× · see citing works
“8% of the optimal structure (Zuker et al., 1991; Mathews et al., 1999).”
Self-citationOptimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Zuker, M., & Stiegler, P. (1981) · Nucleic Acids Research · doi:10.1093/nar/9.1.133 · Cited by 3,604 · see citing works
Gilbert, W. (1986) · Nature · doi:10.1038/319618a0 · Cited by 2,721 · cited 1× · see citing works
“The dual nature of RNA as both a genetic material and functional molecule led to the RNA World hypothesis, that RNA was the first moleculeoflife(Gilbert,1986), andthisdualnaturehasalsobeenutilized to develop in vitro methods to evolve functional sequences (Joyce, 1994).”
BackgroundFrazier, L., & Rayner, K. (1982) · Cognitive Psychology · doi:10.1016/0010-0285(82)90008-1 · Cited by 1,793 · cited 1× · see citing works
“This is analogous to psycholinguistic evidence that humans incrementally parse a sentence before it is fully read or heard (Frazier and Rayner, 1982).”
BackgroundMathews, D. H., Disney, M. D., Childs‐Disney, J. L., Schroeder, S. J., Zuker, M., & Turner, D. H. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0401799101 · Cited by 1,609 · cited 1× · see citing works
“In particular, we demonstrate two versions of LinearFold, LinearFold-V using the thermodynamic free energy model (Mathews et al., 2004) from Vienna RNAfold (Lorenz et al.”
MethodSelf-citationNon–coding RNA genes and the modern RNA world
Eddy, S. R. (2001) · Nature Reviews Genetics · doi:10.1038/35103511 · Cited by 1,429 · cited 1× · see citing works
“Ribonucleicacid(RNA)isinvolvedinnumerouscellularprocesses(Eddy, 2001).”
Big Data: Astronomical or Genomical?
Stephens, Z. D., Lee, S. Y., Faghri, F., Campbell, R. H., Zhai, C., Efron, M. J., Iyer, R., Schatz, M. C., Sinha, S., & Robinson, G. E. (2015) · PLOS Biology · doi:10.1371/journal.pbio.1002195 · Cited by 1,340 · cited 1× · see citing works
“Since experimentally determining the structure is expensive and time comsuming, and given the overwhelming increase in genomic data (about 1021 base-pairs per year) (Stephens et al., 2015), computational methods have been widely used as an alternative to automatically predict the structure.”
MethodThe equilibrium partition function and base pair binding probabilities for RNA secondary structure
McCaskill, J. S. (1990) · Biopolymers · doi:10.1002/bip.360290621 · Cited by 1,288 · cited 2× · see citing works
“…function and base pair probabilities for natural RNA sequences with well-defined structures, since the classical method for that task, the McCaskill (1990) algorithm, is isomorphic in structure to the cubic-time algorithms that are used as baselines in this paper.”
MethodThe promises and pitfalls of RNA-interference-based therapeutics
Castanotto, D., & Rossi, J. J. (2009) · Nature · doi:10.1038/nature07758 · Cited by 1,219 · see citing works
Recognition and parsing of context-free languages in time n3
Younger, D. H. (1967) · Information and Control · doi:10.1016/s0019-9958(67)80007-x · Cited by 935 · cited 1× · see citing works
“1965; Younger, 1967), has a running time of O ( n 3 ) that scales cubically with the sequence length n , which is too slow for long RNA sequences (Lange et al. , 2012).”
BackgroundArchitecture and secondary structure of an entire HIV-1 RNA genome
Watts, J. M., Dang, K. K., Gorelick, R. J., Leonard, C. W., Bess, J. W., Swanstrom, R. I., Burch, C. L., & Weeks, K. M. (2009) · Nature · doi:10.1038/nature08237 · Cited by 825 · cited 1× · see citing works
“,≤700nt) and predict structures within each segment only (Watts et al., 2009; Andronescu et al., 2007; Licon et al., 2010).”
BackgroundOn the translation of languages from left to right
Knuth, D. E. (1965) · Information and Control · doi:10.1016/s0019-9958(65)90426-2 · Cited by 784 · see citing works
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 · cited 1× · see citing works
“1, from the NONCODE database (Zhao et al., 2016)).”
CONTRAfold: RNA secondary structure prediction without physics-based models
Do, C., Woods, D. A., & Batzoglou, S. (2006) · Intelligent Systems in Molecular Biology · doi:10.1093/bioinformatics/btl246 · Cited by 623 · cited 11× · see citing works
“Individually, LinearFold-C (the LinearFold implementation of the CONTRAfold model) is significantly more accurate in sensitivity than CONTRAfold on one family (Group I Intron), and both PPV/sensitivity on two families (16S and 23S ribosomal RNAs), with the last two being the longest families in this dataset, where they…”
MethodInfluentialNussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587 · cited 1× · see citing works
“, 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al. , 1978; Zuker and Stiegler, 1981) to find the best-scoring (lowest free energy, maximum expected accuracy, or best model score) structure (Mathews and Turner, 2006; Washietl et al. , 2012).”
A partition function algorithm for nucleic acid secondary structure including pseudoknots
Dirks, R. M., & Pierce, N. (2003) · Journal of Computational Chemistry · doi:10.1002/jcc.10296 · Cited by 403 · see citing works
Prediction of RNA secondary structure by free energy minimization
Mathews, D. H., & Turner, D. H. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.05.010 · Cited by 400 · cited 3× · see citing works
“Widely used systems such as RNAstructure (Mathews and Turner, 2006), Vienna RNAfold (Lorenz etal.”
BackgroundMethodSelf-citationCENTROIDFOLD: a web server for RNA secondary structure prediction
Sato, K., Hamada, M., Asai, K., & Mitsuyama, T. (2009) · Nucleic Acids Research · doi:10.1093/nar/gkp367 · Cited by 334 · cited 2× · see citing works
“, 2006) and CentroidFold (Sato et al., 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al.”
MethodSato, K., Kato, Y., Hamada, M., Akutsu, T., & Asai, K. (2011) · Bioinform. · doi:10.1093/bioinformatics/btr215 · Cited by 322 · cited 1× · see citing works
“…replacing the cubic-time McCaskill algorithm with a linear-time one in those heuristic pseudoknot-prediction programs (Bellaousov and Mathews, 2010; Sato et al. , 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and Pierce, 2003; Reeder and…”
MethodThe Computer Simulation of RNA Folding Pathways Using a Genetic Algorithm
Gultyaev, A. P., van Batenburg, F. H. D., & Pleij, C. W. A. (1995) · Journal of Molecular Biology · doi:10.1006/jmbi.1995.0356 · Cited by 321 · cited 1× · see citing works
“Finally, our LinearFold algorithm resembles cotranscriptional folding where RNA molecules start to fold immediately before being fully transcribed (Gultyaev et al., 1995; Meyer and Miklos, 2004).”
MethodThe impact of target site accessibility on the design of effective siRNAs
Tafer, H., Ameres, S. L., Obernosterer, G., et al. (2008) · Nature Biotechnology · doi:10.1038/nbt1404 · Cited by 309 · cited 1× · see citing works
“, 2015)tothedesignofoligonucleotidesforknockdownofmessage(Luand Mathews, 2008; Tafer et al. , 2008).”
Reeder, J., & Giegerich, R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-104 · Cited by 303 · cited 1× · see citing works
“, 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and Pierce, 2003; Reeder and Giegerich, 2004).”
BackgroundSystemically delivered antisense oligomers upregulate gene expression in mouse tissues
Sazani, P., Gemignani, F., Kang, S.-H., Maier, M. A., Manoharan, M., Persmark, M., Bortner, D. M., & Kole, R. (2002) · Nature Biotechnology · doi:10.1038/nbt759 · Cited by 301 · see citing works
Huang, L., & Chiang, D. (2005) · doi:10.3115/1654494.1654500 · Cited by 293 · cited 2× · see citing works
“On top of beam search, we borrow k-best parsing (Huang and Chiang, 2005) to reduce the runtime to O(nb log b).”
MethodSelf-citationRNAcentral: a comprehensive database of non-coding RNA sequences
Petrov, A. I., Kay, S., Kalvari, I., Howe, K., Gray, K. A., Bruford, E. A., Kersey, P. J., Cochrane, G., Finn, R. D., Bateman, A. G., et al. (2016) · Nucleic Acids Research · doi:10.1093/nar/gkw1008 · Cited by 258 · cited 5× · see citing works
“It is able to fold the longest sequence in RNAcentral (244 296nt) within 3 min, while neither CONTRAfold or RNAfold runs on anything longer than 32 767nt due to datastructure limitations.”
BackgroundInfluentialRNAz 2.0: improved noncoding RNA detection.
Gruber, A. R., Findeiß, S., Stefan Washietl, A., Hofacker, I. L., & Stadler, P. F. (2010) · PubMed · Cited by 237 · see citing works
Local RNA base pairing probabilities in large sequences
Bernhart, S. H., Hofacker, I. L., & Stadler, P. F. (2005) · Bioinformatics · doi:10.1093/bioinformatics/btk014 · Cited by 230 · cited 2× · see citing works
“ThereisacrucialdifferencebetweenourLinearFoldandlocalfolding algorithms (Kiryu et al. , 2008; Bernhart et al. , 2006; Lange et al. , 2012) that can only predict pairs up to a certain distance.”
Efficient parameter estimation for RNA secondary structure prediction
Andronescu, M., Condon, A., Hoos, H. H., Mathews, D. H., & Murphy, K. P. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm223 · Cited by 220 · see citing works
Self-citationProbKnot: Fast prediction of RNA secondary structure including pseudoknots
Bellaousov, S., & Mathews, D. H. (2010) · RNA · doi:10.1261/rna.2125310 · Cited by 218 · cited 1× · see citing works
“…of pseudoknots, by either replacing the cubic-time McCaskill algorithm with a linear-time one in those heuristic pseudoknot-prediction programs (Bellaousov and Mathews, 2010; Sato et al. , 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and…”
MethodSelf-citationDynamic Programming for Linear-Time Incremental Parsing
Huang, L., & Sagae, K. (2010) · Cited by 208 · see citing works
Self-citationZuker, M., Jaeger, J. A., & Turner, D. H. (1991) · Nucleic Acids Research · doi:10.1093/nar/19.10.2707 · Cited by 203 · cited 1× · see citing works
“For example, it was well studied that while the lowest free energy structure contains only 72.9%oftheactualbasepairs(givenadataset), astructurecontaining 86.1% of them can be found with a free energy within 4.8% of the optimal structure (Zuker et al. , 1991; Mathews et al. , 1999).”
BackgroundInfluentialGareiss, P. C., Sobczak, K., McNaughton, B. R., Palde, P. B., Thornton, C. A., & Miller, B. L. (2008) · Journal of the American Chemical Society · doi:10.1021/ja804398y · Cited by 187 · cited 1× · see citing works
“,2007; Gareiss et al. , 2008; Castanotto and Rossi, 2009; Palde et al. , 2010).”
Cotranscriptional folding of a riboswitch at nucleotide resolution
Watters, K. E., Strobel, E. J., Yu, A. M., Lis, J. T., & Lucks, J. B. (2016) · Nature Structural & Molecular Biology · doi:10.1038/nsmb.3316 · Cited by 183 · cited 1× · see citing works
“We will test the hypothesis that our beams potentially capture cotranscriptional folding with empirical data on cotranscriptional folding (Watters et al., 2016).”
BackgroundSpeeding up the Consensus Clustering methodology for microarray data analysis
Giancarlo, R., & Utro, F. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-1 · Cited by 164 · see citing works
Structured Perceptron with Inexact Search
Huang, L., Fayong, S., & Guo, Y. (2012) · Cited by 159 · see citing works
Self-citationRNA Structure Prediction: An Overview of Methods
Seetin, M. G., & Mathews, D. H. (2012) · Methods in molecular biology · doi:10.1007/978-1-61779-949-5_8 · Cited by 159 · cited 2× · see citing works
“1A), is an important and challenging problem (Seetin and Mathews, 2012; Hofacker and Lorenz, 2014).”
BackgroundSelf-citationEfficient siRNA selection using hybridization thermodynamics
Lu, Z., & Mathews, D. H. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm920 · Cited by 157 · see citing works
Self-citationGlobal or local? Predicting secondary structure and accessibility in mRNAs
Lange, S. J., Maticzka, D., Möhl, M., Gagnon, J. N., Brown, C. M., & Backofen, R. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks181 · Cited by 150 · cited 3× · see citing works
“ThereisacrucialdifferencebetweenourLinearFoldandlocalfolding algorithms (Kiryu et al. , 2008; Bernhart et al. , 2006; Lange et al. , 2012) that can only predict pairs up to a certain distance.”
BackgroundMethodIn vitro evolution of nucleic acids
Joyce, G. F. (1994) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(94)90100-7 · Cited by 147 · cited 2× · see citing works
“The dual nature of RNA as both a genetic material and functional molecule led to the RNA World hypothesis, that RNA was the first moleculeoflife(Gilbert,1986), andthisdualnaturehasalsobeenutilized to develop in vitro methods to evolve functional sequences (Joyce, 1994).”
BackgroundRivas, E., Lang, R., & Eddy, S. R. (2012) · RNA · doi:10.1261/rna.030049.111 · Cited by 145 · see citing works
Crooke, S. T. (2004) · Current Molecular Medicine · doi:10.2174/1566524043360375 · Cited by 140 · cited 2× · see citing works
“Furthermore, RNA is an important drug target and agent (Angelbello et al., 2018; Sazani et al., 2002; Crooke, 2004; Childs-Disney et al., 2007; Gareiss et al., 2008; Castanotto and Rossi, 2009; Palde et al., 2010).”
BackgroundSloma, M. F., & Mathews, D. H. (2016) · RNA · doi:10.1261/rna.053694.115 · Cited by 133 · cited 1× · see citing works
“…sensitivity (the fraction of known pairs predicted) oneachRNAfamilyintheArchiveIIdataset, allowingcorrectlypredicted pairs to be offset by one position for one nucleotide as compared to the known structure (Sloma and Mathews, 2016); we also report exact match accuracies in Supplementary Table SI2.”
ResultSelf-citationA Small Molecule Microarray Platform To Select RNA Internal Loop−Ligand Interactions
Childs‐Disney, J. L., Wu, M., Pushechnikov, A. O., et al. (2007) · ACS Chemical Biology · doi:10.1021/cb700174r · Cited by 111 · see citing works
mRNAs and lncRNAs intrinsically form secondary structures with short end-to-end distances
Lai, W.-J. C., Kayedkhordeh, M., Cornell, E. V., Farah, E. N., Bellaousov, S., Rietmeijer, R. A., Salsi, E., Mathews, D. H., & Ermolenko, D. N. (2018) · Nature Communications · doi:10.1038/s41467-018-06792-z · Cited by 90 · cited 1× · see citing works
“All these local methods omit long-range base pairs, which theoretical and experimental studies have demonstrated to be common in naturalRNAs, especiallybetweenthe5’and3’ends(SeetinandMathews, 2012; Lai et al. , 2018; Li and Reidys, 2018).”
BackgroundSelf-citationUsing Genome Sequence to Enable the Design of Medicines and Chemical Probes
Angelbello, A. J., Chen, J. L., Childs‐Disney, J. L., Zhang, P., Wang, Z.-F., & Disney, M. D. (2018) · Chemical Reviews · doi:10.1021/acs.chemrev.7b00504 · Cited by 80 · see citing works
Co-transcriptional folding is encoded within RNA genes
Meyer, I. M., & Miklós, I. (2004) · BMC Molecular Biology · doi:10.1186/1471-2199-5-10 · Cited by 71 · cited 2× · see citing works
“We hypothesize that some RNA sequences have evolved to fold co-transcriptionally (Meyer and Miklós, 2004), thus making our 50-to-30 incremental approach more accurate than bottom-up baselines.”
BackgroundMethodComputational analysis of noncoding RNAs
Stefan Washietl, A., Will, S., Hendrix, D. A., Goff, L. A., Rinn, J. L., Berger, B., & Kellis, M. (2012) · Wiley Interdisciplinary Reviews - RNA · doi:10.1002/wrna.1134 · Cited by 63 · cited 1× · see citing works
“, 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al. , 1978; Zuker and Stiegler, 1981) to find the best-scoring (lowest free energy, maximum expected accuracy, or best model score) structure (Mathews and Turner, 2006; Washietl et al. , 2012).”
Self-citationRfold: an exact algorithm for computing local base pairing probabilities
Kiryu, H., Kin, T., & Asai, K. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm591 · Cited by 58 · see citing works
The ends of a large RNA molecule are necessarily close
Yoffe, A. M., Prinsen, P., Gelbart, W. M., et al. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq642 · Cited by 57 · see citing works
Graph-structured Stack and natural language parsing
Tomita, M. (1988) · Annual Meeting of the Association for Computational Linguistics (ACL) · doi:10.3115/982023.982054 · Cited by 35 · cited 2× · see citing works
“While this naive version runsintheexponentialtimeof O (3 n ) ,weborrowanefficientpackingidea from computational linguistic (Tomita, 1988) that reduces the runtime back to O ( n 3 ) .”
BackgroundMethodPalde, P. B., Ofori, L. O., Gareiss, P. C., Lerea, J., & Miller, B. L. (2010) · Journal of Medicinal Chemistry · doi:10.1021/jm100231t · Cited by 34 · cited 1× · see citing works
“Furthermore, RNA is an important drug target and agent (Angelbello et al., 2018; Sazani et al., 2002; Crooke, 2004; Childs-Disney et al., 2007; Gareiss et al., 2008; Castanotto and Rossi, 2009; Palde et al., 2010).”
BackgroundThe separation between the 5′-3′ ends in long RNA molecules is short and nearly constant
Leija-Martínez, N., Casas‐Flores, S., Cadena-Nava, R. D., Roca, J. A. I., Méndez, J. A. T., Gómez, E., & Ruiz-Garcia, J. (2014) · Nucleic Acids Research · doi:10.1093/nar/gku1249 · Cited by 30 · cited 1× · see citing works
“Theoretical and empirical studies found several evidences that unboundedly long-distance pairs are actually quite common in natural RNA structures: (a) the length of the longest base pair grows nearly linearly with sequence length n (Li and Reidys, 2018); (b) the physical distance between the 5’–3’ ends in folded stru…”
BackgroundFu, Y., Xu, Z. Z., Lu, Z. J., Zhao, S., & Mathews, D. H. (2015) · PLoS ONE · doi:10.1371/journal.pone.0130200 · Cited by 25 · see citing works
Self-citationEnsemble-based prediction of RNA secondary structures
Aghaeepour, N., & Hoos, H. H. (2013) · BMC Bioinformatics · doi:10.1186/1471-2105-14-139 · Cited by 21 · cited 1× · see citing works
“We test statistical significance using a paired, one-sided permutation test, following (Aghaeepour and Hoos, 2013).”
MethodPredicting RNA Structure: Advances and Limitations
Hofacker, I. L., & Lorenz, R. (2013) · Methods in molecular biology · doi:10.1007/978-1-62703-667-2_1 · Cited by 21 · cited 2× · see citing works
“1A), is an important and challenging problem (Seetin and Mathews, 2012; Hofacker and Lorenz, 2014).”
BackgroundFaster algorithms for RNA-folding using the Four-Russians method
Venkatachalam, B., Gusfield, D., & Frid, Y. (2014) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-9-5 · Cited by 21 · cited 2× · see citing works
“There are other algorithmic efforts to speed up RNA folding, including an O n3= log n algorithm using the Four-Russians method (Venkatachalam et al., 2014), and two other sub-cubic algorithms inspired by fast matrix multiplication and context-free parsing (Bringmann et al., 2016; Zakov et al.,…”
MethodReducing the worst case running times of a family of RNA and CFG problems, using Valiant’s approach
Zakov, S., Tsur, D., & Ziv-Ukelson, M. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-20 · Cited by 19 · cited 1× · see citing works
“, 2014), and two other sub-cubic algorithms inspired by fast matrix multiplication and context-free parsing (Zakov et al., 2011; Bringmann et al., 2016).”
BackgroundLinear Time Algorithm for Parsing RNA Secondary Structure
Rastegari, B., & Condon, A. (2005) · Lecture notes in computer science · doi:10.1007/11557067_28 · Cited by 18 · cited 1× · see citing works
“There also exists a linear-time algorithm (Rastegari and Condon, 2005) to analyze a given structure, but not to predict one de novo.”
BackgroundThe Trouble with Long-Range Base Pairs in RNA Folding
Amman, F., Bernhart, S. H., Doose, G., et al. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-02624-4_1 · Cited by 12 · see citing works
The Rainbow Spectrum of RNA Secondary Structures
Li, T. J. X., & Reidys, C. M. (2018) · Bulletin of Mathematical Biology · doi:10.1007/s11538-018-0411-9 · Cited by 8 · cited 2× · see citing works
“All these local methods omit long-range base pairs, which theoretical and experimental studies have demonstrated to be common in natural RNAs, especially between the 50 and 30 ends (Lai et al., 2018; Li and Reidys, 2018; Seetin and Mathews, 2012).”
BackgroundLicon, A., Taufer, M., Leung, M.-Y., & Johnson, K. L. (2010) · PubMed · Cited by 4 · see citing works
Graph-structured Stack and Natural Language Parsing
Tomlta, M. (2002) · Cited by 2 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- Amman, 2013, Proceedings of the 8th Brazilian Symposium on Bioinformatics, BSB 2013, Recife, Brazil, 1
- Hofacker, 2014, RNA Folding: Methods and Protocols. Methods in Molecular Biology 1086, 1
- Huang, 2010, Proceedings of ACL. Uppsala, Sweden, 1077
- Tomita, 1988, Proceedings of ACL, 249
Cited by
Sorted by citations
Algorithm for optimized mRNA design improves stability and immunogenicity
Zhang, H., Zhang, L., Lin, A., Xu, C., Li, Z., Liu, K., Liu, B., Ma, X., Zhao, F., Jiang, H., et al. (2023) · Nature · doi:10.1038/s41586-023-06127-z · Cited by 498 · see citing works
Self-citationRNA secondary structure prediction using deep learning with thermodynamic integration
Sato, K., Akiyama, M., & Sakakibara, Y. (2021) · Nature Communications · doi:10.1038/s41467-021-21194-4 · Cited by 470 · see citing works
UFold: fast and accurate RNA secondary structure prediction with deep learning
Fu, L., Cao, Y., Wu, J., Peng, Q., Nie, Q. H., & Xie, X. S. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab1074 · Cited by 269 · see citing works
Chen, J., Hu, Z., Sun, S., Tan, Q., Wang, Y., Yu, Q., Zong, L., Hong, L., Xiao, J., Shen, T., et al. (2022) · doi:10.1101/2022.08.06.503062 · Cited by 247 · see citing works
“In terms of RNA secondary structure prediction, RNA-FM outperforms LinearFold by up to 30% and SPOT-RNA by up to 20% in terms of F1 score on cross-dataset validation.”
MethodThe architecture of the SARS-CoV-2 RNA genome inside virion
Cao, C., Cai, Z., Xiao, X., Rao, J. Y., Chen, J., Hu, N., Yang, M., Xing, X., Wang, Y., Li, M., et al. (2021) · Nature Communications · doi:10.1038/s41467-021-22785-x · Cited by 204 · see citing works
Machine learning in polymer informatics
Sha, W., Li, Y., Tang, S., Tian, J., Zhao, Y., Guo, Y., Zhang, W., Zhang, X., Lu, S., Cao, Y., et al. (2021) · InfoMat · doi:10.1002/inf2.12167 · Cited by 202 · see citing works
Bridge RNAs direct programmable recombination of target and donor DNA
Durrant, M. G., Perry, N. T., Pai, J. J., Jangid, A. R., Athukoralage, J. S., Hiraizumi, M., McSpedon, J. P., Pawluk, A., Nishimasu, H., Konermann, S., et al. (2024) · Nature · doi:10.1038/s41586-024-07552-4 · Cited by 163 · see citing works
Multi-purpose RNA language modelling with motif-aware pretraining and type-guided fine-tuning
Wang, N., Bian, J., Li, Y., Li, X., Mumtaz, S., Kong, L., & Xiong, H. (2024) · Nature Machine Intelligence · doi:10.1038/s42256-024-00836-4 · Cited by 138 · see citing works
Review of machine learning methods for RNA secondary structure prediction
Zhao, Q., Zhao, Z., Fan, X., Yuan, Z., Mao, Q., & Yao, Y. (2021) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1009291 · Cited by 106 · see citing works
Singh, J., Paliwal, K. K., Zhang, T., Singh, J., Litfin, T., & Zhou, Y. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab165 · Cited by 106 · see citing works
Sato, K., & Hamada, M. (2023) · Briefings in Bioinformatics · doi:10.1093/bib/bbad186 · Cited by 101 · see citing works
Zhang, H., Zhang, L., Mathews, D. H., & Huang, L. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa460 · Cited by 83 · see citing works
Self-citationmRNA vaccine sequence and structure design and optimization: Advances and challenges
Jin, L., Zhou, Y., Zhang, S., & Chen, S. (2024) · Journal of Biological Chemistry · doi:10.1016/j.jbc.2024.108015 · Cited by 85 · see citing works
Deep learning and CRISPR-Cas13d ortholog discovery for optimized RNA targeting
Wei, J., Lotfy, P., Faizi, K., Baungaard, S., Gibson, E., Wang, E., Slabodkin, H., Kinnaman, E., Chandrasekaran, S. S., Kitano, H. C., et al. (2023) · Cell Systems · doi:10.1016/j.cels.2023.11.006 · Cited by 68 · see citing works
STARRPeaker: uniform processing and accurate identification of STARR-seq active regions
Lee, D., Shi, M., Moran, J. R., Wall, M., Zhang, J., Liu, J. J., Fitzgerald, D., Kyono, Y., Ma, L., White, K. P., et al. (2020) · Genome biology · doi:10.1186/s13059-020-02194-x · Cited by 59 · see citing works
“We used the LinearFold [48] algorithm to estimate the folding energy of each genomic bin iteratively across the whole genome.”
MethodUNI-RNA: UNIVERSAL PRE-TRAINED MODELS REVOLUTIONIZE RNA RESEARCHPreprint
Wang, X., Gu, R., Chen, Z., Li, Y., Ji, X.-H., Ke, G., & Wen, H. (2023) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2023.07.11.548588 · Cited by 60 · see citing works
ERNIE-RNA: an RNA language model with structure-enhanced representations
Yin, W., Zhang, Z., Zhang, S., He, L., Zhang, R., Jiang, R., Liu, G., Wang, J., Zhang, X., Qin, T., et al. (2025) · Nature Communications · doi:10.1038/s41467-025-64972-0 · Cited by 55 · see citing works
Mehta, N. A., & Shukla, S. (2021) · SN Computer Science · doi:10.1007/s42979-021-00923-y · Cited by 55 · see citing works
Bugnon, L. A., Edera, A., Prochetto, S., Gerard, M. F., Raad, J., Fenoy, E., Rubiolo, M., Chorostecki, U., Gabaldón, T., Ariel, F., et al. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac205 · Cited by 53 · see citing works
Nearest neighbor rules for RNA helix folding thermodynamics: improved end effects
Zuber, J., Schroeder, S. J., Sun, H., Turner, D. H., & Mathews, D. H. (2022) · Nucleic Acids Research · doi:10.1093/nar/gkac261 · Cited by 53 · see citing works
Self-citationWang, Y., Shen, Y., Li, J., et al. (2025) · Nucleic Acids Research · doi:10.1093/nar/gkaf533 · Cited by 39 · see citing works
RNAformer: A Simple yet Effective Model for Homology-Aware RNA Secondary Structure PredictionPreprint
Franke, J. K. H., Runge, F., Koeksal, R., Matus, D., Backofen, R., & Hutter, F. (2024) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2024.02.12.579881 · Cited by 35 · see citing works
RNA folding using quantum computers
Fox, D. M., MacDermaid, C. M., Schreij, A. M. A., Zwierzyna, M., & Walker, R. C. (2022) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1010032 · Cited by 33 · see citing works
“There also exist approximate methods that have been shown to have linear scaling (16).”
MethodRNA Secondary Structure Analysis Using RNAstructure
Ali, S. E., Mittal, A., & Mathews, D. H. (2023) · Current Protocols · doi:10.1002/cpz1.846 · Cited by 30 · see citing works
“For long sequences such as RNA viral genomes (i.e., longer than ∼ 5000 nt), the LinearFold and LinearPartition programs are available for structure prediction (Huang et al., 2019; Zhang et al., 2020).”
BackgroundSelf-citationMittal, A., Turner, D. H., & Mathews, D. H. (2024) · Journal of Molecular Biology · doi:10.1016/j.jmb.2024.168549 · Cited by 29 · see citing works
Self-citationRNAProbe: a web server for normalization and analysis of RNA structure probing data
Wirecki, T. K., Merdas, K., Bernat, A., et al. (2020) · Nucleic Acids Research · doi:10.1093/nar/gkaa396 · Cited by 28 · see citing works
“For sequence-only predictions, RNAProbe makes use of ViennaRNA RNAfold (15), RNAstructure Fold and ProbKnot (16), CentroidFold (28), CONTRAFold (29), IPknot (30), LinearFold-V and LinearFold-C (31).”
MethodLi, Y., Wang, F., Yang, J., Han, Z., Chen, L., Jiang, W., Zhou, H., Li, T., Tang, Z., Deng, J., et al. (2025) · Nature Communications · doi:10.1038/s41467-025-64894-x · Cited by 37 · see citing works
“Current MFE prediction tools, such as RNAfold 35 and Linearfold 36 , use dynamic programming.”
Machine learning modeling of RNA structures: methods, challenges and future perspectives
Wu, K., Zou, J., & Chang, H. Y. (2023) · Briefings in Bioinformatics · doi:10.1093/bib/bbad210 · Cited by 25 · see citing works
Nef, C., Madoui, M., Pelletier, É., & Bowler, C. (2022) · PLoS Biology · doi:10.1371/journal.pbio.3001893 · Cited by 22 · see citing works
“…a synonymous mutation, we searched whether the nucleotide substitution modified the predicted RNA secondary structure through an analysis conducted on the LinearFold and RNAfold web servers [65,66], as silent mutations may impact haplotypes as for instance changes in RNA secondary structure [67].”
InfluentialFitness functions for RNA structure design
Ward, M., Courtney, E., & Rivas, E. (2023) · Nucleic Acids Research · doi:10.1093/nar/gkad097 · Cited by 24 · see citing works
RNA design via structure-aware multifrontier ensemble optimization
Zhou, T., Dai, N., Li, S., et al. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad252 · Cited by 23 · see citing works
Self-citationChan, Y.-C., Kienle, E., Oti, M., Liddo, A. D., Méndez-Lago, M., Aschauer, D. F., Peter, M., Pagani, M., Arnold, C. D., Vonderheit, A., et al. (2023) · Scientific Reports · doi:10.1038/s41598-023-33448-w · Cited by 20 · see citing works
RNA stability enhancers for durable base-modified mRNA therapeutics
Jung, S.-J., Seo, J. J., Lee, S., Hyun, S.-I., Lee, J.-E., Lee, S., Lee, Y., Chang, H., Lee, H., Kim, J.-H., et al. (2025) · Nature Biotechnology · doi:10.1038/s41587-025-02891-7 · Cited by 26 · see citing works
AptaMat: a matrix-based algorithm to compare single-stranded oligonucleotides secondary structures
Binet, T., Avalle, B., Felipe, M. D., et al. (2022) · Bioinformatics · doi:10.1093/bioinformatics/btac752 · Cited by 20 · see citing works
Deep learning and CRISPR-Cas13d ortholog discovery for optimized RNA targeting
Wei, J., Lotfy, P., Faizi, K., Baungaard, S., Gibson, E., Wang, E., Slabodkin, H., Kinnaman, E., Chandrasekaran, S., Kitano, H., et al. (2021) · doi:10.1101/2021.09.14.460134 · Cited by 67 · see citing works
Qiu, X. (2023) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1011047 · Cited by 21 · see citing works
RNADiffFold: generative RNA secondary structure prediction using discrete diffusion models
Wang, Z., Feng, Y., Tian, Q., Liu, Z., Yan, P., & Li, X. (2024) · Briefings in Bioinformatics · doi:10.1093/bib/bbae618 · Cited by 19 · see citing works
“Energy-based methods primarily utilize experimentally determined parameters to calculate the free energy of RNA structures and identify the most stable secondary structures through dynamic programming [10–13].”
Community science designed ribosomes with beneficial phenotypes
Krüger, A., Watkins, A. M., Wellington-Oguri, R., Romano, J., Kofman, C., DeFoe, A., Kim, Y., Anderson-Lee, J., Fisker, E., Townley, J., et al. (2023) · Nature Communications · doi:10.1038/s41467-023-35827-3 · Cited by 18 · see citing works
Comparative Study of Single-stranded Oligonucleotides Secondary Structure Prediction Tools
Binet, T., Padiolleau‐Lefèvre, S., Octave, S., Avalle, B., & Maffucci, I. (2023) · BMC Bioinformatics · doi:10.1186/s12859-023-05532-5 · Cited by 17 · see citing works
“For example, Linearfold [7] implements an algorithm with a linear time complexity, which makes it suitable for the prediction of long ssNA structures.”
MethodAdvancing mRNA subcellular localization prediction with graph neural network and RNA structure
Li, F., Bi, Y., Guo, X., et al. (2024) · Bioinformatics · doi:10.1093/bioinformatics/btae504 · Cited by 17 · see citing works
“We have prepared two distinct graphs predicted by two popular prediction tools, i.e. RNAFold (Lorenz et al. 2011) and LinearFold (Huang et al. 2019), to diversify the resources of predicted structures and enhance the reliability of structural features extracted.”
Deep generalizable prediction of RNA secondary structure via base pair motif energy
Zhu, H., Tang, F., Quan, Q., Chen, K., Xiong, P., & Zhou, S. K. (2025) · Nature Communications · doi:10.1038/s41467-025-60048-1 · Cited by 17 · see citing works
“…version 1.0 19 , CONTRAfold version 2.02 18 , and EternaFold version 1.3.1 24 ; (3) Non-learning meth-ods: Linearfold (committed on Aug.29, 2022) 21 , RNAfoldin ViennaRNA package version 2.6.4 22,30 , SimFold 25 in MultiRNAFold 55 package version 2.0 in RNAsoft package 56 and RNAstructure…”
InfluentialRNA structure prediction using deep learning — A comprehensive review
Chaturvedi, M., Rashid, M. A., & Paliwal, K. K. (2025) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2025.109845 · Cited by 18 · see citing works
sincFold: end-to-end learning of short- and long-range interactions in RNA secondary structure
(2024) · doi:10.1093/bib/bbae271 · Cited by 14 · see citing works
“However, all these methods suffer from low resolution and high costs [19].”
BackgroundDasgupta, S., LaDu, J., Garcia, G. R., Li, S., Tomono-Duval, K., Rericha, Y., Huang, L., & Tanguay, R. L. (2023) · Toxicological Sciences · doi:10.1093/toxsci/kfad050 · Cited by 14 · see citing works
Self-citationCut site preference allows influenza A virus PA-X to discriminate between host and viral mRNAs
Gaucherand, L., Iyer, A., Gilabert, I., et al. (2023) · Nature Microbiology · doi:10.1038/s41564-023-01409-8 · Cited by 14 · see citing works
Zhao, Q., Mao, Q., Zhao, Z., Yuan, W., He, Q., Sun, Q., Yao, Y., & Fan, X. (2023) · Scientific Reports · doi:10.1038/s41598-023-30124-x · Cited by 14 · see citing works
“To evaluate the benefits of employing RNA-par as a preprocessing step of RNA secondary structure prediction, we combined RNA-par with five state-of-the-art RNA secondary structure prediction methods (RNAfold 18 , CONTRAfold, Linearfold 20 , SPOT-RNA 28 , and mfold 45 ), and validated them with the independent test set.”
MethodGCNfold: A novel lightweight model with valid extractors for RNA secondary structure prediction
Yang, E., Zhang, H., Zang, Z., Zhou, Z., Wang, S., Liu, Z., & Liu, Y. (2023) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2023.107246 · Cited by 14 · see citing works
Self-citationDiscovery of RNA‐Targeting Small Molecules: Challenges and Future Directions
Cai, Z., Ma, H., Ye, F., Lei, D., Deng, Z., Li, Y., Gu, R., & Wen, H. (2025) · MedComm · doi:10.1002/mco2.70342 · Cited by 14 · see citing works
“The LinearFold algorithm employs an innovative dynamic programming approach to RNA secondary structure prediction, incorporating heuristics that facilitate linear time and space complexity (O(n)) [38].”
Zhang, H., Li, S., Zhang, L., Mathews, D. H., & Huang, L. (2022) · Nucleic Acids Research · doi:10.1093/nar/gkac1029 · Cited by 13 · see citing works
“5 We are the first to formulate general sampling (Nussinov, Zuker, LinearFold, etc.) under a unified framework that exploits symmetry.”
BackgroundSelf-citationQfold: a new modeling paradigm for the RNA folding problem
Lewis, M. W., Verma, A., & Eckdahl, T. T. (2021) · Journal of Heuristics · doi:10.1007/s10732-021-09471-3 · Cited by 13 · see citing works
“For instance, Huang (2019) used beam search in conjunction with DP to report improved accuracy for long RNA molecules The free energies associated with base pairs are used to predict RNA structure, and are often incorporated into a model as static numbers even though they are not known with…”
Language models enable zero-shot prediction of RNA secondary structures including pseudoknotsPreprint
Gong, T., & Bu, D. (2024) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2024.01.27.577533 · Cited by 13 · see citing works
“Representative prediction approaches includes Vienna RNA [28], Mfold [29], LinearFold [30], and RNAstructure [31].”
MethodPRFect: a tool to predict programmed ribosomal frameshifts in prokaryotic and viral genomes
McNair, K. A., Salamon, P., Edwards, R. A., et al. (2024) · BMC Bioinformatics · doi:10.1186/s12859-024-05701-0 · Cited by 12 · see citing works
“The last two were adapted from their original C code libraries [17, 18] into Python packages that auto-install along with the other packages when the previous command ( pip install prfect ) is used.”
LTPConstraint: a transfer learning based end-to-end method for RNA secondary structure prediction
Fei, Y., Zhang, H., Wang, Y., et al. (2022) · BMC Bioinformatics · doi:10.1186/s12859-022-04847-z · Cited by 11 · see citing works
“The methods used for the comparison are CONTRAfold, LinearFold [55], ProbKnot [56], RNAfold and CycleFold [57].”
MethodSelf-citationTargeting non-coding RNAs: Perspectives and challenges of in-silico approaches
Rocca, R., Grillone, K., Citriniti, E. L., Gualtieri, G., Artese, A., Tagliaferri, P., Tassone, P., & Alcaro, S. (2023) · European Journal of Medicinal Chemistry · doi:10.1016/j.ejmech.2023.115850 · Cited by 11 · see citing works
STARRPeaker: Uniform processing and accurate identification of STARR-seq active regionsPreprint
Lee, D., Shi, M., Moran, J., Wall, M., Zhang, J., Liu, J. J., Fitzgerald, D., Kyono, Y., Ma, L., White, K. P., et al. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/694869 · Cited by 11 · see citing works
LinearAlifold: Linear-time consensus structure prediction for RNA alignments
Malik, A., Zhang, L., Gautam, M., Dai, N., Li, S., Zhang, H., Mathews, D. H., & Huang, L. (2024) · Journal of Molecular Biology · doi:10.1016/j.jmb.2024.168694 · Cited by 10 · see citing works
“Here we report LinearAlifold, an efficient tool for consensus structure prediction that scales linearly with both the sequence length ( n ) and the number of aligned sequences ( k ) without any constraints on pair distance, building upon on our previous work LinearFold (19) and LinearPartition (20) for single sequence…”
InfluentialSelf-citationmRNA folding algorithms for structure and codon optimization
Ward, M., Richardson, M. O. G., & Metkar, M. (2025) · Briefings in Bioinformatics · doi:10.1093/bib/bbaf386 · Cited by 10 · see citing works
“…folding algorithms directly identify the sequence π with the lowest MFE structure from the set of all valid coding sequences CDS (α) ([13, 14]): However, the goal of mRNA folding is to find the optimal sequence-structure pair for the CDS, rather than just the optimal structure as in RNA folding.”
Huber, M., & Raidl, G. R. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-95470-3_22 · Cited by 10 · see citing works
“Concerning combinatorial optimization problems, many applications exist in particular in the domains of scheduling, see, e.g., [23,8,3], and string-related problems originating in bioinformatics, see, e.g., [13,7,6], but also packing [2].”
BackgroundVillarreal-González, R., Acosta-Hoyos, A. J., Garzon-Ochoa, J. A., et al. (2020) · Molecules · doi:10.3390/molecules26010020 · Cited by 10 · see citing works
Tagashira, M., & Asai, K. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab738 · Cited by 10 · see citing works
A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
Zaborniak, T., Giraldo, J., Müller, H. A., Jabbari, H., & Stege, U. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00037 · Cited by 11 · see citing works
ThreshKnot: Thresholded ProbKnot for Improved RNA Secondary Structure PredictionPreprint
Zhang, L., Zhang, H., Mathews, D., & Huang, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12796 · Cited by 17 · see citing works
“4 Following LinearFold (Huang et al., 2019), we only consider full sequences (i.e., 4 http://rna.urmc.rochester.edu/pub/archiveII.tar.gz excluding the individual folding domains of 16S/23S rRNAs) and remove those sequences found in the S-Processed set (Andronescu et al., 2007) (because CONTRAfold is trained on S-Proce…”
MethodInfluentialSelf-citationThe role of secondary structures in the functioning of 3′ untranslated regions of mRNA
Zhukova, M. V., Schedl, P. D., & Shidlovskii, Y. V. (2023) · BioEssays · doi:10.1002/bies.202300099 · Cited by 9 · see citing works
“…50 transcripts (400 transcripts in total) for each of eight groups distinguished by the minimaldistancefromthe CPEtothe 3 ′ end (51–100,101–150,etc.to 401–450) and analyzed the secondary structure of the 3 ′ UTRs using two models in LinearFold software, [67] LinearFold-C (based on CON-TRAfold v2.”
MethodTransformers in RNA structure prediction: A review
Chaturvedi, M., Rashid, M. A., & Paliwal, K. K. (2025) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2025.03.021 · Cited by 8 · see citing works
“RNAfold [36] and LinearFold [37] calculate the minimum free energy (MFE) to predict the RNA secondary structures.”
Zhang, H., Li, S., Dai, N., Zhang, L., Mathews, D. H., & Huang, L. (2023) · Nucleic Acids Research · doi:10.1093/nar/gkad664 · Cited by 9 · see citing works
“Note that the default value of b is inherited from LinearFold ( 28 ), which shows that the performance of b = 100 is robust across different families.”
BackgroundSelf-citationZhang, C., & Forsdyke, D. R. (2021) · Computational Biology and Chemistry · doi:10.1016/j.compbiolchem.2021.107570 · Cited by 8 · see citing works
LinearDesign: Efficient Algorithms for Optimized mRNA Sequence DesignPreprint
Zhang, H., Zhang, L., Li, Z., Liu, K., Liu, B., Mathews, D. H., & Huang, L. (2020) · arXiv (Cornell University) · Cited by 8 · see citing works
Self-citationComparative analysis of RNA secondary structure accuracy on predicted RNA 3D models
Kulkarni, M., Thangappan, J., Deb, I., et al. (2023) · PLoS ONE · doi:10.1371/journal.pone.0290907 · Cited by 7 · see citing works
“The R2DT-predicted 2D structure has a large flexible loop region, A19-G34, whereas this region is divided into bulge and apical loop due to the base pairing of C21-G29 and C22-G28 in the CentroidFold_CONTRAfold and LinearFold-C predicted 2D structures (Supplementary Table S5 and Figure S4).”
MethodInfluentialAnalysis of natural structures and chemical mapping data reveals local stability compensation in RNA
Cornwell-Arquitt, R., Nigh, R., Hathaway, M. T., et al. (2025) · Nucleic Acids Research · doi:10.1093/nar/gkaf565 · Cited by 7 · see citing works
“The field continues to evolve rapidly, with linear-time structure prediction methods [ 29 ], machine learning [ 30 ], and deep learning approaches enhancing our ability to predict RNA secondary structures with increasing accuracy [ 31– 33 ], but they often struggle when presented with novel RNAs […”
Self-citationKnotAli: informed energy minimization through the use of evolutionary information
Gray, M., Chester, S., & Jabbari, H. (2022) · BMC Bioinformatics · doi:10.1186/s12859-022-04673-3 · Cited by 7 · see citing works
“This dataset was compiled from the dataset of [54, 55], by removing duplicate sequences.”
MethodRnaBench: A Comprehensive Library for In Silico RNA ModellingPreprint
Runge, F., Farid, K., Franke, J. K. H., & Hutter, F. (2024) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2024.01.09.574794 · Cited by 7 · see citing works
“We provide the following commonly used baseline algorithms: RNAFold [Lorenz et al., 2011], LinearFold-C and LinearFold-V [Huang et al., 2019], ContraFold [Do et al., 2006], IpKnot [Sato et al., 2011], pKiss [Janssen and Giegerich, 2015], and the DL approaches SPOT-RNA [Singh et al., 2019], MXFold2…”
BackgroundMethodInfluentialBridge RNAs direct modular and programmable recombination of target and donor DNAPreprint
Durrant, M. G., Perry, N. T., Pai, J. J., Jangid, A. R., Athukoralage, J. S., Hiraizumi, M., McSpedon, J. P., Pawluk, A., Nishimasu, H., Konermann, S., et al. (2024) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2024.01.24.577089 · Cited by 7 · see citing works
Fukunaga, T., & Hamada, M. (2022) · Bioinformatics Advances · doi:10.1093/bioadv/vbac078 · Cited by 5 · see citing works
Loyer, G., & Reinharz, V. (2024) · Bioinformatics · doi:10.1093/bioinformatics/btae022 · Cited by 6 · see citing works
“…(i.e. a ¼ 0), PKnots (Rivas and Eddy 1999), HotKnots (Ren et al. 2005) Knotty (Jabbari et al. 2018), SPOT-RNA (Singh et al. 2019), MXfold2 (Sato et al. 2021), LinearFold (Huang et al. 2019), pAliKiss (Janssen and Giegerich 2015), BiokoP (Legendre et al. 2018) and BiORSEO (Becquey et al. 2020).”
SIMARD-LinearFold: Long Sequence RNA Design with Simulated Annealing
McBride, R., & Tsang, H. H. (2021) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec45853.2021.9504978 · Cited by 6 · see citing works
daminglu123 at SemEval-2022 Task 2: Using BERT and LSTM to Do Text Classification
Lu, D. (2022) · International Workshop on Semantic Evaluation (SemEval) · doi:10.18653/v1/2022.semeval-1.22 · Cited by 6 · see citing works
“Machine learning has made deep impacts on various areas, such as computer vision (He et al., 2015, 2017; Lu, 2018), computational biology (Jumper et al., 2021; Huang et al., 2019; Lu, 2010, 2009), and natural language processing (Yang et al., 2019b; Lewis et al., 2019; Madabushi et al., 2020) .”
BackgroundLinear-Time Algorithms for RNA Structure Prediction
Zhang, H., Zhang, L., Liu, K., Li, S., Mathews, D. H., & Huang, L. (2022) · Methods in molecular biology · doi:10.1007/978-1-0716-2768-6_2 · Cited by 6 · see citing works
Self-citationRubio‐Largo, Á., Lozano-García, N., Granado-Criado, J. M., et al. (2023) · Applied Soft Computing · doi:10.1016/j.asoc.2023.110779 · Cited by 6 · see citing works
Wfold: A new method for predicting RNA secondary structure with deep learning
Yuan, Y., Yang, E., & Zhang, R. (2024) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2024.109207 · Cited by 5 · see citing works
Tang, W. Y., Dai, N., Zhou, T., Mathews, D. H., & Huang, L. (2026) · Nature Communications · doi:10.1038/s41467-025-67901-3 · Cited by 5 · see citing works
Self-citationWaldl, M., Spicher, T., Lorenz, R., et al. (2023) · Journal of Bioinformatics and Computational Biology · doi:10.1142/s0219720023500166 · Cited by 5 · see citing works
SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration
Gray, M., Will, S., & Jabbari, H. (2024) · Algorithms for Molecular Biology · doi:10.1186/s13015-024-00256-4 · Cited by 5 · see citing works
“To evaluate the performance of our SparseRNAFolD, we compared it to two of the best-performing methods for prediction of pseudoknot-free RNA secondary structure, namely RNAFold [18] and LinearFold [19].”
BackgroundMethodMusyafa, A., Gao, Y., Solyman, A., Khan, S. A., Cai, W., & Khan, M. F. (2024) · PeerJ Computer Science · doi:10.7717/peerj-cs.2122 · Cited by 7 · see citing works
A Policy-Based Learning Beam Search for Combinatorial Optimization
Ettrich, R., Huber, M., & Raidl, G. R. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30035-6_9 · Cited by 5 · see citing works
“AlphaZero has also been adapted to solve various combinatorial optimization problems like 3D packing problems [13], minimum vertex cover and maximum cut [1], or graph coloring [10].”
MethodDeepRaccess: high-speed RNA accessibility prediction using deep learning
Hara, K., Iwano, N., Fukunaga, T., & Hamada, M. (2023) · Frontiers in Bioinformatics · doi:10.3389/fbinf.2023.1275787 · Cited by 5 · see citing works
Undesignable RNA Structure Identification via Rival Structure Generation and Structure Decomposition
Zhou, T., Tang, W. Y., Mathews, D. H., & Huang, L. (2024) · Lecture notes in computer science · doi:10.1007/978-1-0716-3989-4_17 · Cited by 5 · see citing works
“In Algorithm 2, we used LinearFold [11] (beam size set as 0, which means exact search without beam pruning) with the energy parameter from ViennaRNA 2.5.1 to find MFE( x ) and uMFE( x ).”
MethodInfluentialSelf-citationmemerna: Sparse RNA folding including coaxial stacking
Courtney, E., Datta, A., Mathews, D. H., & Ward, M. (2024) · Journal of Molecular Biology · doi:10.1016/j.jmb.2024.168819 · Cited by 5 · see citing works
Self-citationLearning to Fold RNAs in Linear TimePreprint
Chowdhury, F. A. R. R., Zhang, H., & Huang, L. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/852871 · Cited by 5 · see citing works
“To overcome the efficiency bottleneck of training, we present a new machine learning-based RNA folding system, using the recently proposed linear-time prediction engine LinearFold [10] for inference.”
MethodSelf-citationAb initio prediction of RNA structure ensembles with RNAnnealPreprint
Herron, L., Qiu, Y., Verma, A. R., et al. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.02.01.703098 · Cited by 5 · see citing works
LncTracker: A Unified Multi-Channel Framework for Multi-Label lncRNA Localization
Yi, H., Guo, X., Ran, Z., Bi, Y., & Li, F. (2025) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2025.3597589 · Cited by 4 · see citing works
“Thesecondary structuresoflncRNAswereobtainedusingLinearFold[30],and eachlncRNAwassubsequentlyencodedasagraph,definedas: each node v i ∈ V was represented by a feature vector composed of five properties: where p anf denotes the accumulated nucleotide frequency (ANF); p eiip denotes the electron…”
NTFold: Structure-Sensing Nucleotide Attention Learning for RNA Secondary Structure Prediction
Jin, K., Zhang, Z., Lan, G., et al. (2026) · Sensors · doi:10.3390/s26020688 · Cited by 4 · see citing works
“…0.533 RNAsoft [49] 0.497 0.626 0.535 RNAfold [12] 0.494 0.631 0.536 Mfold [13] 0.501 0.627 0.538 Contextfold [50] 0.529 0.607 0.546 LinearFold [46] 0.561 0.581 0.550 MXfold2 [31] 0.519 0.646 0.558 CONTRAfold [45] 0.528 0.655 0.567 SPOT-RNA [26] 0.594 0.693 0.619 UFold [28] 0.521 0.588 0.553…”
InfluentialMotif server: web server for undesignable RNA motifs and structures
Malik, A., Zhou, T., Tang, W. Y., et al. (2026) · Journal of Molecular Biology · doi:10.1016/j.jmb.2026.169767 · Cited by 4 · see citing works
Self-citationThe ADAR Family in Amphioxus: RNA Editing and Conserved Orthologous Site Predictions
Zawisza-Álvarez, M., Pérez-Calles, C., Gattoni, G., García‐Fernàndez, J., Benito‐Gutiérrez, È., & Herrera-Úbeda, C. (2020) · Genes · doi:10.3390/genes11121440 · Cited by 5 · see citing works
StemP: A Fast and Deterministic Stem-Graph Approach for RNA Secondary Structure Prediction
Tang, M., Hwang, K., & Kang, S. H. (2023) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2023.3253049 · Cited by 4 · see citing works
Dai, N., Zhou, T., Tang, W. Y., Mathews, D. H., & Huang, L. (2025) · Bioinformatics · doi:10.1093/bioinformatics/btaf245 · Cited by 4 · see citing works
“This function is also known as the RNA folding problem (Do et al. 2006, Lorenz et al. 2011, Huang et al. 2019), where we want to find the most stable structure for the input RNA x .”
Self-citationAptamers Meet Structural Bioinformatics, Computational Chemistry, and Artificial Intelligence
da Rosa, G., de Castro, M., García-Velásquez, V. M., Pintos, S., Benedetto, J., Grille, L., Valla, S., Álvarez-Salas, L. M., Calzada, V., & Dans, P. D. (2025) · Wiley Interdisciplinary Reviews Computational Molecular Science · doi:10.1002/wcms.70050 · Cited by 3 · see citing works
“In recent years, hybrid models for RNA have emerged, including LinearFold [90] and Vfold2D-MC [75].”
Toki, S., Matsui, M., Tominaga, K., Suzuki, T., Tsuchimatsu, T., & Iwasaki, W. (2026) · mSystems · doi:10.1128/msystems.00062-26 · Cited by 3 · see citing works
Sequence Design Using RNAstructure
Zhu, M., & Mathews, D. H. (2024) · Methods in molecular biology · doi:10.1007/978-1-0716-4079-1_2 · Cited by 3 · see citing works
Self-citationOmnes, L., Angel, É., Bartet, P., et al. (2025) · PLoS ONE · doi:10.1371/journal.pone.0314837 · Cited by 3 · see citing works
“…relying on either the Minimum Free Energy [3] (MFE) (mfold [4], RNAfold [5,6], RNAstructure [7], pKiss [8,9], ShapeKnots [10], LinearFold [11]), Maximum Expected Accuracy [12] (MEA) (CONTRAfold [13], CentroidFold [14], Prob-Knot [15], IPknot [16,17], BiORSEO [18]), or both (BiokoP [19]),…”
Hess, J. M., Jannen, W. K., & Aalberts, D. P. (2022) · Journal of Molecular Biology · doi:10.1016/j.jmb.2022.167578 · Cited by 3 · see citing works
- Authors
- Huang, L., Zhang, H., Deng, D., Zhao, K., Liu, K., Hendrix, D. A., & Mathews, D. H.
- Affiliations
- Oregon State University (US)
- Baidu (China) (CN)
- University of Rochester Medicine (US)
- Corresponding author
- Huang, Liang
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2019-07
- Volume
- 35
- Issue
- 14
- Pages
- i295-i304
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- PMC
- PMC6681470
- OpenAlex
- W2954102902
- Semantic Scholar
- 3aec8d65f4879bb9615fc09c3839036b60425b75
- Cited by
- 207
- References
- 63
- Citations by year
- 2026: 34 · 2025: 41 · 2024: 44 · 2023: 38 · 2022: 25 · 2021: 11 · 2020: 10 · 2019: 4
- FWCI
- 4.71
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Bioinformatics (publishedVersion, cc-by-nc)
- PubMed Central (publishedVersion, cc-by-nc)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (IIS-1656051, IIS-1817231)
- National Institutes of Health (R56 AG053460, R21 AG052950, R01 GM076485)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- RNA secondary structure prediction, RNA folding, beam search, incremental parsing, context-free grammars, 16S rRNA, 23S rRNA
- MeSH terms
- Nucleic Acid Conformation, RNA, Software, Sequence Analysis, RNA, RNA Folding
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
