PaperlayerView exact revision on arXiv

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

arXiv:2001.04020v1q-bio.BMcs.DSmath.COphysics.bio-phq-bio.QM

TL;DR

Existing RNA-folding algorithms can be too slow for long sequences, while faster local methods restrict the structures they predict. LinearFold uses left-to-right dynamic programming with beam pruning; it runs in linear time and space and reports higher accuracy overall, especially on long families and long-range pairs.

  • Problem

    Existing dynamic-programming RNA folding scales cubically with sequence length, while faster local methods restrict predicted base pairs to short-range interactions.

    Source: §1 · p. 2

  • Method

    LinearFold scans RNA left to right with incremental dynamic programming and beam pruning, yielding approximate O(n) time and O(n) space.

    Source: §2.4 · p. 4, §2.5 · p. 4, §5 · p. 8

  • Results

    LinearFold was more accurate overall in PPV and sensitivity across thermodynamic and machine-learned models, with larger improvements on 16S/23S rRNAs and pairs over 500 nt apart.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The findings show approximate search can improve accuracy while using a fraction of existing algorithms’ time and memory.

    Source: §5 · p. 8

    The dynamic-programming approach requires a scoring function that decomposes into smaller structures.

    Source: §2.1 · p. 2

Abstract

from arXiv · show

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

LinearFold uses left-to-right dynamic programming and beam search for approximate RNA folding without restricting base-pair distance. The introduction reports higher average accuracy across families and gains on long sequences and long-range base pairs.

Motivation

  • RNA secondary structure, defined by canonical A–U, G–C, and G–U pairs, reveals functional information and supports applications such as ncRNA detection and oligonucleotide design.The introduction notes that experimental structure determination is expensive and time-consuming, motivating computational prediction.Source: §1 · p. 1
  • Standard folding algorithms take O(n^3) time, while linear-time local methods restrict pair distance, typically to L ≤150, and omit long-range pairs common in natural RNAs.Long sequences are also often divided into short segments for folding.Source: §1 · p. 2

Method

  • Scanning 5′-to-3′ and keeping the top b states per prefix yields approximate O(nb log b)-time, O(n)-space folding without a base-pair-distance constraint.The scan incrementally assigns dot-bracket symbols to nucleotides.Source: §1 · p. 2, Figure 1 · p. 2
  • A packed left-to-right dynamic program reduces the naive O(3^n) scan to O(n^3), providing a novel exact algorithm before beam pruning.The paper adapts an efficient packing idea from computational linguistics.Source: §1 · p. 2

Contributions

  • The approach can linearize any dynamic-programming pseudoknot-free RNA folding system, demonstrated with thermodynamic LinearFold-V and learned-model LinearFold-C.LinearFold-V uses the Vienna RNAfold thermodynamic model, while LinearFold-C uses the CONTRAfold machine-learned model.Source: §1 · p. 2

Results

  • LinearFold is substantially more efficient, achieves higher average accuracy across families, improves on exact search for 16S and 23S rRNAs, and predicts long-range pairs more accurately.The introduction describes the gains on 16S and 23S ribosomal RNAs and long-range pairs as particularly notable.Source: §1 · p. 2

2 The LinearFold Algorithm

LinearFold reformulates pseudoknot-free RNA folding as a left-to-right dynamic program, then applies beam pruning to obtain linear-time approximate search.

2.1 Problem Formulation

  • The task is to maximize a decomposable scoring function over pseudoknot-free structures, with valid pairs and balanced brackets defining admissible outputs.The simple presentation scores individual base pairs and penalizes unpaired nucleotides; the actual models decompose scores over loops.Source: §2.1 · p. 2

2.2 Idea 0: Brute-Force Search: O(3n)

  • A left-to-right exhaustive search uses push, skip, and pop actions to construct structures, but its up to three choices per step yield exponential O(3^n) runtime.Search starts and ends with an empty stack, ensuring a well-balanced dot-bracket output.Source: §2.2 · pp. 2–3

2.3 Idea 1 (DP): Merge States with Identical Stacks: O(2n)

  • Merging states with identical stacks retains only the highest-scoring history because those states are equivalent for future transitions, reducing search to O(2^n) but leaving exponentially many stacks.Source: §2.3 · p. 4

2.4 Idea 2 (DP): Pack Temporarily Equivalent States: O(n3)

  • Packing states with the same stack top lets them share computation until that bracket closes, when they unpack; the exact algorithm runs in worst-case O(n^3).The packed state tracks a substructure and score for the substring between its two indices; its scoring does not depend on the histories before packing.Source: §2.4 · p. 4

