Source-linked AI summary
LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search
Liang Huang, He Zhang, Dezhong Deng, Kai Zhao, Kaibo Liu, David A. Hendrix, David H. Mathews
TL;DR
RNA secondary-structure prediction is important but standard dynamic-programming methods scale cubically, limiting long-sequence use. LinearFold replaces bottom-up computation with left-to-right incremental dynamic programming and beam search, achieving linear time and space through approximate search. It attains higher overall accuracy, with especially strong results on long ribosomal RNAs and long-range base pairs.
Problem
Standard RNA-folding algorithms use O(n^3) time, while faster local methods restrict predicted pair distances and omit long-range base pairs.
Method
LinearFold combines left-to-right incremental dynamic programming with beam pruning to approximate unrestricted pseudoknot-free RNA folding in linear time and space.
Results
LinearFold achieves higher overall accuracy than exact baselines and is more accurate on long RNA families and base pairs separated by over 500 nucleotides.
Takeaways & Limitations
The approach provides efficient RNA folding without imposing base-pair-distance constraints while improving predictions on challenging long and long-range structures.
Takeaways & Limitations
The paper presents extending LinearFold to partition functions and base-pair probabilities as possible future work rather than a demonstrated capability.
Abstract
from arXiv · showhide
Motivation: Predicting the secondary structure of an 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(n^3)$-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: Our source code is available at https://github.com/LinearFold/LinearFold, and our webserver is at http://linearfold.org (sequence limit: 100,000nt).
1 Introduction
RNA secondary-structure prediction supports biological applications but is challenging at genomic scale because standard dynamic-programming methods scale cubically with sequence length. LinearFold addresses this bottleneck with left-to-right approximate folding that preserves unrestricted pair distances and improves accuracy on long and long-range structures.
- RNA secondary structure is defined by canonical base pairs, and knowing it provides information useful for applications including ncRNA detection and oligonucleotide design.
- LinearFold scans sequences left-to-right and uses an approximate search without constraining output base-pair distance.
- O(n^3) runtime makes widely used RNA-folding methods too slow for long sequences.
- Local alternatives run in linear time but restrict base pairs to distances of at most L, commonly L ≤150, omitting long-range pairs.
- The work connects computational linguistics, compiler theory, and RNA folding.
2 The LinearFold Algorithm
LinearFold reformulates pseudoknot-free RNA folding as left-to-right dynamic programming over stack-based prefix states, then combines state merging, packing, and beam pruning to reduce search from exponential to linear time. The resulting approximate method uses linear time and memory while retaining unbounded-distance base-pair prediction and improving accuracy over exact baselines.
- Problem formulation: RNA folding seeks the best-scoring pseudoknot-free structure for sequence x by maximizing a decomposable scoring function over valid base pairs and unpaired nucleotides.The allowed structures are balanced and use canonical CG, AU, and GU pairs.
- Idea 0: Brute-Force Search: The left-to-right algorithm scans each nucleotide while maintaining a stack and choosing push, skip, or pop actions to construct balanced dot-bracket structures.Push opens a downstream pair, skip marks an unpaired nucleotide, and pop closes a valid pair with the stack top.
- Idea 1: Merge States: Naive exhaustive search takes O(3^n) time, while merging states with identical stacks reduces the search to O(2^n) time.Identical-stack states are equivalent going forward, so only the highest-scoring state needs to be retained.
- Idea 2: Pack Temporarily Equivalent States: Packing states that share a stack top makes them temporarily equivalent until that opening bracket is closed, yielding an exact worst-case O(n^3)-time algorithm.Packed states are indexed by two positions, and their substructure and score depend only on the corresponding substring.
- Idea 3: Beam Pruning: Beam pruning keeps the b highest-scoring states at each step, producing approximate O(nb^2)-time and O(nb)-space search, or O(nb log b) time with k-best parsing.With default constant beam size b=100, runtime and space are linear in n; the approach retains unbounded-distance base-pair prediction.
- Accuracy and efficiency: LinearFold improves overall PPV and sensitivity over exact baselines, including CONTRAfold MFE 54.51/55.36 versus LinearFold-C 55.84/56.24.The accuracy advantage is especially reported for longer families and long-range base pairs.
3 Results
LinearFold combines substantially improved scalability with higher accuracy than cubic-time baselines, particularly on long sequences and long-range base pairs. Its approximate beam search offers controllable search quality and retains unbounded-distance pairing without the local-folding restriction.
- Efficiency and scalability: LinearFold scales nearly linearly in runtime, while baselines show superquadratic or near-cubic scaling on longer sequences.For a 32,753nt sequence, LinearFold takes 26 seconds versus 2 hours for CONTRAfold and 1.7 hours for RNAfold.
- Efficiency and scalability: LinearFold uses O(n) memory and predicts base pairs of unbounded distance, unlike classical O(n^2)-space dynamic programming.It folded a 244,296nt RNAcentral sequence within 3 minutes, while the baselines failed beyond 32,767nt because of data-structure limitations.
- Accuracy: Across RNA families, LinearFold improves accuracy over corresponding baselines, with the largest gains on long 16S and 23S ribosomal RNAs.LinearFold-C improves PPV/sensitivity by +3.56%/+3.09% on 16S and +8.65%/+5.66% on 23S; overall gains are +1.3%/+0.9% versus CONTRAfold and +0.3%/+0.2% versus RNAfold.
- Accuracy: LinearFold improves both PPV and sensitivity for long-range base pairs more than 500 nucleotides apart, correcting severe overprediction by exact-search baselines.The method is more selective while still predicting more correct long-range pairs.
- Beam-size effects: At beam size 100, search error grows linearly with sequence length, so average error per nucleotide remains stable; increasing beam size quickly approaches exact search.Accuracy is stable for LinearFold-C across b ∈[100, 150], while both PPV and sensitivity peak at b=120 before converging to exact search.
- Example predictions: Example structures show fewer false positives and many correctly predicted long-range pairs, including a 2,901nt pair in E. coli 23S rRNA.Local folding with a 150nt maximum base-pair span predicts no long-range pairs and is twice as slow as LinearFold-V with b=100.
4 Discussion
LinearFold’s approximate beam search can outperform exact-score baselines because model scores are imperfect and alternative structures may better match true base pairs. Its left-to-right design is distinct from other acceleration methods built on classical bottom-up dynamic programming.
- LinearFold’s approximate search can improve accuracy when exact optimization follows an imperfect scoring model.
- Imperfect scoring functions can make suboptimal-score structures more accurate than optimal-score structures.A cited example reports 72.9% of actual base pairs for the lowest-free-energy structure versus 86.1% for a structure within 4.8% of the optimum.
- Four-Russians, fast-matrix-multiplication, and parsing-based speedups remain based on classical cubic-time bottom-up algorithms.These approaches are therefore orthogonal to LinearFold’s left-to-right dynamic-programming strategy.
5 Conclusion and Future Work
LinearFold combines incremental dynamic programming with beam search to achieve linear time and memory while retaining unconstrained long-range folding. It improves accuracy overall and especially on long RNA families and long-range base pairs, while remaining stable across a moderate beam-size range.
- Conclusion: O(n)-time and O(n)-space approximate search applies to both machine-learned and thermodynamic RNA-folding models.The approach uses incremental dynamic programming plus beam search.
- Conclusion: LinearFold improves overall PPV and sensitivity while using only a fraction of existing algorithms’ time and memory.
- Conclusion: Accuracy gains are more pronounced for longer families such as 16S and 23S ribosomal RNAs.
- Conclusion: LinearFold is more accurate than baselines for long-range base pairs over 500nt apart.Such pairs are described as challenging for current models.
- Conclusion: Prediction accuracy and base-pair counts remain stable for beam sizes from 100–200.Performance still depends on beam size outside this reported range.
- Future Work: Unlike local folding methods, LinearFold does not restrict predicted pairs to a fixed maximum distance.The paper links this distinction to evidence that unboundedly long-distance pairs occur in natural RNA structures.
- Future Work: The paper proposes extensions to partition-function estimation, pseudoknot prediction, cotranscriptional-folding evaluation, and parameter training.These are presented as potential extensions rather than completed results.
Supporting Information
The supporting information identifies the paper and its authors, including the LinearFold method’s full title and contributor list.
- The listed authors are Liang Huang, He Zhang, Dezhong Deng, Kai Zhao, Kaibo Liu, David Hendrix, and David H. Mathews.
A Extra Definitions
The paper defines pseudoknot-free secondary structures through balanced notation strings, pair sets, validity checks, and unpaired nucleotide indices.
- Allowed pseudoknot-free secondary structures are represented using notation strings whose balance is explicitly defined.
- The paper defines the set of nucleotide pairs represented in a notation string.
- valid(x, S) checks whether every pair in set S is valid for RNA sequence x.
- unpaired(y) denotes the indices whose notation-string symbols are periods.
B Actual Scoring Functions
The scoring functions decompose RNA structures into loop-specific components. Vienna RNAfold uses thermodynamic feature templates, whereas CONTRAfold replaces energies with learned weights within the same framework.
- Loop decomposition: RNA structure scores decompose into hairpin, single, multiloop, and external-loop components.Single loops include bulges, internal loops, and stacking interactions.
- Loop decomposition: The scoring framework represents hairpin, single-loop, multiloop, and external-loop contributions separately.The example structure identifies each loop class explicitly.
- Model parameterization: Vienna RNAfold scores loops using thermodynamic templates for lengths, mismatches, stacking, and helix-closing features.These templates include hairpin, bulge, and internal-loop lengths.
- Model parameterization: CONTRAfold replaces the thermodynamic energies in this framework with model weights learned from data.Both models retain the same loop-based decomposition.
C Extra Results Tables and Figures
The supplementary evaluations characterize dataset construction, scoring conventions, pair counts, and accuracy across methods. LinearFold predicts similar pair quantities to the baselines and shows stronger performance on long-range pairs and selected RNA families.
- Datasets and evaluation: 2,889 sequences across 9 families remained after removing ArchiveII sequences appearing in the S-Processed training dataset.ArchiveII contains over 3,000 RNA sequences with known structures.
- Datasets and evaluation: A sampled RNAcentral evaluation evenly covers lengths from 1,000 to 244,296 nucleotides using 30 logarithmic bins.One sequence was randomly selected from each bin.
- Datasets and evaluation: A predicted pair counts as correct when it matches the reference or is displaced by one nucleotide on either strand.This evaluation convention accounts for uncertainty in comparative structures and equilibrium base pairing.
- Accuracy patterns: LinearFold-C outperforms CONTRAfold MFE by +1.30/+0.86 in PPV/sensitivity with sharpturn and +1.90/+1.37 without sharpturn.LinearFold-V exceeds Vienna RNAfold by +0.11 PPV and +0.06 sensitivity under exact matching.
- Accuracy patterns: LinearFold-V is more accurate than Vienna RNAfold for long-range pairs 500+nt apart in both PPV and Sensitivity.The comparison includes Vienna RNAfold and its local folding mode.
- Pair-count behavior: 0.2776 pairs per nucleotide occur in the dataset, with 7.6% pseudoknotted pairs.With the default beam size, LinearFold predicts nearly the same pair quantity as the baselines, differing by only 0.0002 and 0.0012 pairs per nucleotide.
D Deductive System for the Actual Systems
The actual LinearFold deductive system combines scoring rules with a left-to-right sequence scan and jumping operations. Only the multiloop reduce rule remains cubic-time in the described system.
- System structure: The implemented deductive system processes input x1 ... xn from an initial axiom toward a goal spanning the sequence.The figure specifies the input, axiom, and goal states.
- Scoring rules: The system uses base-pair, multiloop, single-loop, and hairpin scoring parameters.These parameters correspond to the scoring components used by the actual systems.
- Jumping operations: The next(i, j) operation returns the next position after xj that can pair with xi, implementing the jumping trick used in CONTRAfold and ViennaRNA.The final two rules also use this operation on their right-hand sides.
- Runtime structure: The reduce rule, an intermediate multiloop step, is the only cubic-time rule in the described system.Its design is inspired by CONTRAfold source code.
E Connections between Context-Free Parsing and RNA Folding
LinearFold is connected to incremental parsing for context-free grammars through an alternative left-to-right formulation. The supplementary comparison places classical bottom-up RNA folding and parsing alongside left-to-right parsing algorithms.
- Algorithmic connection: RNA folding and natural-language parsing share isomorphic classical bottom-up O(n^3) algorithms.The comparison is framed through context-free grammar parsing.
- Algorithmic connection: Incremental parsing provides a left-to-right perspective for relating parsing algorithms to RNA folding.The figure distinguishes left-to-right algorithms from bottom-up methods.
- Parsing precedents: Knuth’s O(n) LR algorithm applies only to a small subset of context-free grammars, while Tomita generalizes the approach to arbitrary grammars with an alternative left-to-right O(n^3) algorithm.These parsing results motivate the corresponding alternative formulation for RNA folding.