PaperlayerView exact revision on arXiv

Source-linked AI summary

RNA Secondary Structure Prediction By Learning Unrolled Algorithms

Xinshi Chen, Yu Li, Ramzan Umarov, Xin Gao, Le Song

arXiv:2002.05810v1cs.LGstat.ML

TL;DR

RNA secondary-structure prediction must account for hard pairing constraints, limited data, and structures that may contain pseudoknots. E2Efold directly predicts a base-pairing matrix and integrates an unrolled constraint-enforcing network. It outperforms previous state-of-the-art methods on reported accuracy measures while matching the fastest algorithms’ inference time.

  • Problem

    RNA prediction must account for hard structural constraints, while limited data makes it difficult for a naive network to learn those constraints and a separate post-processing stage leaves the predictor unaware of them.

    Source: §1 · p. 2

  • Method

    E2Efold jointly trains a transformer-based Deep Score Network with an unrolled Post-Processing Network that enforces constraints on the predicted structure.

    Source: §1 · p. 2, §4.1 · p. 4, §4.2 · p. 4

  • Results

    E2Efold outperforms previous state-of-the-art methods in F1 score, precision, and recall, predicts valid structures including pseudoknots, and runs as efficiently as the fastest algorithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors propose that unrolling constrained programming to enforce constraints may transfer to other problems, including protein folding and document correspondence.

    Source: §1 · p. 2, §7 · p. 9

    The stated pairing rules allow only AU, UA, GC, CG, GU, and UG nucleotide combinations to form base-pairs.

    Source: §3 · p. 3

Abstract

from arXiv · show

In this paper, we propose an end-to-end deep learning model, called E2Efold, for RNA secondary structure prediction which can effectively take into account the inherent constraints in the problem. The key idea of E2Efold is to directly predict the RNA base-pairing matrix, and use an unrolled algorithm for constrained programming as the template for deep architectures to enforce constraints. With comprehensive experiments on benchmark datasets, we demonstrate the superior performance of E2Efold: it predicts significantly better structures compared to previous SOTA (especially for pseudoknotted structures), while being as efficient as the fastest algorithms in terms of inference time.

1 INTRODUCTION

RNA structure prediction must handle constrained base-pairing, limited data, and pseudoknots without relying on a separate decoding step. E2Efold integrates prediction with an unrolled constraint-enforcing network and outperforms prior methods across reported accuracy measures while matching the fastest inference time.

1 INTRODUCTION

  • Existing energy-based methods face an exponentially large search space and often assume nested structures, excluding valid pseudoknots.Pseudoknots are reported in around 40% of RNAs and are overrepresented in functionally important regions.Source: §1 · pp. 1–2
  • A separate post-processing stage leaves the trained predictor unaware of the constraints applied afterward, limiting its use of that prior knowledge.The paper motivates integrating both stages in one end-to-end model.Source: §1 · p. 2
  • E2Efold jointly trains a transformer-based Deep Score Network and an unrolled Post-Processing Network that gradually enforces constraints.The post-processing architecture is based on an unrolled algorithm for constrained optimization.Source: §1 · p. 2
  • Its unrolled inductive bias restricts the output space to aid learning with limited data while retaining the flexibility to represent pseudoknots.The authors describe this as balancing learning biases with expressiveness for valid RNA structures.Source: §1 · p. 2
  • E2Efold outperforms previous state-of-the-art methods in F1 score, precision, and recall, predicts valid structures including pseudoknots, and runs as efficiently as the fastest algorithms.The reported comparisons span benchmark datasets and also describe predictions as visually close to true structures.Source: §1 · p. 2
  • The authors propose that learning unrolled algorithms to enforce constraints could also transfer to problems such as protein folding and document correspondence.They describe the approach as generic beyond RNA secondary structure prediction.Source: §1 · pp. 2–3

2 RELATED WORK

Prior RNA-folding approaches trade computational tractability against the ability to represent pseudoknots, while differentiable structured-prediction methods have not addressed this RNA setting effectively.