2.5 Idea 3 (Approximate Search): Beam Pruning: O(n)

  • Beam pruning keeps the top b states per step, yielding approximate O(nb log b) time and O(nb) space; with default constant b=100, runtime is linear in sequence length.The implementation limits interior-loop length and the leftmost unpaired multiloop segment to 30 nucleotides; neither restriction was violated in ArchiveII.Source: §2.5 · p. 4
  • LinearFold-C scored 55.84 PPV (+1.3) and 56.24 sensitivity (+0.9), versus CONTRAfold MFE’s 54.51 PPV and 55.36 sensitivity.Figure 4 reports that LinearFold’s gains are especially notable on longer families and long-range pairs.Source: §2.5 · p. 5, Figure 4 · p. 5
  • LinearFold-V scored 50.51 PPV (+0.3) and 58.97 sensitivity (+0.2), versus Vienna RNAfold’s 50.22 PPV and 58.74 sensitivity.Figure 4 reports that LinearFold’s gains are especially notable on longer families and long-range pairs.Source: §2.5 · p. 5, Figure 4 · p. 5

3 Results

LinearFold combines near-linear runtime and linear-space folding with accuracy gains over exact-search baselines, particularly for long sequences and long-range base pairs. Its search quality improves with larger beams, and example predictions show it recovering distant pairs while reducing false positives.

3.1 Efficiency and Scalability

  • LinearFold runtime scales near-linearly on ArchiveII and linearly on RNAcentral; at 10,000nt it takes 8 seconds versus 4 minutes, and at 32,753nt it takes 26 seconds versus 2 and 1.7 hours.At 32,753nt, the baseline times are 2 hours for CONTRAfold and 1.7 hours for RNAfold.Source: §3.1 · p. 5
  • LinearFold uses O(n) space, folds RNAcentral’s 244,296nt longest sequence within 3 minutes, and predicts unbounded-distance pairs; neither baseline runs beyond 32,767nt.Classical O(n^3)-time algorithms use O(n^2) space; the baseline length limit is due to data-structure limitations.Source: §3.1 · p. 5

3.2 Accuracy

  • +1.3%/+0.9% PPV/sensitivity over CONTRAfold and +0.3%/+0.2% over RNAfold overall; gains were larger on the longest 16S and 23S rRNA families.On 16S rRNA, LinearFold-C improved PPV/sensitivity by +3.56%/+3.09%; on 23S rRNA, by +8.65%/+5.66%.Source: §3.2 · p. 5

3.3 Search Quality

  • Search error shrinks toward zero as beam size increases and grows linearly with sequence length at b=100, leaving average error per nucleotide unchanged.The search error is the score or free-energy gap between exact search and the beam-search structure.Source: Figure 5 · p. 6, §3.3 · p. 6

3.4 Impacts of Beam Size on Prediction Accuracy

  • LinearFold-C outperforms CONTRAfold MFE in PPV and sensitivity at b≥75, is stable for b=100–150, and peaks at b=120 before declining toward exact search.Beam size 100 is the untuned default; LinearFold-V shows a similar trend.Source: Figure 6 · p. 6, §3.4 · p. 6

3.2 Accuracy

  • For base pairs more than 500nt apart, LinearFold has higher PPV and sensitivity than exact search; its accuracy also does not degrade toward the 3′ end.The results indicate greater selectivity for long-range pairs while correctly predicting more such pairs; LinearFold also corrects exact-search baselines’ severe overprediction.Source: §3.2 · pp. 5–6

3.5 Example Predictions: Group I Intron, 16S & 23S rRNAs

  • Example predictions reduce false positives and recover long-range pairs, including a 582nt pair in 23S rRNA and its longest 5′–3′ pair at 2,901nt.LinearFold-V on Bacillus subtilis 16S rRNA is the stated exception to substantial improvement over the corresponding baseline.Source: §3.5 · p. 6, Figure 7 · p. 7
  • Local RNAfold folding capped at 150nt predicts no long-range pairs; its default mode is twice as slow as LinearFold-V with b=100.The comparison is for E. coli 23S rRNA; the local-folding limit is the largest default limit cited for local-folding methods and software.Source: Figure 8 · p. 8, §3.5 · p. 8

4 Discussion

The authors suggest that beam search can outperform exact-search baselines because imperfect scoring and prefix-based pruning favor accurate suboptimal structures; they also propose that incremental folding may better reflect cotranscriptional folding. They describe other speedup algorithms as orthogonal to their left-to-right approach.

