CoChat
Sign Up
Cited by 215RNA and protein synthesis mechanismsGenomics and Phylogenetic StudiesAlgorithms and Data Compression

The DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search

Open access
Huang, Liang, Zhang, He, Deng, Dezhong, Zhao, Kai, Liu, Kaibo, Hendrix, David A, Mathews, David H·2019·Bioinformatics
DOI 10.1093/bioinformatics/btz375PMC PMC6681470
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

Overview

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/btz375

Cites

64 of 64 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1. Summary of our work. (A) Secondary structure representations of E.coli tRNAGly; (B) the corresponding dot-bracket format and an illustration of our algorithm, which scans the sequence left-to-right, and tags each nucleotide as ‘.’ (unpaired), ‘(’ (to be paired with a future nucleotide) or ‘)’ (paired with a previous nucleotide). (C) Comparison between our work and existing ones. L is the limit of pair distance in local folding methods (often ≤150), and b is the beam size in our work (default 100). Our algorithm, though approximate, is the first to achieve linear runtime without imposing constraints on the output structure
Fig. 1. Summary of our work. (A) Secondary structure representations of E.coli tRNAGly; (B) the corresponding dot-bracket format and an illustration of our algorithm, which scans the sequence left-to-right, and tags each nucleotide as ‘.’ (unpaired), ‘(’ (to be paired with a future nucleotide) or ‘)’ (paired with a previous nucleotide). (C) Comparison between our work and existing ones. L is the limit of pair distance in local folding methods (often ≤150), and b is the beam size in our work (default 100). Our algorithm, though approximate, is the first to achieve linear runtime without imposing constraints on the output structureCC BY-NC · PubMed Central
Fig. 2. Illustration of the LinearFold approach, using a short sequence CCAGG and the simple scoring function (Eq. 2). (A) An example state and an example (actually optimal) path, showing states (predicted prefix structures), actions (push ‘(’, skip ‘.’, and pop ‘)’), and stacks (unpaired open brackets, which are shown in bold in states). (B) Two example paths (the optimal one in blue and a suboptimal one in green) and two essential ideas of left-to-right dynamic programming: merging equivalent states with identical stacks (Idea 1) and packing temporarily equivalent states sharing the same stack top, and corresponding unpacking upon pop (Idea 2). (C) Illustration of beam search, which keeps top b states (those in the shaded region) per step (Idea 3). (D) The whole search space of the naive algorithm (O(3n) time). (E) Improving to O(2n) time with Idea 1. (F) Further improving to O(n3) time with Idea 2. (G) Further improving to O(n) time (but with approximate search) with Idea 3. In B, F, and G, each green/blue arrow pair ?(?(. is actually a single arrow, denoting two paths temporarily packed as one; we draw paired arrows to highlight that two states .( and (( are performing skip action together. Note the version up to Idea 2 is exact and worst-case O(n3) time
Fig. 2. Illustration of the LinearFold approach, using a short sequence CCAGG and the simple scoring function (Eq. 2). (A) An example state and an example (actually optimal) path, showing states (predicted prefix structures), actions (push ‘(’, skip ‘.’, and pop ‘)’), and stacks (unpaired open brackets, which are shown in bold in states). (B) Two example paths (the optimal one in blue and a suboptimal one in green) and two essential ideas of left-to-right dynamic programming: merging equivalent states with identical stacks (Idea 1) and packing temporarily equivalent states sharing the same stack top, and corresponding unpacking upon pop (Idea 2). (C) Illustration of beam search, which keeps top b states (those in the shaded region) per step (Idea 3). (D) The whole search space of the naive algorithm (O(3n) time). (E) Improving to O(2n) time with Idea 1. (F) Further improving to O(n3) time with Idea 2. (G) Further improving to O(n) time (but with approximate search) with Idea 3. In B, F, and G, each green/blue arrow pair ?(?(. is actually a single arrow, denoting two paths temporarily packed as one; we draw paired arrows to highlight that two states .( and (( are performing skip action together. Note the version up to Idea 2 is exact and worst-case O(n3) timeCC BY-NC · PubMed Central
Fig. 3. Efficiency and scalability of LinearFold. (A) Runtime comparisons on the ArchiveII dataset with the two baselines, CONTRAfold MFE and Vienna RNAfold. (B) Runtime comparisons on the RNAcentral dataset (log–log). (C) Memory usage comparisons (RNAcentral set, log–log). LinearFold uses O(n) time and memory, being substantially faster and slimmer than the O(n3)-time, O(n2)-space, baselines on long sequences
Fig. 3. Efficiency and scalability of LinearFold. (A) Runtime comparisons on the ArchiveII dataset with the two baselines, CONTRAfold MFE and Vienna RNAfold. (B) Runtime comparisons on the RNAcentral dataset (log–log). (C) Memory usage comparisons (RNAcentral set, log–log). LinearFold uses O(n) time and memory, being substantially faster and slimmer than the O(n3)-time, O(n2)-space, baselines on long sequencesCC BY-NC · PubMed Central
Fig. 4. Accuracy of LinearFold. (A) Each bar represents PPV/sensitivity averaged over all sequences in one family. Statistical significance is marked as *(0.01​≤​P​<​0.05) or **(P​<​0.01). See Table 2 for details. (B) The overall accuracies, averaging over all families. (C) Each bar represents the overall PPV/sensitivity of all base pairs in a certain length range across all sequences. Supplementary Figure SI 1. shows a similar result for LinearFold-V. Overall, LinearFold outperforms exact search baselines, especially on longer families and long-range pairs
Fig. 4. Accuracy of LinearFold. (A) Each bar represents PPV/sensitivity averaged over all sequences in one family. Statistical significance is marked as *(0.01​≤​P​<​0.05) or **(P​<​0.01). See Table 2 for details. (B) The overall accuracies, averaging over all families. (C) Each bar represents the overall PPV/sensitivity of all base pairs in a certain length range across all sequences. Supplementary Figure SI 1. shows a similar result for LinearFold-V. Overall, LinearFold outperforms exact search baselines, especially on longer families and long-range pairsCC BY-NC · PubMed Central
Fig. 5. Search error (model score gap or free energy gap ΔΔG). (A) Average free energy gap (Vienna RNAfold vs. LinearFold-V) and model cost gap (CONTRAfold vs. LinearFold-C) with varying beam size; the search error shrinks with beam size, quickly converging to 0. (B and C) The search error (or gap) grows linearly with sequence length. Here, tmRNA is the outlier with disproportionally severe search errors, which can explain the slightly worse accuracies of LinearFold on tmRNA in Figure 4A. See Supplementary Figure SI 3. for a close-up on short sequences
Fig. 5. Search error (model score gap or free energy gap ΔΔG). (A) Average free energy gap (Vienna RNAfold vs. LinearFold-V) and model cost gap (CONTRAfold vs. LinearFold-C) with varying beam size; the search error shrinks with beam size, quickly converging to 0. (B and C) The search error (or gap) grows linearly with sequence length. Here, tmRNA is the outlier with disproportionally severe search errors, which can explain the slightly worse accuracies of LinearFold on tmRNA in Figure 4A. See Supplementary Figure SI 3. for a close-up on short sequencesCC BY-NC · PubMed Central
Fig. 6. Impacts of beam size on prediction accuracy. (A and C) PPV and sensitivity with varying beam size for LinearFold-C (A) and LinearFold-V (C); (B and D) PPV-sensitivity tradeoff for LinearFold-C (B) and LinearFold-V (D). Note that LinearFold with b = ∞ is exact search in O(n3) time (Idea 2) and produces identical results to the baselines
Fig. 6. Impacts of beam size on prediction accuracy. (A and C) PPV and sensitivity with varying beam size for LinearFold-C (A) and LinearFold-V (C); (B and D) PPV-sensitivity tradeoff for LinearFold-C (B) and LinearFold-V (D). Note that LinearFold with b = ∞ is exact search in O(n3) time (Idea 2) and produces identical results to the baselinesCC BY-NC · PubMed Central
Fig. 7. Circular plots of the prediction results on three RNA sequences (from three different RNA families) comparing the baselines (A–C: CONTRAfold MFE; G–I: Vienna RNAfold) and our LinearFold (D–F: LinearFold-C; J–L: LinearFold-V). Correctly predicted base pairs are in blue (true positives), incorrectly predicted pairs in red (false positives) and missing true base pairs in light gray (false negatives). Each plot is clockwise from 5′ to 3′. We can observe that (i) our LinearFold greatly reduces the false positives, especially on CONTRAfold; (ii) our LinearFold correctly predicts many long-range pairs, e.g. LinearFold-C on all three sequences and LinearFold-V on E.coli 23S rRNA(L); (iii) our LinearFold is able to predict the longest 5′–3′ pairs, even with the beam size of 100, which is an order of magnitude smaller than the sequence lengths of 16S and 23S rRNAs. (iv) In almost all cases (except for LinearFold-V on B.subtilis 16S rRNA(K)), LinearFold substantially outperforms the corresponding baseline
Fig. 7. Circular plots of the prediction results on three RNA sequences (from three different RNA families) comparing the baselines (A–C: CONTRAfold MFE; G–I: Vienna RNAfold) and our LinearFold (D–F: LinearFold-C; J–L: LinearFold-V). Correctly predicted base pairs are in blue (true positives), incorrectly predicted pairs in red (false positives) and missing true base pairs in light gray (false negatives). Each plot is clockwise from 5′ to 3′. We can observe that (i) our LinearFold greatly reduces the false positives, especially on CONTRAfold; (ii) our LinearFold correctly predicts many long-range pairs, e.g. LinearFold-C on all three sequences and LinearFold-V on E.coli 23S rRNA(L); (iii) our LinearFold is able to predict the longest 5′–3′ pairs, even with the beam size of 100, which is an order of magnitude smaller than the sequence lengths of 16S and 23S rRNAs. (iv) In almost all cases (except for LinearFold-V on B.subtilis 16S rRNA(K)), LinearFold substantially outperforms the corresponding baselineCC BY-NC · PubMed Central
Fig. 8. Circular plots of prediction results using the local folding mode of Vienna RNAfold (which only predicts local pairs no more than 150nt apart) on the E.coli 23S rRNA (corresponding to Fig. 7I). Moreover, the O(nL2)-time local folding (with default L = 150) is twice as slow as the O(nblogb)-time LinearFold-V (with default b = 100)
Fig. 8. Circular plots of prediction results using the local folding mode of Vienna RNAfold (which only predicts local pairs no more than 150nt apart) on the E.coli 23S rRNA (corresponding to Fig. 7I). Moreover, the O(nL2)-time local folding (with default L = 150) is twice as slow as the O(nblogb)-time LinearFold-V (with default b = 100)CC BY-NC · PubMed Central

Verification

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.

A few free checks a day · papers already verified open instantly · results are public

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?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 63 references

Research works printed but not linked: 4

  1. Amman, 2013, Proceedings of the 8th Brazilian Symposium on Bioinformatics, BSB 2013, Recife, Brazil, 1
  2. Hofacker, 2014, RNA Folding: Methods and Protocols. Methods in Molecular Biology 1086, 1
  3. Huang, 2010, Proceedings of ACL. Uppsala, Sweden, 1077
  4. Tomita, 1988, Proceedings of ACL, 249

Cited by

Sorted by citations

Related

See all

Metadata

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
ORCID
Venue
Bioinformatics
Publisher
Oxford University Press (OUP)
Published
2019-07
Volume
35
Issue
14
Pages
i295-i304
ISSN
  • 1367-4803 (ISSN-L)
  • 1367-4811
DOI
10.1093/bioinformatics/btz375
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
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 › Mathematics › Theoretical Computer Science › 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