2 RELATED WORK

  • Classical energy-minimization methods typically use dynamic programming with nested-structure assumptions, while pseudoknot-capable heuristic methods still need better accuracy and efficiency.LinearFold runs in O(L) time but cannot handle pseudoknots; most pseudoknot methods use more computationally intensive approaches.Source: §2 · p. 3
  • Learning-based energy methods still rely on dynamic programming, while CDPfold cannot represent pseudoknots and requires costly post-processing for long sequences.The passage names ContraFold, ContextFold, and CDPfold.Source: §2 · p. 3
  • Prior differentiable-algorithm methods had not addressed RNA secondary structure constraints, and OptNet’s cubic complexity makes it prohibitive for this problem.The passage cites related work as Hershey et al. (2014), Belanger et al. (2017), Ingraham et al. (2018), Chen et al. (2018), and Shrivastava et al. (2019).Source: §2 · p. 3
  • Dependency parsing offers a related structured-prediction analogy, with deep models scoring word dependencies in a way similar to E2Efold’s Deep Score Network.The passage cites McDonald et al. (2005), Dozat & Manning (2016), and Kiperwasser & Goldberg (2016).Source: §2 · p. 3

3 RNA SECONDARY STRUCTURE PREDICTION PROBLEM

RNA secondary structure prediction maps a nucleotide sequence to a binary pairing matrix subject to base-pairing, loop-length, and matching constraints.

3 RNA SECONDARY STRUCTURE PREDICTION PROBLEM

  • Only AU, UA, GC, CG, GU, and UG nucleotide combinations can pair, and pairs with fewer than four positions between bases are disallowed.These rules exclude illegal pairings based on nucleotide type and relative position.Source: §3 · p. 3
  • No nucleotide may participate in overlapping pairs, so the pairing matrix must satisfy a global matching constraint.The passage distinguishes this global rule from the base-type and relative-position constraints.Source: §3 · p. 3
  • Valid structures are symmetric binary matrices satisfying all three constraints, forming a smaller output space that can support learning with less training data.The paper uses an unrolled algorithm as the inductive bias for incorporating these constraints into the architecture.Source: §3 · p. 4

4 E2EFOLD: DEEP LEARNING MODEL BASED ON UNROLLED ALGORITHM

E2Efold addresses limited RNA data and hard structure constraints by pairing a sequence-scoring network with an unrolled constrained-optimization network trained jointly. The architecture incorporates constraints into prediction while retaining an expressive output space.

4.1 DEEP SCORE NETWORK

  • The Deep Score Network maps an L × 4 one-hot sequence to symmetric L × L pair scores using position embeddings, Transformer encoders, and 2D convolutions.Each matrix entry scores whether two nucleotides are paired.Source: §4.1 · p. 4

4 E2EFOLD: DEEP LEARNING MODEL BASED ON UNROLLED ALGORITHM

  • E2Efold jointly trains a transformer-based Deep Score Network with a Post-Processing Network designed by unrolling constrained optimization.This combines base-pair scoring and constraint enforcement rather than leaving post-processing unaware of the scoring network.Source: §4.2 · p. 4, §4 · p. 4

4.2.1 POST-PROCESSING WITH CONSTRAINED OPTIMIZATION

  • Post-processing formulates structure selection as maximizing score agreement under constraints, relaxes binary A to [0, 1], and parameterizes feasible matrices through T.The transformation encodes pairing-type and minimum-separation constraints; the formulation reduces the search to free variables with L inequality constraints.Source: §4.2.1 · p. 5

4.2.2 POST-PROCESSING NETWORK VIA AN UNROLLED ALGORITHM

  • The differentiable, tuning-free Post-Processing Network connects to Uθ for joint training, making score-network training aware of constraint enforcement.Clipping keeps intermediate  values in [0, 1] for computing losses over intermediate outputs.Source: §4.2.2 · pp. 5–6
  • A primal-dual iterative solver supplies the template; PPcellφ updates pairing variables and multipliers using learnable step sizes, decay rates, sparsity, and offset parameters over fixed T iterations.The update iterations are fixed manually rather than run until convergence.Source: §4.2.1 · p. 5, §4.2.2 · p. 6

5 END-TO-END TRAINING ALGORITHM

The training algorithm uses a differentiable F1-based objective and supervises intermediate outputs across the optimization trajectory. It also uses logistic-regression pretraining for the Deep Score Network.

5 END-TO-END TRAINING ALGORITHM

  • A differentiable loss mimics F1 using continuous true-positive, false-positive, and false-negative quantities, allowing the training objective to optimize F1 directly.The paper optimizes F1 rather than precision or recall losses.Source: §5 · p. 6
  • F1 loss handles the abundance of negative samples automatically, whereas ℓ2 and cross-entropy losses require a hand-tuned balancing weight.The passage notes this may be useful for other problems as well.Source: §5 · p. 6
  • The overall objective includes auxiliary losses on the optimization trajectory’s intermediate outputs to guide a smooth solution trajectory.E2Efold produces an intermediate matrix A_t at each iteration.Source: §5 · p. 7
  • The Deep Score Network is empirically useful to pre-train with logistic regression loss, which can also be added to the overall objective as regularization.The passage reports both practices as helpful.Source: §5 · p. 7

