RNA Secondary Structure Prediction By Learning Unrolled Algorithms
Authors: Xinshi Chen
Yu Li
Ramzan Umarov
Xin Gao
Le Song
Venue:  (2020)
Keywords: RNA secondary structure prediction
learning algorithm
deep architecture design
computational biology

Abstract: 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.

Published as a conference paper at ICLR 2020
RNA SECONDARY STRUCTURE PREDICTION BY LEARNING UNROLLED ALGORITHMS
Xinshi Chen't, Yu Li Ramzan Umarov?, Xin Gao Le Song 1331
GGorgia Tech "KAUST 3 *Ant Financial
xinshi, chen@gatech.
{yu. [yu.li; ramzan. umarov; xin. gao edu. lsongêee gatech. edu
ABSTRACT
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 directly pre- dict 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 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 inference time.
benchmark datasets, we demonstrate the superior
INTRODUCTION
Ribonucleic acid (RNA) is molecule playing essential roles in numerous cellular processes and regulating expression of genes (Crick, 1970). It consists of an ordered sequence of nu- cleotides, with each nucleotide containing one of four bases: Adenine (A), Guanine (G), Cytosine (C) and Uracile (U). This sequence of bases can be represented as
matrirreppesentttiinn
(II, (II,..., .I) where x; E CA,,
which known as the primary structure of RNA. The bases can bond with one another to form a set of base-pairs, which defines the secondary structure. A secondary structure can be represented by a binary matrix A' where Ai = 1 if the i, j-th bases are paired (Fig 1). Discovering the secondary structure of RNA is important for understanding functions of RNA since the structure essentially affects the interaction and reaction between RNA and other cellular components. Although secondary structure can be determined by experimental assays (e.g. X-ray diffraction), it is slow, expensive and technically challenging. Therefore, compu- tational prediction of RNA secondary structure becomes an important task in RNA research and is useful in many applications such as drug design (Jorns al., 2007).
Figure 1: Graph and matrix represen- tations of RNA secondary structure.
Research on computational prediction of RNA secondary structure from knowledge of primary structure has been carried out for decades. Most existing methods assume the secondary structure
() Nested Structure
Pseudo-knot
result of energy minimiza- tion, i.e., A" = arg min, Ex(A).. The energy function either estimated by physics-based thermodynamic ex- periments (Lorenz et al., 2011; Bellaousov et al., 2013; Figure 2: Nested and non-nested structures. Markham & Zuker, 2008) or learned from data (Do et al., 2006). These approaches are faced with common problem that the search space of all valid sec- ondary structures is exponentially-Larg with respect to the length L of the sequence. To make the minimization tractable, it is often assumed the base-pairing has nested structure (Fig 2 left), and
" Equul contribution. 'Co-correpooddin.

---

Published as a conference paper at ICLR 2020
the energy function factorizes pairwisely. With this assumption, dynamic programming (DP) based algorithms can iteratively find the optimal structure for subsequences and thus consider an enormous number of structures in time (L))).
Although DP-based algorithms have dominated RNA structure prediction, it is notable that they restrict the search space nested structures, which excludes some valid yet biologically important RNA secondary structures that contain "pseudoknots', i.e., elements with at least two non-nested base-pairs (Fig 2 right). Pseudoknots make up roughly 1.4% of base-pairs (Mathews & Turner, 2006), and are overrepresented in functionally important regions (Hajdin et al., 2013; Staple & Butcher, 2005). Furthermore, pseudoknots are present in around 40% of the RNAs. They also assist folding into 3D structures (Fechter et al., 2001) and thus should not be ignored. To predict RNA structures with pseudoknots, energy-basee methods need to run more computationally intensive algorithms to decode the structures.
In summary, the presence of more complex structured output (i.e., pseudoknots), it challenging for energy-based approaches simultaneously take into account the complex constraints while be- ing efficient. In this paper, we adopt a different viewpoint by assuming that the secondary structure is the output of feed-forward function, i.e., A = Fo()), and propose to learn 0 from data in an end-to-end fashion. avoids the second minimization step needed in energy function based ap- proach, and does not require the output structure to be nested. Furthermore, the ferd-forward model can be fitted by directly optimizing the loss that one is interested in.
Despite the above advantages of using feed-forwart model, the architecture design is challenging. To be more concrete, in the RNA case, Fo is difficult to design for the following reasons:
(i) RNA secondary structure needs obey certain hard constraints (see details in Section 3), which means certain kinds of pairings cannot occur at all (Steeg, 1993). Ideally, the output of Fo needs to satisfy these constraints.
(ii) The number of RNA data points is limited, so we cannot expect that naive fully connected network can learn the predictive information and constraints directly from data. Thus, inductive biases need to be encoded into the network architecture.
(iii) One may take two-step approach, where a post-proeet post-processing step can be carried out enforce the constraints when Fe predicts an invalid structure. However, in this design, the deep network trained in the first stage is unaware of the post-processing stage, making less effective use of the potential prior knowledge encoded in the constraints.
In this paper, we present an end-to-end deep learning solution which integrates the two stages. The first part of the archi- tecture is a transformer-base Network which represents sequence information useful for structure prediction. The second part is a multilayer network called Post-Processing Network which gradually enforces the constraints and restrict the output space. It is designed based on unrolled algorithm for solving constrained optimiza- tion. These two networks are coupled together and learned
All Binary Structures
deep model called Deep Score
Output Space of E2Efold
*All Valid Structures* *
with constraints
Nested Structures (DP applicatie
Figure 3: Output space of E2Efold. jointly in an end-to-end fashion. Therefore, we call our model E2Efold.
By using an unrolled algorithm as the inductive bias to design Post-Processing Network, the output space of E2Efold is constrained (illustrated in Fig 3), which makes easier to learn good model in the case of limited data and also reduces the overfitting issue. Yet, the constraints encoded in E2Efold are flexible enough such that pseudoknots are not excluded. In summary, E2Efold strikes a nice balance between model biases for learning and expressiveness for valid RNA structures.
We conduct extensive experiments to compare E2Efold with otate-of-the-art (SOTA) methods on several RNA benchmark datasets, showing superior performance of E2Efold including:
being able to predict valid RNA secondary structures including pseudoknots;
running as efficient as the fastest algorithm in terms of inference time;
producing structures that are visually close to the true structure;
better than previous SOTA in terms of Fl score, precision and recall.
Although in this paper we focus on RNA secondary structure prediction, which presents an impor- tant and concrete problem where E2Efold leads to significant improvements, our method is generic
2

---

Published as a conference paper at ICLR 2020
and can be applied to other problems where constraints need to be enforced or prior knowledge is provided. We imagine that our design idea of learning unrolled algorithm to enforce constraints can also be transferred to problems such protein folding and natural language understanding problems (e.g., building correspondence structure between different parts in a document).
2 RELATED WORK
Classical RNA folding methods identify candidate structures for an RNA sequence energy min- imization through DP and rely on thousands of experimentally-eesuure
thermodynamic parame- ters. A few widely used methods such as RNAstructure (Bellaousov al., 2013), Vienna RNAfold (Lorenz et al., 2011) and UNAFold (Markham & Zuker, 2008) adpoted this approach. These meth- ods typically scale as OLL)) in time and (L*) in storage (Mathews, 2006), making them slow for long sequences. A recent advance called LinearFold (Huang al., 2019) achieved linear run time (L) by applying beam search, but it can not handle pseudoknots in RNA structures. The prediction of lowest free energy structures with pseudoknots is NP-complete (Lyngsø & Pedersen, 2000), so pseudoknots are not considered in most algorithms. Heuristic algorithms such as HotKnots (An- dronescu al., 2010) and Probknots (Bellaousov & Mathews, 2010) have been made to predict structures with pseudoknots, but the predictive accuracy and efficiency still need to be improved.
Learning-based RNA folding methods such ContraFold (Do et al., 2006) and ContextFold (Za- kov et al., 2011) have been proposed for energy parameters estimation due to the increasing avail- ability of known RNA structures, resulting in higher prediction accuracies, but these methods still rely on the above DP-based algorithms for energy minimization. A recent deep learning model, CDPfold (Zhang et al., 2019), applied convolutional neural networks to predict base-pairings, but adopts the dot-bracket representation for RNA secondary structure, which can not represent pseu- doknotted structures. Moreover, requires a DP-based post post-processing step whose computational complexity is prohibitive for sequences longer than a few hundreds.
Learning with differentiable algorithms a useful idea that inspires a series of works (Hershey et al., 2014; Belanger et al., 2017; Ingraham et al., 2018; Chen et al., 2018; Shrivastava et al., 2019), which shared similar idea of using differentiable unrolled algorithms as a building block in neural architectures. Some models are also applied to structured prediction problems (Hershey al., 2014; Pillutla et al., 2018; Ingraham et al., 2018), but they did not consider the challenging RNA sec- ondary structure problem or discuss how to properly incorporating constraints into the architecture. OptNet (Amos & Kolter, 2017) integrates constraints by differentiating KKT conditions, but has cubic complexity in the number of variables and constraints, which prohibitive for the RNA case.
Dependency parsing in NLP is a different but related problem to RNA folding. It predicts the de- pendency between the words in sentence. Similar to nested/non-nestee structures, the correspond- ing terms in NLP are berecciveenon-prjjjeete based inference algorithms are commonly used (McDonald et al., 2005). Deep learning mod- els (Dozat & Manning, 2016; Kiperwasser & Goldberg, 2016) are proposed to proposed to score the dependency between words, which has a similar flavor to the Deep Score Network our work.
parsing, where most works focus on the former and
RNA SECONDARY STRUCTURE PREDICTION PROBLEM
In the RNA secondary structure prediction problem, the input is the ordered sequence of bases x = (I1,..., and the output is the RNA secondary structure represented by a matrix A E {0, 12 Hard constraints the forming of RNA secondary structure dictate that certain kinds of pairings cannot occur at all (Steeg, 1993). Formally, these constraints are:
Only three types of nucleotides combinations, B = {AU,UA) {GC, CG) U UGU, can form base-pairs.
Vi,j. if 2,I, $ B, then Aij 0.
No sharp loops are allowed.
Vii 5l 4, Aij = 0. Vi, > Aij 5
There is no overlap of pairs, i.e., it a matching.
ii and (ii) prevent pairing of certain base-pairs pairs based their types and relative locations. Incorpo- rating these two constraints can help the model exclude lots of illegal pairs. (iii) is global constraint among the entries of A
3

---

Published as a conference paper at ICLR 2020
The space of all valid secondary structures contains all symmettrcc matrices A E {0, 1] 11f that satisfy the above three constraints. This space is much smaller than the space of all binary matrices {0, 1) 1 Therefore, if we could incorporate these constraints in deep model, the reduced output space could help us train a better predictive model with less training data. We do this by using unrolled algorithm as the inductive bias to design deep architecture.
4 E2EFOLD: DEEP LEARNING MODEL BASED ON UNROLLED ALGORITHM
In the literature on feed-forwad networks for structured prediction, most models are designed using traditional deep learning architectures. However, for RNA secondary structure prediction, directly using these architectures does not work well due to the limited amount of RNA data points and the hard constraints on forming an RNA secondary structure. These challenges motivate the design of E2Efold deep model, which combines Deep Score Network with a Post- Post-Processing Network based on an unrolled algorithm for solving a constrained optimization problem.
4.1 DEEP SCORE NETWORK
The first part of E2Efold is Deep Score Network (2) whose output is an L x L symmetric matrix. Each entry of this matrix, i.e., Uo(x) indicates the score of nucleotides æ; and zj being paired. The input to the network here is the L dimensional one-hot embedding. The specific architecture of Up is shown in Fig 4. It mainly consists of
position embedding matrix P which distinguishes {2:)//1 by their exact and relative positions: P. MLP 4/1 (f),..., (i), the+1 (i/ ()........ 1he (t/()) where {w) is of feature maps such as sin(-), poly(-), sigmoid()), etc, and MLP(.) denotes multi-layer perceptions. Such posi- tion embedding idea has been used in natural language modeling such as BERT (Devlin et al., 2018), but adapted for RNA sequence representation;
stack of Transformer Encoders (Vaswani et al., 2017) which encode the sequence information and the global dependency between nucleotides; 2D Convolution layers (Wang et al., 2017) for outputting the pairwise scores.
With the representation power of neural networks, the hope is that we can learn an informative Up such that higher scoring entries in (ar) correspond well to ac- tual paired bases in RNA structure. Once the score matrix (z(x) computed, a naive approach to use it is to choose an offset term E IR (e.g., and let A, = if U0());; > s. However, such entry-wise independent predictions of Aij may re- sult a matrix A that violates the constraints for a valid RNA secondary structure. Therefore, post- processing step is needed to make sure the predicted A is valid. This step could be carried out separately after Uo is learned. But such decoupling of base-pair scoring and post-processing for constraints may lead to sub-optimal results, where the errors in these two stages can not be considered together and tuned to- gether. Instead, we will introduce Post-Processing Network which can be trained end-to-end together with Un to enforce the constraints.
1xlx1
symmetiiation
Convolution
2D Convolution
0)
painwise concet
LxLx6d
scores
concat Lx3d
cousnnbog
1.22d
Transformr Encoder
Position Embedding
Transfomer Encoder
Lxd
Transforer Encoder
MLP
concat 1.x2d
Lxd
Multiply by W R
feature map W
4.2 POST-PROCESSING NETWORK
1002
100
100
100
100
2018
3/L 4/L S/L
position LX2
The second part of E2Efold is a Post-Processing Net- work PP, which is an unrolled and parameterized al- gorithm for solving a constrained optimization prob- Figure 4: Architecture of Deep Score Network.
Input Lx4
lem. We first present how we formulate the post-processing step constrained optimization prob- lem and the algorithm for solving it. After that, we show how we use the algorithm as a template to design deep architecture pP..
4

---

Published as a conference paper at ICLR 2020
4.2.1 POST-PROCESSING WITH CONSTRAINED OPTIMIZATION
Formulation of constrained optimization. Given the scores predicted by Ua(æ), we define the total score Σx, (U)(()) s) as the objective to maximize, where is an offset term. Clearly, without structure constraints, the optimal solution is to take Ay 1 when Ug(z) > Intu- itively, the objective measures the covariation between the entries in the scoring matrix and the A matrix. With constraints, the exact maximization becomes intractable. To make it tractable, we consider convex relaxation of this discrete optimization to a continuous one by allowing Ag E [0, 1]. Consequently, the solution space that consider optimize {A E [0, 1| L A is symmetric and satisfies constraints (i)-(iii) in Section 3).
is A(x)
To further simplify the search space, we define a nonlinear transformation T on R as T(A) A ( A)
(z), where o denotes element-wise multiplication. Matrix M is defined as M( == 1 v, E B and also i - j| 2 4, and M (z) == otherwise. From this definition we see that (a:) encodes both constraint (i) and (ii). With transformation T, the resulting matrix nen-negative symmetric, and satisfies constraint and (ii). Hence, by defining A T(A), the solution space simplified as A(x) = {A (A) Á E L ,1,,,,111111 - 1}.
Finally, we introduce a & penalty term || == Eig | to make A sparse and formulate the post-processing step as: ((--) denotes matrix inner product, i.e. sum of entry-wise multiplication)
max AERLXL 2 s,
-ll s.t. A A
The advantages of this formulation are that the variables A.j are free variables in IR and there are only L inequality constraints A1 < This system of linear inequalities can be replaced by a set of nonlinear equalities relu(A1 (1l 1) = 0 so that the constrained problem can be easily transformed into unconstrained problem by introducing Lagrange multiplier À E R4:
min max [U)(()) - s, A) (A, relu(A1 1)) -pllAl11. A ÁERLXL
(2)
Algorithm for solving it. We use primal-dual method for solving Eq. 2 (derived in Appendix B). In each iteration, Á and X are updated alternatively by:
(primal) gradient step: A c - A M(x) (01/aA:+
(3)
[0f/AA, = (U=(x) -) (A sign(A,11 1))1 (iig((c when
where
(4)
and 0 otherwise,
(primal) soft threshold:
A <- relu(] At+1l - a 7.): A411 + +(A+t)),
(5)
(dual) gradient step: A <- A441 + 3 7/2 relu( 1-
(6)
where a, 8 are step sizes and Ya. 79 decaying coefficients. When it converges T, an approx- imate solution Round(Ar Un (a)), even if this step disconnected the training phase of Ua(w), the final prediction works much better than many other existing methods (as reported in Section 6). Next, we introduce how couple this post-processing step with the training of Ue(x) further improve the performance.
T(Ar)) is obtained. With this algorithm operated on the learned
4.2.2 POST-PROCESSING NETWORK VIA AN UNROLLED ALGORITHM
We design Post-Processing Nenwork, denoted by PP based the above algorithm. After it is defined, we can connect it with the deep score network U, and train them jointly in an end-to-end fashion, so that the training phase of Uø Uz( is aware of the post-processigg step.
5

---

Published as a conference paper at ICLR 2020
Algorithm 1: Post-Processing Network PP (U, M)
Algorithm 2: Neural Cell PPcello
Parameters @ (w, B, Non N3
Function PPcell& (U, M, X, A, A,t):
U < softsign(U - -)
G + U - (A softsign( A1 1))1 Å Å + 7aa Ao M (G G
Ao - softsign(U
sigmoid(U)
Ao - T(Ao): A f- w relu Ao 1)
À f- relu([A|
a 70')
For 1 = O,..., 1
1-1de do
Ā t - relu(1 A) [i.e..min(A A, 1)]
L A+11, A+11, A PU, M, XE, A Ac,t) return {A:)
A + T(); ; + A+ relu reluu(1-1 AA-1)
return X, A,
The specific computation graph of pP is given in Algorithm 1, whose main component is recurrent cell which we call PPcell The computation graph is almost the same as the iterative update from Eq. 3 to Eq. 6, except for several modifications:
(learnable hyperparameters) The hyperparameters including step sizes a, B, decaying rate Ya- Ts sparsity coefficient, p and the offset term are treated as learnable parameters in ø, so that there is no need to tune the hyperparameters by hand but automatically learn them from data instead. (fixd # Heertiooss Instead of running the iterative updates until convergence, PPcell, is applied recursively for iterations where T is a manually fixed number. This is why in Fig the output space of E2Efold is slightly larger than the true solution space.
(smoothed sign fugnctinn Resulted from the gradient of refu(-), the update step in Eq. 4 contains a sign(-) function. However, to push gradient through PP&, we require differentiable update step. Therefore, we use smoothed sign function defined as softsign(c) = 1/(1 + exp(-kc)), where is a temperature.
(clip Á) An additional step, Å + min(A, A. 1), is included to make the output At each itera- tion stay in the range [0. 1] 1 This is useful for computing the loss over intermediate results {At)T= for which we will explain more in Section
With these modifications, the Post-Processing Network PP is tuning- free and differentiable un- rolled algorithm with meaningful intermediate outputs. Combining it with the deep score network, the final deep model is
Process Network
E2Efold:
{A.)
pP
Un(w)
M(x))
Deep Score Nenwork
5 END-TO-END TRAINING ALGORITHM
Given a dataset D containing examples of input-output pairs (æx, A"), the training procedure of E2Efold is similar to standard gradient-based supervised learning. However, for RNA secondary structure prediction problems, commonly used metrics for evaluating predictive performances are F1 score, precision and recall, which are non-differentiable.
Differentiable F1 Loss. To directly optimize these metrics, mimic true positive (TP), false posi- tive (FP), true negative (TN) and false negative (FN) by defining continuous functions on [0, 1] 1,
TP A") FP = (A,1 A") FN = (1 - A, TN = (1 A, AA)).
Since F1 2TP/ + FP + FN), we define a loss function to mimic the negative of score as:
f- == - (2 A*) (A,1 A*) (1-A,A")) A,)*))
Assuming that Eig AG + 0, this loss is well-defined and differentiable on [o, 1] Precision and recall losses can be defined a similar way, but we optimize Fl score in this paper.
It is notable that this Fl loss takes advantages over other differentiable losses including lz and cross-entropy losses, because there are much more negative samples (i.e. Ai = 0) than positive samples (i.e. Ag 1). A hand-tune tuned weight is needed to balance them while using la cross- entropy losses, but F1 loss handles this issue automatically, which can be useful for a number of problems (Wang et al., 2016; Li et al., 2017).

---

Published as a conference paper at ICLR 2020
Overall Loss Function. As noted earlier, E2Efold outputs matrix A, E [0, 1| in each itera- tion. This allows us to add auxiliary losses to regularize the intermediate results, guiding it to learn parameters which can generate a smooth solution trajectory. More specifically, we use objective that depends on the entire trajectory of optimization:
T
min 0
Σ T
7 T-
(A,,
D
(x,A")ED
where {A,) = (x) M(x)) and 7 S discounting factor. Empirically, we find very useful to pre-train Up using logistic regression loss. Also, it is helpful to add this additional loss to Eq. 9 as a regularization.
EXPERIMENTS
We compare E2Efold with the SOTA and also the most commonly used methods in the RNA sec- ondary structure prediction field on two benchmark datasets. It is revealed from the experimental results that E2Efold achieves 29.7% improvement in terms of Fl score on RNAstralign dataset and it infers the RNA secondary structure fast as the most efficient algorithm (LincarFold) among isting ones. An ablation study is also conducted to show the necessity of pushing gradient through the post-procsssing step. The codes for reproducing the experimental results released."
Dataset. We use two benchmark datasets: (i) Archivell
Table 1: Dataset Statisties
(Sloma & Mathews, 2016), containing 3975 RNA struc- tures from 10 RNA types, is a widely used benchmark dataset for classical RNA folding methods. (ii) RNAS- tralign (Tan et al., 2017), composed of 149 structures from 8 RNA types, one of the most comprehensive col- lections of RNA structures in the market. After removing redundant sequences and structures, 30451 structures re- main. See Table 1 for statistics about these two datasets.
Archivell
RNAStralign
Type
length
#samples
length
#samples
28-29668
3975
30~1851
30451
16S+RNA
73~-1995
110
54--1851
11620
SSIRNA
102-135
1283
104-132
9385
IRNA
54--33
557
59--95
6443
gmpl
210-733
163--15
1502
SRP
28--533
928
30--553
468
ImRNA
102-x437
462
102--437
572
RNaseP
120~-486
454
189~.486
434
Experiments On RNAStralign. We divide RNAStralign dataset into training, testing and validation sets by strat- ified sampling (see details in Table 7 and Fig 6), so that
telomerase
382~5559
382~559
37
23StRNA
242--2968
35
grp2
619~7880
11
each set contains all RNA types. We compare the performance of E2Efold to six methods includ- ing CDPfold, LincarFold, Mfold, RNAstructure (ProbKnot), RNAfold and CONTRAfold. Both E2Efold and CDPfold are learned from the same training/validation sets. For other methods, directly use the provided packages or web-servers to generate predicted structures. We evaluate the Fl score, Precision and Recall for each sequence in the test set. Averaged values are reported in Table 2. As suggested by Mathews (2019), for a base pair (i,,j), the following predictions are also considered correct: (i (1 (i 1, (i,j + 1), (i,j- 1), we also reported the metries when
one-position shift is allowed.
Table 2: Results on RNAStralign test set. "(S)" indi-
10
cates the results when one-position shift is allowed.
0.8
Method
Pree
Rec
F1
Prec(S) Rec(S) FI(()
0.6
E2Efold
0,866
0.788
0.821
0.880
0.798 0.833
0.4
CDPiold
0.633
0.597 0.614
0.720
0.677 0.697
LincarFold
0.620 0.606 0.609
0.635
0.622 0.624
0.2
Mfold
0.450 0.398 0.420
0.463
0.409 0.433
RNAstructure
0.537 0.568 0.550
0.559
0.592 0.573
0.0
comes
wis
oiseroto Guaben
RNAfold
0.516 0.568 0.540
0.533
0.587 0.558
CONTRAfold 0.608 0.663 0.633
0.624
0.681 0.650
Figure 5: Distribution of score.
As shown in Table 2, traditional methods achieve Fl score ranging from 0.433 to 0.624, which is consistent with the performance reported with their original papers. The two learning- baased methods, CONTRAfold and CDPfold, can outperform classical methods with reasonable margin on
The codes for reproducing the experimental results are released at https//githh..cmmm/444eeee2

---

Published as a conference paper at ICLR 2020
some criteria. E2Efold, on the other hand, significantly outperforms all previous methods across all criteria, with at least 20% improvement. Notice that, for almost all the other methods, the recall is usually higher than precision, while for E2Efold, the precision is higher than recall. That can be the result of incorporating constraints during neural network training. Fig 5 shows the distributions of F1 scores for each method. It suggests that E2Efold has consistently good performance.
To estimate the performance of E2Efold on long sequences, we also compute the Fl scores weighted by the length of sequences, such that the results are more dominated by longer sequences. Detailed results are given in Appendix D.3.
Table 3: Performance comparison on ArchivelI
Table 4: Inference time on RNAStralign
Method
Prec
Rec
Prec(S) Rec(S)
FI(S)
Method
total run time time per seq
E2Efold
0.734
0.66 0.686
0.758
0.676
0.704
E2Efold (Pytorch)
19m (GPU)
0.40s
CDPfold
0.557
0,535 0,545
0.612
0,585
0.597
CDPfold (Pytorch)
440m*32 threads
300.107s
LinearFold
0.641
0.617 0.621
0.668
0.644
0.647
LinearFold
(C)
20m
0.43s
Mfold
0.428
0.383 0.401
0.450
0,403
0.421
Mfold
(C)
360m
7.65s
RNAstructure
0.563
0.615 0,585
0.590
0.645
0.613
RNAstructure (C)
3 days
142.02s
RNAfold
0.565 0.627 0,592
0.586
0.652
0.615
RNAfold
(C)
26m
0.55s
CONTRAfold 0.607 0.679 0.638 0.629
0.705
0.662
CONTRAfold (C) 1 day
30,58s
Test On Archivell Without Re-training. To mimic the real world scenario where the users want to predict newly discovered RNA's structures which may have a distribution different from the training dataset, we directly test the model learned from RNAStralign training set on the Archivell dataset, without re-training the model. To make the comparison fair, we exclude sequences that are over- lapped with the RNAStralign dataset. We then test the model on sequences in Archivell that have overlapping RNA types (5SRRAA, 16StRNA, etc) with the RNAStralign dataset. Results shown in Table 3. It understandable that the performances of classical methods which are not learning- based are consistent with that on RNAStralign. The performance of E2Efold, though is not as good as that on RNAStralign, is still better than all the other methods across different evaluation crite- ria. In addition, since the original Archivell dataset contains domain sequences (subsequences), remove the domains and report the results in Appendix D.4, which are similar to results in Table 3.
Inference Time Comparison. We record the running time of all algorithms for predicting RNA secondary structures on the RNAStralign test set, which is summarized in Table 4. LinearFold is the most efficient among baselines because it uses beam pruning heuristic accelerate DP. CDPfold, which achieves higher Fl score than other baselines, however, is extremely slow due to its DP post-processing step. Since we use gradient- based algorithm which simple to design the Post- Processing Network, E2Efold is fast. On GPU, E2Efold has similar inference time as LinearFold.
Pseudoknot Prediction. Even though E2Efold does not exclude pseudoknots, it is not sure whether it ac-
Table 5: Evaluation of pscudoknot prediction
tually generates pseudoknotted structures. Therefore, we pick all sequences containing pseudoknots and com- pute the averaged Fl score only on this set. Besides, we count the number of pseudoknotted sequences that predicted as pseudoknotted and report this count as true positive (TP). Similarly we report TN, FP and FN in Table 5 along with the F1 score. Most tools exclude pseudoknots while RNAstructure is the most famous one that can predict pseudoknots, so we choose it for comparison.
Method
Set Fl
TP
FP
TN
FN
E2Efold 0.710 1312 242 1271
RNAstructure 0.472
1248 307
983 286
true structure
E2Efold
RNAstructure
CONTRAfold
true structure
E2Efold
RNAstructure
CONTRAfold
Visualization. We visualize predicted structures of three RNA sequences in the main text. More examples are provided in appendix (Fig to 14). these figures, purple lines indicate edges of pseudoknotted elements. Although CDPfold has higher Fl score than other base- lines, its predictions truth. Instead, RNAstructure and CONTRAfold produce comparatively more reasonable visualizations among all baselines, so we compare with them. These
visually far from the ground-
true structure
E2Etold
8

---

Published as a conference paper at ICLR 2020
two methods capture rough sketch of the structure, but not good enough. For most E2Efold produces structures most similar to the ground truths. Moreover, works surprisingly well for some RNA sequences that long and very difficult to predict.
Ablation Study. To exam whether integrating the two stages by pushing gradient through the post- process is necessary for performance of E2Efold, we conduct an ablation study (Table 6). We test the per- formance when the post-processing step is discon- nected with the training of Deep Score Network Ug. We apply the post-processing step (i.e., for solving augmented Lagrangian) after Up is learned (thus the notation "Ua + PP" in Table 6). Al- though "Un + PP" performs decently well, with constraints incorporated into training, E2Efold still has significant advantages over it.
Table 6: Ablation study (RNAStralign test set)
Method Prec E2Efold 0.866 0.788 0.821 0.880
Rec
F1
Prec(S) Rec(S) F1(S)
0.798 0.833
Us+PP 0.755 0.712 0.721 0.782 0.737 0.752
Discussion. better estimate the performance of E2Efold on different RNA types, we include the per-family FI scores in Appendix D.5. E2Efold performs significantly better than other methods in 16S rRNA, IRNA, 5S RNA, tmRNA, and telomerase. These results are from a single model. In the future, we can view it multi-task learning and further improve the performance by learning multiple models for different RNA families and learning an additional classifier to predict which model for the input sequence.
7 CONCLUSION
We propose novel DL model, E2Efold, for RNA secondary structure prediction, which incorpo- rates hard constraints in its architecture design. Comprehensive experiments conducted to show the superior performance of E2Efold, no matter on quantitative criteria, running time, or visualiza- tion. Further studies need to be conducted to deal with the RNA types with less samples. Finally, believe the idea of unrolling constrained programming and pushing gradient through post-processing can be generic and useful for other constrained structured prediction problems.
ACKNOWLEDGEMENT
We would like to thank anonymous reviewers for providing constructive feedbacks. This work is supported in part by NSF grants CDS&E-1100011 D3SC,
FMitF, IIS-1841351, CA- REER IIS-1350983 to L.S. and grants from King Abdullah University of Science and Technology, under award numbers BAS/1/1624-01,, FCC/1/1976-18-01, FCC///1976-2--01, FCC/1/1976-25-01, FCC/1/1976-26-00 REI/1/0018-01-11 and URF/1/4098-01-01.
REFERENCES
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning-Ver Volume 70, pp. 136- 145. JMLR. org, 2017.
Mirela S Andronescu, Cristina Pop, and Anne E Condon. Improved free energy parameters for RNA pseudoknotted secondary structure prediction. RNA, 16(1):26-42, 2010.
David Belanger, Bishan Yang, and Andrew McCallum. End-to-end learning for structured prediction energy networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 429-439. JMLR. org, 2017.
Stanislav Bellaousov and David Mathews. Probknot: fast prediction of RNA secondary structure including pseudoknots. RNA, 16(10):1870-1880 2010.
Stanislav Bellaousov, Jessica S Reuter, Matthew G Sectin, and David H Mathews. RNAstructure: web servers for RNA secondary structure prediction and analysis. Nucleic acids research, 41 (W1):W41--4474, 2013.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of un- folded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.

---

Published as a conference paper at ICLR 2020
Francis Crick. Central dogma of molecular biology. Nature, 227(5258))561, 1970.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
Chuong B Do, Daniel A Woods, and Serafim Batzoglou. Contrafold: RNA secondary structure
prediction without physics-based models. Bioinformatics, 22(14))e0--998 2006.
Timothy Dozat and Christopher D Manning. Deep biaffine attention for neural dependency parsing. arXiv preprini urXiv:/611.01735 2016.
P Fechter, J Rudinger-Thirion, C Florentz, and R Giege. Novel features in the tRNA-like world of plant viral RNAs. Cellular and Molecular Life Sciences CMLS, 58 58(11):557-1151, 2001.
Christine E Hajdin, Stanislav Bellaousov, Wayne Huggins, Christopher W Leonard, David H Math- ews, and Kevin Weeks. Accurate shape-directed RNA secondary structure modeling, including pseudoknots. Proceedings of the National Academy of Sciences,
2013.
John Hershey, Jonathan Roux, and Felix Weninger. Deep unfolding: Model-based inspiration of novel deep architectures. arXiv preprint
2014.
Liang Huang, He Zhang, Dezhong Deng, Kai Zhao, Kaibo Liu, David Hendrix, and David H Mathews. Linearfold: linear-time approximate RNA folding by 5' 5'-to-3' 3dy-mmic programming and beam search. Bioinformatics, 35(14):1255-1304 2019.
John Ingraham, Adam Riesselman, Chris Sander, and Debora Marks. Learning protein structure with a differentiable simulator. 2018.
Elizabeth Iorns, Christopher Lord, Nicholas Turner, and Alan Ashworth. Utilizing RNA interfer- ence to enhance cancer drug discovery. Nature reviews Drug discovery. 6(7):556, 2007.
Eliyahu Kiperwasser and Yoav Goldberg. Simple and accurate dependency parsing using bidirec- tional Istm feature representations. Transactions of the Association for Computational Linguistics, 4:313-327, 2016.
Yu Li, Sheng Wang, Ramzan Umarov, Bingqing Xie, Ming Fan, Lihua Li, and Xin Gao. Deepre: sequence-based enzyme ec number prediction by deep learning. Bioinformatics, 34(5)7660-769, 2017.
Ronny Lorenz, Stephan H Bernhart, Christian Höner Zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker. ViennaRNA package 2.0. Algorithms for molecular biology, 6(1):26, 2011.
Rune B Lyngsø and Christian NS Pedersen. RNA pseudoknot prediction in energy-based models. Journal of computational biology, 7(3-4):409-427, 2000.
NR Markham and M Zuker. Unafold: software for nucleic acid folding and hybridization in: Keith jm, ced) bioinformatics methods in molecular biology, vol. 453, 2008
David Mathews. Predicting RNA secondary structure by free energy minimization. Theoretical Chemistry Accounts, 116(1-3):160-16)) 2006.
David Mathews. How to benchmark RNA secondary structure prediction accuracy. Methods, 2019.
David Mathews and Douglas H Turner. Prediction of RNA secondary structure by free energy minimization. Current opinion in structural biology, 16(3):270-278, 2006.
Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. Non-projective dependency pars- ing using spanning tree algorithms. In Proceedings of the conference on Human Language Tech- nology and Empirical Methods in Natural Language Processing, pp. 523-530. Association for Computational Linguistics, 2005.
10

---

Published as a conference paper at ICLR 2020
Venkata Krishna Pillutla, Vincent Roulet, Sham M Kakade, and Zaid Harchaoui. A smoother way to train structured prediction models. Advances in Neural Information Processing Systems, pp- 4766-4778, 2018.
Harsh Shrivastava, Xinshi Chen, Binghong Chen, Guanghui Lan, Srinvas Aluru, and Le Song. Glad: Learning sparse graph recovery. arXiv preprint (rxivv:906.002777 2019.
Michael F Sloma and David H Mathews. Exact calculation of loop formation probability identifies folding motifs in RNA secondary structures. RNA, 22(12):1808-18 18188 2016.
David Staple and Samuel Butcher. Pseudoknots: RNA structures with diverse functions. PLoS biology, 3(6):e213, 2005.
Evan W Steeg. Neural networks, adaptive optimization, and RNA secondary structure prediction. Artificial intelligence and molecular biology, pp. 121-160, 1993.
Zhen Tan, Yinghan Fu, Gaurav Sharma, and David H Mathews. Turbofold i:: RNA structural alignment and secondary structure prediction informed by multiple homologs. Nucleic acids research, 15(20):11570-1) 15881 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, pp. 5998 5998-6008. 2017.
Sheng Wang, Siqi Sun, and Jinbo Xu. Auc-maximized deep convolutional neural fields for protein sequence labeling. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 1-16. Springer, 2016.
Sheng Wang. Siqi Sun, Zhen Li, Renyu Zhang, and Jinbo Xu. Accurate de novo prediction of protein contact map by ultra-deep learning model. PLoS computational biology, 13()):e1005324 2017.
Shay Zakov, Yoav Goldherg, Michael Elhadad, and Michal Ziv-Ukelson. Rich parameterization improves RNA structure prediction. Journal of Computational Biology, 18(11):1525-1542 2011.
Hao Zhang, Chunhe Zhang, Zhi Li, Cong Li. Xu Wei, Borui Zhang, and Yuanning Liu. A new method of RNA secondary structure prediction based on convolutional neural network and dy- namic programming. Frontiers in genetics, 10, 2019.

---

Published as a conference paper at ICLR 2020
A MORE DISCUSSION ON RELATED WORKS
Here we explain the difference between our approach and other works on unrolling optimization problems.
First, our view of incorporating constraints to reduce output space and to reduce sample complexity novel. Previous works (Hershey al., 2014; Belanger et al., 2017: Ingraham al., 2018) did not discuss these aspects. The most related work which also integrates constraints is OptNet (Amos & Kolter, 2017), but its very expensive and can not scale to the RNA problem. Therefore, our proposed approach is a simple and effective one.
Second, compared (Chen et al., 2018; Shrivastava et al., 2019), our approach has different purpose of using the algorithm. Their goal is to learn a better algorithm, so they commonly make their architecture more flexible than the original algorithm for the room of improvement. However, we aim at enforcing constraints. To ensure that constraints are nicely incorporated, we keep the original structure of the algorithm and only make the hyperparameters learnable.
Finally, although all works consider end-to-end training, none of them can directly optimize the F1 score. We proposed differentiable loss function to mimic the F1 score/precision/recall, which effective and also very useful when negative samples are much fewer than positive samples (or the inverse).
B DERIVATION OF THE PROXIMAL GRADIENT STEP
The maximization step in Eq. 1 can be written as the following minimization:
min
(Uo(.) 8, A) + (A, relu(A1 A1 - 1)) + A/2
(10)
ÁEREXI
-S(A)
Consider the quadratic approximation of -A() centered Ag:
- -a((A) = - f(Ar) + (- 0ʃ
Ad) + 2a
|| - Ael
(11)
0A,
1
Á, + 0f
=- =-S(Ai) + _
(12)
2x
0A,
and rewrite the optimization in Eq. 10 as
1
min ÂEREXL
- f((a) +
À A
+ -11
(13)
2a
1 A A
min AERLxU
+ 1||
(14)
2x
where
as
Å A.
(15)
a..
Next, we define proximal mapping as a function depending on as follows:
prox (Ae+1) mig Å - A +llAA|l
(16)
ÁERiXE
2a
Å Ac+1 | apll
arg min _
(17)
ÁERAXI
sign(A.-1) maxpmaaaaammm A ap, 0)
(18)
sign(A)-))reu((A(:)) - ap).
(19)
Since we always use o Á instead of Á in our problem, we can take the absolute value
[prora(A++1) Ae41l axp) without loss of generality. Therefore, the proximal gradient
12

---

Published as a conference paper at ICLR 2020
step is
0s 0A,
A++1 - A. + a (correspond to Eq. 3)
(20)
A+t1 relu(1AA+ - ap) (correspond to Eq. 5).
(21)
More specifically, in the main text, we write 0f 8A,
as
05
05
05
0A OA.
+
(22)
0A,
0A,
OA,
1 0AA
0f
0f
(23)
2 0A.
0A,
0A,
2 0 M (2Á, + -247))
1
0f
0f
+
(24)
0A,
A4,
0f
0f
o M (2Á, - -2A,)
(25)
22
OA,
0A.
05
os
= M A.
+
(26)
0A
dA.
The last equation holds since Ag will remain symmetric in our algorithm if the initial Åg is symmet- ric. Moreover, in the main text, is replaced by a %
C IMPLEMENTATION AND TRAINING DETAILS
We used Pytorch implement the whole package of E2Efold.
Deep Score Network. In the deep score network, we used a hyper-parameter, d, which was set as 10 in the final model, control the model capacity. In the transformer encoder layers, we the number of heads as 2, the dimension of the feed-forward network as 2048, the dropout rate as 0.1. As for the position encoding, we used 58 base functions to form the position feature map, which goes through a 3-layer fully-connected neural network (the number of hidden neurons is 5 * d) to generate the final position embedding, whose dimension is by d. the final output layer, the pairwise concatenation is carried out in the following way: Let X E LRdddd be the input to the final output layers in Figure (which is the concatenation of the sequence embedding and position embedding). The pairwise concatenation results in a tensor Y E IR 2xx6x defined as
Yi.ji:)) = (( ()):))
(27)
where (iijj.)) Rdd, Xii.)) E 3d and ((.:) e 3d
In the 2D convolution layers, the the channel of the feature map gradually change from 6*d to d and finally 1. We set the kernel size
translate the feature map into the final score matrix. Each 2D convolution layer is followed by batch normalization layer. We used ReLU as the activation function within the whole score network.
Post- Post-Processing Network. In the PP network, we initialized ws as 1, as log(9), a as 0.01, 3 0.1, Ya as 0.99, 7/9 as 0.99, and / as 1. We set T as 20.
Training details. During training, we first pre-trained deep score network and then fine-tuned the score network and the PP network together. To pre-train the score network, we used binary cross- entropy loss and Adam optimizer. Since, in the contact map, most entries are 0, we used weighted loss and set the positive sample weight as 300. The batch size was set to fully use the GPU memory, which was 20 for the Titan Xp card. We pre-train the score network for 100 epochs. As for the fine-tuning, we used binary cross-entropy loss for the score network and Fl loss for the PP network and summed up these two losses as the final loss. The user can also choose only the F1 loss
13

---

Published as a conference paper at ICLR 2020
another coefficient to weight the loss estimated the score network Ug. Due to the limitation of the GPU memory, we set the batch size as 8. However, we updated the model's 's parameters every 30 steps to stabilize the training process. We fine-tuned the whole model for 20 epochs. Also, since the data for different RNA families are imbalanced, we up-sampled the data in the small RNA families based their size. For the training of the score network Ug in the ablation study, it is exactly the same as the training of the above mentioned process. Except that during the fine-tune process, there the unrolled number of iterations
to be 0.
D MORE EXPERIMENTAL DETAILS
D.1 DATASET STATISTICS
8000
6000
Count
4000
250
500
750
1000
1250
1500
1750
Sequence length
Figure The RNAStralign length distribution.
Table 7: RNAStralign dataset splits statistics
RNA type
All
Training
Validation
Testing
16SIRNA
11620
9325
1145
1150
5SIRNA
9385
7687
819
879
tRNA
6443
5412
527
504
grpl
1502
1243
123
136
SRP
468
379
36
53
tmRNA
572
461
50
61
RNascP
434
360
37
37
telomerase
37
28
4
5
RNAStralign
30451
24895
2702
2854
D.2 TWO-SAMPLE HYPOTHESIS TESTING
To better understand the data distribution different datasets, we provide statistical hypothesis test results in this section.
We can assume that
(i) Samples in RNAStralign training set are i.i.d. from the distribution P(RNAStriaan):
(ii) Samples in RNAStralign testing set i.i.d. from the distribution P(RNAStriew):
iiii Samples in ArchivelI dataset are i.i.d. from the distribution P(AreII).
To compare the differences among these data distributions, we can test the following hypothesis:
(a) P(RNAStrmain) P(RNASStrea)
(b) P(RNAStrrmin) P
14

---

Published as a conference paper at ICLR 2020
The approach that adopted is the permutation test the unbiased empirical Maximum Mean Discrepancy (MMD) estimator:
N
N
M M
N
M
2 mn
MMD,(X,Y)
+
kyh Vj)
k( M3
(28)
j=1
where X
{ contains N i.idd. samples from a distribution Pi, {vs ) contains ii.d. samples from distribution P2, and k(:,)) is string kernel.
Since we conduct stratified sampling to split the training and testing dataset, when we perform permutation we use stratified re-sampling well (for both Hypothese (a) and (b)). The result of the permutation test (permuted 1000 times) reported in Figure 7.
250
200
150
100
30
50
0.0018
0.0020
0,0022
0,0024
0.0026
0,0028
0,022
0.024
0.026
0.028
0.030
Figure 7: Left: Distribution MMD,, under Hypothesis P(RNAStruaan P(RNAStrea)) Right: Distribution of MMD,, under Hypothesis P(RNAStrmain) = P(Archivell)..
The result shows
(a) Hypothesis P(RNAStrraim) = P(RNASSriea) can be accepted with significance level 0.1.
(b) Hypothesis p(RNAStrmmin = P (Archiieell) is rejected since the p-value is 0.
Therefore, the data distribution in Archivell is very different from the RNAStralign training set. A good performance on Archivell shows significant generalization power of E2Efold.
D.3 PERFORMANCE ON LONG SEQUENCES: WEIGHTED FI SCORE
For long sequences, E2Efold still performs better than other methods. We compute F1 scores weighted by the length of sequences (Table 8), such that the results sequences.
dominated by longer
Table 8: RNASStalign: Fl after a weighted average by sequence length.
Method
E2Efold
CDPfold
LinearFold
Mffodd
RNAstructure
RNAfold
CONTRAfold
non-weighted
0.821
0.614
0.609
0.420
0.550
0.540
0.633
weighted
0.720
0.691
0.509
0.366
0.471
0.444
0.542
change
-12.3%
+12.5%
-16.4%
-12.8%
-1.3%
-17.7%
-14.3%
The third row reports how much F1 score drops after reweighting.
D.4 ARCHIVELI RESULTS AFTER DOMAIN SEQUENCES ARE REMOVED
Since domain sequence (subsequences) in Archivell explicitly labeled, filter them out in Archivell and recompute the Fl scores (Table 9).
The results do change much before after filtering subsequences.
15

---

Published as a conference paper at ICLR 2020
Table Archivell: Fl after subsequences are filtered out.
Method
E2Efold
CDPfold
LinearFold
Mfold
RNAstructure
RNAfold
CONTRAfold
original
0.704
0.597 0.605
0.647 0.645
0.421 0.419
0.613 0.611
0.615
0.662
filtered
0.723
0.615
0.659
D.5 PER-FAMILY PERFORMANCES
To balance the performance among different families, during the training phase we conducted weighted sampling of the data based on their family size. With weighted sampling, the overall Fl score (S) 0.83, which is the same as when we did eqigl-weighted sampling. The per-family results are shown in Table 10.
Table 10: RNAStralign: per-family performances
16S IRNA
IRNA
5S RNA
SRP
F1
F1(S)
F1
FI(S)
F1
F1(S)
F1
F1(S)
E2Efold
0.783
0.795
0.917
0.939
0.906
0.936
0.550
0.614
LinearFold
0.493
0,504
0.734
0.739
0.713
0.738
0.618
0.648
Mfold
0.362
0.373
0.662
0.675
0.356
0.367
0.350
0.378
RNAstructure
0.464
0.485
0.709
0.736
0.578
0.597
0.579
0.617
RNAfold
0.430
0.449
0.695
0.706
0.592
0.612
0.617
0.651
CONTRAfold
0.529
0.546
0.758
0.765
0.717
0.740
0.563
0.596
tmRNA
Group
intron FI(S)
RNaseP
telomerase
F1
FI(S)
F1
F1
FI(S)
F1
FI
E2Efold
0.588
0.653
0.387
0.428
0.565
0.604
0.954
0.961
LinearFold
0.393
0.412
0.565
0.579
0.567
0.578
0.515
0.531
Mfold
0.290
0.308
0.483
0.498
0.562
0.579
0.403
0.531
RNAstructure
0,400
0.423
0,566
0.599
0.589
0.616
0.512
0.545
RNAfold
0.411
0.430
0.589
0.599
0.544
0.563
0.471
0.496
CONTRAfold
0.463
0.482
0.603
0.620
0.645
0.662
0.529
0.548
16

---

Published as a conference paper at ICLR 2020
D.6 MORE VISUALIZATION RESULTS
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Figure Visualization of 5S rRNA, B01865.
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Figure 9: Visualization of 16S IRNA, DQ170870.
17

---

Published as a conference paper at ICLR 2020
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Figure 10: Visualization of Group intron, IC3, Kaf.c.tmL
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Chr
Cat
Figure 11: Visualization of RNaseP, A.sainnssris--18 184.
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Camm
Figure 12: Visualization of SRP, Homo.sapi. BU56690.
18

---

Published as a conference paper at ICLR 2020
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Can Cuc
Figure 13: Visualization of tmRNA, uneu.bact. AF389956.
true structure
E2Efold
RNAstructure
CDPfold
CONTRAfold
LinearFold
Mfold
RNAfold
Figure 14: Visualization of tRNA, tabD00012019.
19


Reviews:
[{"review_id": "SJlmuE8k5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed an end-to-end method (E2Efold) to predict RNA secondary structure. The method consists of a Deep Score Network and a Post-Process Network (PPN). The two networks are trained jointly. The score network is a deep learning model with transformer and convolution layers, and the post-process network is solving a constrained optimization problem with an T-step unrolled algorithm. Experimental results demonstrate that the proposed approach outperforms other RNA secondary structure estimation approaches.\n\nOverall I found the paper interesting. Although the writing can be improved and some important details are missing.\n\nMajor comments\nAs the authors point out, several existing approaches for unrolling optimization problems have been proposed. It would be helpful to clarify the methodological novelty of the proposed algorithm compared to those.\n\n\nTraining details and implementation details are missing; these hinder the reproducibility of the proposed approach. The author stated pre-training of the score network, how is the PPN and score network updated during the joint training? Does the model always converge? The authors vaguely mentioned add additional logistic regression loss to Eq9 for regularization. What is a typical number of T? How does varying T affect the performance, both in terms of training time (and convergence) and in terms of accuracy/F1?\n\nMinor comments\nThe 29.7% improvement of F1 score overstates the improvements compared to non-learning approaches.. This performance was computed on the dataset (RNAStralign) on which E2Efold was trained. A fair comparison, as the authors also stated, is on the independent ArchiveII data. On this data, E2Efold has F1 score 0.686 versus 0.638 for CONTRAfold. The author should report performance improvement under this line.\n\n\nIt would be helpful to report performance per RNA category, both for RNAstralign data and ArchiveII data, while the ArchiveII data should still remain independent. Different models may have their strengths and weaknesses on different RNA types.\n\n\nIt is not obvious to me how the proximal gradient was derived to (3)-(5). It would be helpful if the authors show some details in the supplements.\n\n\nWhy is there a need to introduce an l_1 penalty term to make A sparse?\n\n\nOn which data is Table 6?\n\nTypos, etc.\nThe references are not consistently formatted\n“structure a result” -> “structure is a result”\n“a few hundred.” -> “a few hundred base pairs.”\n“objective measure the” -> “objective measures the”\n“section 5” -> “Section 5” (in several places)\nIn the equation above Equation 2, should it be -\\rho||\\hat{A}||_{1} instead of plus? Otherwise, the “max” could be made arbitrarily large.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1xh9zkV9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces an end-to-end method to predict the secondary structure of RNA, by mapping the nucleotide sequence to a binary affinity matrix. The authors decompose this problem into two part: (i) predicting an affinity score between each base pair in the input sequence, using a combination of a transformer sequence encoder network and a convolutional decoder, and (ii) a post-processing step that ensures that structural local and global constraints are enforced. An innovation is to express this post-processing as an unrolled sequence of proximal gradient descent steps, which are fully differentiable, and allow the full combination of (i)+(ii) to be trained end-to-end. A thorough set of experiments validate the approach.\n\nOverall, the paper is well written and easy to follow. The approach of unrolling structural constraints as shown in the paper is interesting and applicable to much wider domains than secondary structure prediction. The proposed approach appears to provide a novel, convincing and non-obvious solution to RNA secondary structure prediction, and subject to suggestions below, would represent a valuable contribution to ICLR.\n\nThe principal area for improvement would be to include additional detail (perhaps in appendix) on the model hyperparameter configurations that were used in the experiments. Moreover, more details on the set of \\psi functions, and the MLP details for P_i (e.g. number of hidden units, activation function, the use of dropout, batch normalization, etc) should be given, as well as more information on the specifics how how the “pairwise concatenation” is carried out in the output layer. What unrolling constant T is used? Finally, in the ablation study (p. 8) details on how U_\\theta is trained by itself (without the post-processing step) should be given. \n\nDetailed comments:\n* Overall, the whole paper should be thoroughly reviewed for English grammar and writing style; a subset of suggested changes follow.\n* p. 1: structure a result ==> structure is a result\n* p. 2: energy based methods ==> energy-based methods\n* p. 2: energy function based approaches ==> energy function-based approaches\n* p. 2: view point ==> viewpoint\n* p. 2: E2Efold is flexible ==> E2Efold are flexible\n* p. 2: nearly efficient ==> nearly efficiently\n* p. 3: typically scale ==> typically scale as\n* p. 3: few hundred. ==> few hundreds.\n* p. 4: all binary matrix ==> all binary matrices\n* p. 4: output space can help ==> output space could help\n* p. 5: formulation are the ==> formulation are that the\n* p. 6: eq. (7) should contain quantities indexed by $t$ in the RHS\n* p. 8: pesudoknotted ==> pseudoknotted\n* p. 9 ff: in the bibliography, all lowercase rna should be uppercase RNA. Use {RNA} in bibtex entries.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Bklpej_AKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\nThe authors perform RNA secondary prediction using deep learning. The outputs are subject to hard constraints on which nucleotides can be in contact with others. They unroll a sophisticated optimization algorithm for a relaxation of the task of finding the optimal contact map subject to these constraints. This work is in a long line of work demonstrating that end-to-end training of models that incorporate application-specific optimization routines as sub-modules is very useful. In particular, it outperforms an approach where the inputs to this optimization problem come from a network that was trained using a simple loss that ignores the fact that it will feed into this structured optimizer. The paper also considers an application domain that will be unfamiliar to many ICLR readers interested in deep structured prediction, and may serve as a call to arms for the community engaging with additional problems in this field.   \n\n*Overall Assessment*\nThe paper is well written, well executed, and part of a general research thread that ICLR readers care about. There are a number of technical details, such as the loss function in (8) that will be of general interest. I advocate for acceptance.\n\n*Comments*\nThe actual specification of the output constraints doesn't occur until late in the paper. Before then, the discussion of them is very abstract. Given that the constraints are easy to describe, the exposition would be improved notably if you described the specific constraints earlier on. This would help me understand the problem domain better.\n\nFyi, the idea of nested structures vs. non-nested structures appears in NLP in terms of projective parsing vs. non-projective parsing. There may be some relevant reading for you to do there. Your specific work (minus the unrolled constraint enforcement) is similar to \"Dozat et al. 2017. Deep biaffine attention for neural dependency parsing.\"\n\nThe idea of backpropping through some constraint-enforcing process is reminiscent of backpropping through belief propagation. See, for example, Domke's \"Learning Graphical Model Parameters with Approximate Marginals Inference.\" Or Hershey et al. \"Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures.\" You should also cite work using unrolled ISTA to learn sparse coding dictionaries. They have terms similar to (5). \n\nWhat exactly was your motivation for the setup in \"Test On ArchiveII Without Re-training?\"\n\nHow sensitive is performance to the number of optimizer iterations? Does it work to train with a fixed number of unrolled iters, but at test time run the optimizer until convergence?\n\n(8) is cool!\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "B1g-0PdH3r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "RNA Secondary Structure Prediction by Learning Unrolled Algorithms\n\nThis paper proposes E2Efold, which is an RNA secondary structure prediction algorithm based on an unrolled algorithm. Previous methods rely on dynamic programming (which does not work for molecular configurations that do not factorize) or rely on energy-based models (which require a minimization step, e.g. by using MCMC to traverse the energy landscape and find minima). The former does not work for all molecules and the latter can be difficult to optimize. The method presented here is novel, shows strong SOTA performance, and would be of interest to the wider deep learning community.\n\nThe method is based on an unrolled algorithm, which is motivated by the inclusion of three inductive biases / constraints important underlying RNA folding. These constraints limit the wide RNA search space. The first component of the method is a “Deep Score Network” which uses a stack of Transformer encoders (with relative and exact positional embeddings) followed by 2D convolutional layers to output a L x L symmetric matrix describing the “scores” of base pairing. As these scores may not obey the rules of RNA folding, a second post-processing network is trained end-to-end together with the “Deep Score Network” to enforce constraints. This network starts with a transformation that symmetrizes the matrix and applies a constraint-enforcing mask. The problem is transformed into an unconstrained problem by using Lagrange multipliers; it is then solved using a proximal gradient. Finally, a recurrent cell is defined that implements this algorithm in a deep learning framework. This method is creative, could be applied to other tasks with constraints, and would be interesting to the wider deep learning community.\n\nIn addition to developing the deep score network and post-processing network, the authors also develop a differentiable F1 loss, so that the network can directly optimize for precision and recall on the task. The performance of this method significantly outperforms previous methods. There was a fruitful discussion on OpenReview regarding whether this was a result of overfitting on the task. Indeed, it is critical in deep learning applications to carefully construct train/test sets to avoid high performance by memorization alone. To address this, the authors train on RNAStralign and test on ArchiveII. As the original ArchiveII dataset contains subsequences of other RNA sequences, which can result in overfitting, the authors re-ran their experiment with that removed, and similar results were achieved. To support the hypothesis that ArchiveII and RNAStralign capture different distributions, they perform a permutation test on the unbiased empirical Maximum Mean Discrepancy estimator, finding that the distributions are different. I do wonder why they did not check if P(ArchiveII) = P(ArchiveII) as they do check if P(RNAStr_train) = P(RNAStr_train). On the specific task of pseudoknot prediction, the method also performs well (F1 is >0.23 over the baseline). On sequence length-weighted F1, the model does even better.\n\nThe paper is rich with ablations. The analysis of the number of unrolling iterations T helps support the use of an unrolled method and builds intuition for its importance - it would be useful to include this in the appendix of the paper. I also appreciated the visualizations, which are a good sanity check that the model correctly handles pseudoknots. The performance of the method is broken down by RNA family, which is also quite interesting -- the method outperforms LinearFold on all classes, besides 5S RNA, SRP, and Group I intron. Further analysis is required to better understand why the method is weaker on those datasets. Additionally, further work should explore training on one set of families and testing on a held-out set of families. This was pointed out by public comments on this paper. This is potentially a limitation of E2EFold (the authors do not seem to have tried this suggested experiment) and further exploration is required. Exploring this limitation (even if it is not overcome) would make this paper even more rich.\n\nThat said, I recommend acceptance of this paper due to the extensive experiments, polished writing, novel method, and strong results, which can inspire future research. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a RNA structure prediction algorithm based on an unrolled inference algorithm. The proposed approach overcomes limitations of previous methods, such as dynamic programming (which does not work for molecular configurations that do not factorize), or energy-based models (which require a minimization step, e.g. by using MCMC to traverse the energy landscape and find minima).

Reviewers agreed that the method presented here is novel on this application domain, has excellent empirical evaluation setup with strong numerical results, and has the potential to be of interest to the wider deep learning community. The AC shares these views and recommends an enthusiastic acceptance. 
Decision: Accept (Talk)