4 Discussion

  • Beam search can outperform exact-search baselines in accuracy, especially for 16S and 23S rRNAs and long-range base pairs.The authors attribute this to several possible factors, rather than to a single established cause.Source: §4 · p. 8
  • Imperfect scoring can make a suboptimal structure more accurate: the lowest-free-energy structure contains 72.9% of actual base pairs, while one within 4.8% of optimal free energy contains 86.1%.Source: §4 · p. 8
  • Beam pruning requires highly scored structures at each prefix and may act like regularization, helping LinearFold select more accurate suboptimal structures without ground truth.The authors note that this phenomenon has also been observed in computational linguistics.Source: §4 · p. 8
  • The authors hypothesize that some RNAs evolved to fold cotranscriptionally, making LinearFold’s 5′-to-3′ approach more accurate than bottom-up baselines; Supplementary Fig. SI5B shows a slight preference over 3′-to-5′ order.They relate this incremental folding hypothesis to psycholinguistic evidence that people parse sentences before finishing them.Source: §4 · p. 8
  • Other faster RNA-folding algorithms build on the classical bottom-up method and are orthogonal to LinearFold’s left-to-right approach; a linear-time structure-analysis algorithm does not predict structures de novo.The cited alternatives include Four-Russians, fast-matrix-multiplication, and context-free-parsing approaches, and structure analysis.Source: §4 · p. 8

5 Conclusion and Future Work

LinearFold combines incremental dynamic programming with beam search to achieve linear-time, linear-space approximate RNA folding. The authors report improved prediction accuracy and outline extensions to probabilistic folding, pseudoknot prediction, cotranscriptional folding, and parameter training.

Conclusion

  • The algorithm uses incremental dynamic programming with beam search to achieve O(n) time and O(n) space for approximate RNA folding.It is applied to both machine-learned and thermodynamic models.Source: §5 · p. 8
  • LinearFold is more accurate overall in PPV and sensitivity across both machine-learned and thermodynamic models, especially on 16S/23S rRNAs and base pairs over 500 nt apart; predictions are stable for beam sizes 100–200.The authors note that accuracy improvement is more pronounced on longer families and that long-range pairs are challenging for current models.Source: §5 · p. 8
  • Unlike local folding algorithms that limit pair distance, LinearFold permits unbounded distances, which occur commonly in natural RNA structures.The cited evidence includes the nearly linear growth of longest-pair length with sequence length n (Li and Reidys, 2018) and the nearly constant, short distance between folded 5′–3′ ends.Source: §5 · p. 8

Future Work

  • The authors propose extending the approach to calculate partition functions and base-pair probabilities, then using linear-time probabilities to facilitate heuristic or direct pseudoknot prediction.The proposals draw on McCaskill (1990), Bellaousov and Mathews (2010), Sato et al. (2011), Dirks and Pierce (2003), and Reeder and Giegerich (2004).Source: §5 · p. 8
  • Future work will test whether beams capture cotranscriptional folding and use LinearFold’s speed to train parameters faster and develop a more accurate model tailored to its search.The training comparison is with cubic-time CONTRAfold using structured prediction methods.Source: §5 · p. 8

A Extra Definitions

This section formalizes allowed pseudoknot-free secondary structures and defines predicates and sets used to describe structure strings and their relation to sequences.

A Extra Definitions

  • Allowed pseudoknot-free secondary structures are introduced using a balance condition based on the difference between counts of “(” and “)” in y.The supplied passage does not include the full iff condition for balanced(y).Source: A Extra Definitions · p. 11
  • The section defines the set of pairs in y.The set’s formal expression is omitted from the supplied passage.Source: A Extra Definitions · p. 11
  • The predicate valid(x, S) checks whether all pairs in S are valid for x.The supplied passage does not include its full iff condition.Source: A Extra Definitions · p. 11
  • The unpaired indices in y are defined as unpaired(y) = {i | y_i = .}.Source: A Extra Definitions · p. 11

B Actual Scoring Functions

The scoring functions for CONTRAfold, RNAfold, and LinearFold decompose RNA structures into loop scores, with multiloop scores further divided by adjacent base pairs. Vienna RNAfold uses thermodynamic features, while CONTRAfold learns weights within the same loop-scoring framework.