6 EXPERIMENTS

On RNAStralign, E2Efold outperforms previous methods across evaluation criteria and retains an advantage on ArchiveII without retraining. It has inference time similar to LinearFold on GPU, while experiments also assess pseudoknot prediction, visual similarity, ablations, and performance across RNA families.

Dataset; Experiments On RNAStralign

  • The experiments use ArchiveII, with 3,975 structures from 10 RNA types, and RNAStralign, with 30,451 structures remaining after redundancy removal.RNAStralign is split into stratified training, testing, and validation sets; evaluation reports per-sequence F1, precision, and recall, also allowing one-position shifts.Source: §6 · p. 7, Table 1 · p. 7

Experiments On RNAStralign

  • E2Efold improves F1 score by 29.7% on RNAStralign and outperforms previous methods across criteria by at least 20%.Its F1-score distribution also indicates consistently good performance.Source: Table 2 · p. 7, §6 · pp. 7–8, Figure 5 · p. 7

Test On ArchiveII Without Re-training

  • On ArchiveII sequences with RNA types overlapping RNAStralign, E2Efold performs better than all other methods across evaluation criteria without retraining, though less well than on RNAStralign.The comparison excludes overlapping sequences; the authors describe ArchiveII as having a very different data distribution from the RNAStralign training set.Source: Table 3 · p. 8, §6 · p. 8

Inference Time Comparison

  • On GPU, E2Efold has inference time similar to LinearFold, the most efficient baseline in the comparison.CDPfold is extremely slow, which the authors attribute to its dynamic-programming post-processing step.Source: Table 4 · p. 8, §6 · p. 8

Pseudoknot Prediction

  • The pseudoknot evaluation measures F1 on sequences containing pseudoknots and counts correctly predicted pseudoknotted sequences as true positives.RNAstructure is the comparison method because most tools exclude pseudoknots.Source: Table 5 · p. 8, §6 · p. 8

Visualization

  • For most visualized examples, E2Efold predictions are most similar to the ground-truth structures among the compared methods.RNAstructure and CONTRAfold capture a rough sketch, but are not considered good enough; E2Efold also works well on some long, difficult sequences.Source: §6 · pp. 8–9

Ablation Study

  • E2Efold significantly outperforms the disconnected “Uθ + PP” variant, supporting the value of training the Deep Score Network with post-processing connected.The disconnected variant applies post-processing after the Deep Score Network has been learned.Source: Table 6 · p. 9, §6 · p. 9

Discussion

  • A single E2Efold model performs significantly better than other methods on 16S rRNA, tRNA, 5S RNA, tmRNA, and telomerase.The authors suggest future work could train multiple family-specific models and a classifier to select among them.Source: §6 · p. 9

7 CONCLUSION

E2Efold incorporates hard constraints into its architecture, and the paper presents unrolled constrained programming as potentially useful beyond RNA prediction. The related-work discussion distinguishes this goal from learning a more flexible algorithm and describes a differentiable loss that mimics F1, precision, and recall.

7 CONCLUSION

  • E2Efold incorporates hard constraints into its architecture for RNA secondary structure prediction; the authors also see unrolling constrained programming as potentially useful for other structured prediction problems.They identify RNA types with fewer samples as an area needing further study.Source: §7 · p. 9

A MORE DISCUSSION ON RELATED WORKS

  • The authors frame constraint incorporation as a way to reduce output space and sample complexity, contrasting their approach with prior work that did not discuss these aspects.They describe OptNet as too expensive to scale to the RNA problem.Source: A MORE DISCUSSION ON RELATED WORKS · p. 12
  • Unlike approaches that make an algorithm more flexible, E2Efold keeps the original algorithm structure and makes only its hyperparameters learnable to enforce constraints.The comparison is with Chen et al. (2018) and Shrivastava et al. (2019).Source: A MORE DISCUSSION ON RELATED WORKS · p. 12
  • The authors propose a differentiable loss that mimics F1, precision, and recall, which they say is useful when positive and negative samples are imbalanced in either direction.They note that the compared end-to-end works could not directly optimize F1.Source: A MORE DISCUSSION ON RELATED WORKS · p. 12

B DERIVATION OF THE PROXIMAL GRADIENT STEP

The appendix derives a proximal-gradient step by rewriting a maximization as minimization and using a quadratic approximation. It then defines a proximal mapping and relates the resulting update to the main-text procedure.

B DERIVATION OF THE PROXIMAL GRADIENT STEP

C IMPLEMENTATION AND TRAINING DETAILS

The appendix specifies E2Efold’s network configuration and training procedure, including separate pretraining and joint fine-tuning. It also presents RNAStralign split statistics and a sequence-length distribution.

C IMPLEMENTATION AND TRAINING DETAILS

  • The Deep Score Network uses a transformer encoder with 2 heads and a 2048-dimensional feed-forward network, followed by pairwise features and 2D convolutions that produce the score matrix.The final model sets d to 10; the convolutional channels change from 6*d to d and then 1.Source: C IMPLEMENTATION AND TRAINING DETAILS · p. 13
  • The Post-Processing Network uses 20 unrolled iterations, with the listed initial values for its learnable parameters and hyperparameters.The appendix gives w=1, s=log(9), α=0.01, β=0.1, γα=γβ=0.99, and ρ=1.Source: C IMPLEMENTATION AND TRAINING DETAILS · p. 13
  • Training pretrains the Deep Score Network for 100 epochs with weighted binary cross-entropy, then fine-tunes it with the Post-Processing Network for 20 epochs using combined score-network and F1 losses.The positive-sample weight is 300 during pretraining; fine-tuning uses batch size 8 and updates parameters every 30 steps.Source: C IMPLEMENTATION AND TRAINING DETAILS · pp. 13–14

D.1 DATASET STATISTICS

  • The appendix reports RNAStralign split statistics in Table 7 and shows the dataset’s sequence-length distribution in Figure 6.The supplied captions identify the scope of these visuals but do not state their values.Source: Table 7 · p. 14, Figure 6 · p. 14

D.2 TWO-SAMPLE HYPOTHESIS TESTING

The appendix compares RNAStralign training and test distributions with ArchiveII using a permutation test on an unbiased empirical MMD estimator. It reports that the training and test distributions can be treated as matching at significance level 0.1, while ArchiveII differs; E2Efold also performs better on long sequences under length-weighted F1.

D.2 TWO-SAMPLE HYPOTHESIS TESTING

  • The comparison uses a permutation test on an unbiased empirical Maximum Mean Discrepancy estimator, with stratified resampling and 1,000 permutations.The stated hypotheses compare RNAStralign training with its test set and with ArchiveII.Source: §D.2 · pp. 14–15
  • The test accepts equality between the RNAStralign training and test distributions at significance level 0.1, but rejects equality between the training distribution and ArchiveII with p-value 0.Figure 7 shows the MMD_u distributions for the two hypotheses.Source: §D.2 · p. 15, Figure 7 · p. 15
  • The authors interpret E2Efold’s performance on ArchiveII as evidence of significant generalization power because ArchiveII’s data distribution is very different from the RNAStralign training set.The passage reports the distributional difference and the authors’ interpretation, without giving a performance value here.Source: §D.2 · p. 15

D.3 PERFORMANCE ON LONG SEQUENCES: WEIGHTED F1 SCORE

  • E2Efold still performs better than other methods on long sequences when F1 scores are weighted by sequence length.Table 8 reports these weighted scores, and its third row gives the F1-score drop after reweighting; no values are stated in the supplied passages.Source: Table 8 · p. 15, §D.3 · p. 15

D.4 ARCHIVEII RESULTS AFTER DOMAIN SEQUENCES ARE REMOVED

Filtering explicitly labeled ArchiveII subsequences leaves results broadly similar; the appendix also reports family-balanced sampling performance and visualizations of example RNA structures.

D.4 ARCHIVEII RESULTS AFTER DOMAIN SEQUENCES ARE REMOVED

  • ArchiveII results do not change much after explicitly labeled subsequences are filtered out.Table 9 reports F1 scores after filtering.Source: §D.4 · p. 15, Table 9 · p. 16

D.5 PER-FAMILY PERFORMANCES

  • 0.83 overall F1 score (S) with weighted sampling matches the score with equal-weighted sampling.Table 10 presents per-family performances.Source: §D.5 · p. 16, Table 10 · p. 16

D.6 MORE VISUALIZATION RESULTS

  • Figures 8–13 visualize examples of 5S rRNA (B01865), 16S rRNA (DQ170870), Group I intron (IC3, Kaf.c.trnL), RNaseP (A.salinestris-184), SRP (Homo.sapi. BU56690), and tmRNA (uncu.bact. AF389956).Source: Figure 8 · p. 17, Figure 9 · p. 17, Figure 10 · p. 18
Loading 2002.05810v1…