B Actual Scoring Functions

  • CONTRAfold, RNAfold, and LinearFold score structures by decomposing them into hairpin, single, multiloop, and external loops.Single loops include bulges, internal loops, and stacking.Source: B Actual Scoring Functions · p. 11
  • Multiloop scores are further decomposed into contributions from each adjacent base pair in the multiloop.For an example structure, the paper identifies a multiloop, its adjacent base pairs and unpaired bases, as well as the structure’s hairpin, single, and external loops.Source: B Actual Scoring Functions · p. 11
  • Vienna RNAfold scores loop types with thermodynamic feature templates, whereas CONTRAfold substitutes weights learned from data in the same framework.The passage also states that LinearFold implements this scoring function.Source: B Actual Scoring Functions · p. 11

C Extra Results Tables and Figures

The extra tables report LinearFold’s accuracy comparisons on ArchiveII, while the accompanying passages describe evaluation criteria, dataset scope, and beam-size effects on predicted base-pair counts.

C Extra Results Tables and Figures

  • The ArchiveII evaluation used 2,889 sequences across nine families, averaging 222.2 nt, after removing sequences present in CONTRAfold’s S-Processed training set.ArchiveII contains over 3,000 sequences with known secondary structures; RNAcentral sampling selected one sequence from each of 30 log-scale length bins spanning 1,000 to 244,296 nt.Source: C Extra Results Tables and Figures · p. 11
  • A base pair was counted correct if it matched ground truth or was displaced by one nucleotide on either strand; exact matching was also reported, with both PPV and sensitivity.The slipping criterion addresses uncertainty in comparative-analysis matches and equilibrium base-pair fluctuations.Source: C Extra Results Tables and Figures · p. 11, Table SI1 · p. 12, Table SI2 · p. 12
  • With one-nucleotide slipping, LinearFold-C exceeded CONTRAfold MFE by +1.33/+0.88 in PPV/sensitivity with sharpturn and +1.98/+1.42 without; LinearFold-V exceeded Vienna RNAfold by +0.28/+0.24.Among nine families, LinearFold-C was significantly better on Group I Intron, 16S, and 23S rRNAs; LinearFold-V was significantly better on SRP, Group I Intron, and 16S rRNAs.Source: Table SI1 · p. 12
  • With exact base-pair matching, LinearFold-C exceeded CONTRAfold MFE by +1.30/+0.86 in PPV/sensitivity with sharpturn and +1.90/+1.37 without; LinearFold-V exceeded Vienna RNAfold by +0.11/+0.06.Among nine families, LinearFold-C was significantly better on Group I Intron, 16S, and 23S rRNAs; LinearFold-V was significantly better on Group I Intron and 16S rRNAs.Source: Table SI2 · p. 12
  • Ground truth averaged 0.2776 pairs per nucleotide, with 7.6% pseudoknotted; LinearFold predicted more pairs as beam size increased and nearly baseline counts at default size.At default beam size, it predicted 0.0002 and 0.0012 fewer pairs per nucleotide than the baselines, respectively.Source: C Extra Results Tables and Figures · p. 12, Figure SI2 · p. 13

D Deductive System for the Actual Systems

This section sketches LinearFold’s implemented deductive system using the real scoring functions. It describes the scoring parameters, pairing-position jump, and sole cubic-time rule.

D Deductive System for the Actual Systems

  • The system processes input x1...xn with axiom E⟨0, 1⟩ and goal E⟨0, n+1⟩.The figure depicts the implemented deductive system; shaded substrings represent balanced brackets.Source: D Deductive System for the Actual… · p. 14, Figure SI6 · p. 14
  • The scoring parameters cover external, multiloop, single-loop, and hairpin-loop energies.E denotes external loop; multi, S, and H denote multiloop, single loop, and hairpin loop, respectively.Source: D Deductive System for the Actual… · p. 14
  • The next(i, j) function jumps to the next position after xj that can pair with xi; reduce, an intermediate multiloop step, is the only cubic-time rule.The final two rules also use the jumping trick in their right-hand-side loop; the trick is used in CONTRAfold and ViennaRNA.Source: D Deductive System for the Actual… · p. 14

E Connections between Context-Free Parsing and RNA Folding

The section connects RNA folding with incremental context-free parsing: Tomita’s left-to-right algorithm inspires LinearFold Idea 2, and beam-pruned parsing inspires Idea 3.

E Connections between Context-Free Parsing and RNA Folding

  • Classical bottom-up O(n^3) algorithms are isomorphic across natural-language parsing and RNA folding, while Tomita’s left-to-right O(n^3) algorithm for arbitrary CFGs inspires LinearFold Idea 2.Knuth’s O(n) LR algorithm covers only a small subset of CFGs; Huang and Sagae generalized Tomita’s algorithm and combined it with beam search for linear runtime, inspiring Idea 3.Source: Figure SI7 · p. 15
Loading 2001.04020v1…