DEPfold: RNA Secondary Structure Prediction as Dependency Parsing.
Authors: KE WANG
Shay B Cohen
Venue: ICLR 2025 Poster (2025)
Keywords: RNA secondary structure prediction
Dependency parsing
Biaffine attention
Pseudoknots
Pretrained Model
Deep learning
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
TL;DR: DEPfold reframes RNA secondary structure prediction as dependency parsing. Using structure transformation, Biaffine parser, and optimal decoding, it outperforms existing methods, especially for pseudoknots and long-range interactions.

Abstract: RNA secondary structure prediction is critical for understanding RNA function
but remains challenging due to complex structural elements like pseudoknots and
limited training data. We introduce DEPfold, a novel deep learning approach that
re-frames RNA secondary structure prediction as a dependency parsing problem.
DEPfold presents three key innovations: (1) a biologically motivated transformation of RNA structures into labeled dependency trees, (2) a biaffine attention
mechanism for joint prediction of base pairings and their types, and (3) an optimal
tree decoding algorithm that enforces valid RNA structural constraints. Unlike traditional energy-based methods, DEPfold learns directly from annotated data and
leverages pretrained language models to predict RNA structure. We evaluate DEPfold on both within-family and cross-family RNA datasets, demonstrating significant performance improvements over existing methods. DEPfold shows strong
performance in cross-family generalization when trained on data augmented by
traditional energy-based models, outperforming existing methods on the bpRNAnew dataset. This demonstrates DEPfold’s ability to effectively learn structural
information beyond what traditional methods capture. Our approach bridges natural language processing (NLP) with RNA biology, providing a computationally
efficient and adaptable tool for advancing RNA structure prediction and analysis

Published as a conference paper at ICLR 2025
DEPFOLD: RNA SECONDARY STRUCTURE PREDICTION AS DEPENDENCY PARSING
Ke Wang Shay B. Cohen School of Informatics, The University of Edinburgh (k. wang-72, scohen) @ed ac.uk
ABSTRACT
RNA secondary structure prediction is critical for understanding RNA function but remains challenging due to complex structural elements like pseudoknots and limited training data. We introduce DEPfold, novel deep learning approach that re-frames RNA secondary structure prediction as a dependency parsing problem. DEPfold presents three key innovations: (1) a biologically motivated transfor- mation of RNA structures into labeled dependency trees, (2) a biaffine attention mechanism for joint prediction base pairings and their types, and (3) an optimal tree decoding algorithm that enforces valid RNA structural constraints. Unlike tra- ditional energy- mneeey-based methods, DEPfold learns directly from annotated data and leverages pretrained language models to predict RNA structure. We evaluate DEP- fold on both within-family and cross-family RNA datasets, demonstrating signif- icant performance improvements over existing methods. DEPfold shows strong performance in cross-family generalization when trained on data augmented by traditional energy-based models, outperforming existing methods on the bpRNA- new dataset. This demonstrates DEPfold's ability to effectively learn structural information beyond what traditional methods capture. Our approach bridges nat- ural language processing (NLP) with RNA biology, providing a computationally efficient and adaptable tool for advancing RNA structure prediction and analysis.
INTRODUCTION
Ribonucleic acid (RNA) molecules play cru- cial roles in biological processes, including gene expression regulation, protein synthesis, and gene editing systems such as CRISPR- Cas9 (Atkins et al., 2011; Sullenger & Nair, 2016; Grabow & Jaeger, 2014). RNA con- sists of an ordered sequence of nucleotides, each containing one of four bases: adenine (A), guanine (G), cytosine (C), and uracil (U). This sequence is referred to the RNA's pri- mary structure. These bases can form pairs, defining the secondary strucfure, illustrated in Figure 1.
dam
RHA secondaryyyyyo
bese-paii
ponstokkoo basenia
Jom bos pairo
00000O0OO Doooo oooo ooo 000
Arc band oprosetztion with preshet notaton
ctm
ponadoknet
stor
The function of RNA is closely related its secondary structure. Accurate prediction of
00000000000
wowoooooooooooooooo COooOoo 1O000O 000 00000
connector
these structures is essential for understanding RNA functional mechanisms, designing RNA-
targeted drugs, and studying RNA evolution (Puzzarini & Barone, 2018; Saini et al., 2021). While experimental methods such as X-ray crystallography, nuclear magnetic resonance, and cryo-clectron microscopy can determine RNA structures (Zhang et al., 2022: Kappel et al., 2020), these approaches are generally limited by low throughput and high costs. The RNAcentral
Figure 1: RNA secondary structure example and its corresponding dependency structure
Our code is available httph:tt///// http///gtttttttteeee thub. com/ 0256kk/////////oll

---

Published as a conference paper at ICLR 2025
database has cataloged over 24 million non-coding RNA sequences, yet only tiny fraction have perimentally determined structures (The RNAcentral Consortium, 2016). RNA secondary structure prediction is fundamental problem in biology, and serves wetlab biologists in tasks such as drug discovery (Oluoch et al., 2018) () and cell analysis (Sethi et al., 2013).
Currentl,, there are two main methods for RNA structure prediction: energy-based methods and statistical and deep learning methods (Hajiaghayi et al., 2012). With energy based methods, the main prediction algorithm relies on minimizing, in an inference procedure, an energy objective that describes the alignment between the different nucleotides in the RNA sequence. Deep learning methods, on the other hand, rely on the usual machine learning setup, with a training set from which a structured prediction model is learned.
While energy-based models are overall more stable because they do not rely on training and are not sensitive to the distribution of the data they were trained on as deep learning models, their overall performance is often not very high when compared to deep learning models tested within distribution. Deep learning models do not generalize well out of their training distribution, because the amount of RNA sequenced data is small, for example, compared to proteins, where very large models such as AlphaFold (Jumper et al., 2021) are state of the art.
We balance these two issues, and motivated by NLP research on dependency parsing, 2 we develop DEPfold, an RNA structure prediction model, in which dependency parsing supports the following:
A more detailed annotated structure than just basic alignment between nucleotides, This refined structures makes the learning problem easier for the underlying dependency model, it provides additional constraints to the RNA structure, such as explicitly modeling unaligned nucleotides.
A nested structure that follows the underlying assumptions for RNA structures. Pseudoknots excluded, there is an underlying understanding that RNA structures are nested, and this is the reason why often models such as context-free grammars have been used for them (Knudsen & Hein, 1999; Do et al., 2006a). Our dependency model, while locally directly models the alignment between the different nucleotides, also has global constraint in the form of dependency trees that follows a nested structure.
When pscudoknots are being included in the prediction problem, we can support that additional modification by changing the underlying inference algorithm for the dependency parsing model. Pseudoknots, we find, are equivalent to adding a certain level of non non-projecttivity to the depen- dency parsing model, as both notions indicate edges that cross each other in the dependency tree.
Our dependency formulation model is built in such a way that it is easy to incorporate further constraints to the inference problem, such as energy-based constraints. This yields a hybrid model that balances well between learning from data and relying on a physical energy model originating in molecular biology (Zuker & Stiegler, 1981).
Our approach relies on encoding model to transform the RNA sequence into a sequence of embeddings. This component is plug-in, and can used, for example, with a foundation model for RNA structures.
DEPfold adapts the biaffine parser of Dozat & Manning (2016), which uses deep biaffine attention to compute dependency relations. This parser decomposes the task into two modules: one pre- dicting the existence of directed edges between nucleotides, and another predicting the best label for each potential edge. By transforming RNA structures into labeled dependency trees, DEPfold leverages the power of dependency parsing while maintaining biological constraints. This approach effectively predicts both the existence and types of base pairings, including pseudurknots, and can handle RNA sequences exceeding 3000 nucleotides. We conduct extensive experiments to compare DEPfold with tfateoof-the-ar methods on several benchmark datasets, demonstrating its superior performance, particularly in predicting pseudoknots and long-range interactions. Moreover, DEP- fold shows strong cross-family generalization when trained on augmented data, suggesting effective learning of structural information beyond traditional methods.
DDpendenncy parsing is the problem of identifying a syntactic structure for natural language sentence hy identifying head-dependent relationships hetween words. See Kübler et al. (2009) PPscddoknoss are a relatively unique type of bonds hetween nucleotides that violate nestedness in tree.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND AND NOTATION
Our RNA structure prediction algorithm relies on dependency parsing, a method in NLP that pro- vides syntactic structures to natural language utterances (Kübler et al., 2009). These structures origi- nate in the syntactic theory of Tesnière (2015) called dependency grammar. At the core of this theory, is stipulated that there is a head-dependent relationship between words in a sentence, described as edges between the different words that all together constitute a dependency parse tree. More for- mally, given an input sentence I = W Wn. where wi E Σ (an alphabet or a vocabulary). a de- pendency tree, illustrated in Figure 1, is defined as y {(i.j. e) S i S n, 1 S j S n, C), where (i, E) represents a dependency relation E E L from the head word W; to the modifier word Wy. In our case, the words are the nucleotides, and the edges between them describe alignment (or lack of) relationships between them. Dependency trees can be directed or undirected. While the alignments between nucleotides is undirected (corresponding stem structures), we use directed formalism to model more freely both alignment between nucleotides and lack thereof.
RNA consists of an ordered sequence of nucleotides, each containing one of four bases: adenine (A), guanine (G), cytosine (C), and uracil (U), Hence, we denote by X' = Σ¹ where Σ = {A, G, U, U), the set of RNA sequences, by Y the set of RNA structures (in the form of Figure 1) and by 2 the set of all dependency trees over RNA sequences from X. In RNA secondary structures, each nu- cleotide pairs with at most one other nucleotide, forming structures such as stems and loops(Turner & Mathews, 2009). For clarity, we refer to these base-paired structures as stems, and the un- paired nucleotides form loops, as illustrated in Figure 1. A unique structural motif frequently hellcll structure formed by base pairing between
observed in RNA is the pseudoknot, single-stranded regions within stem-loop structures and external complementary sequences(Naderi al., 2021). Formally, a pseudoknot occurs when RNA has two base pairs, i-j and i'-j', such that i < 1' j < j' (Achawanantakun & Sun, 2013). Pseudoknots can function as independent elements or as parts of complex RNA structures, participating in stabilization, replication, RNA processing, toxin inactivation, and gene expression control (Brierley et al., 2007; 2008; Giedroc & Comish, 2009). Therefore, predicting pseudoknots is of significant importance.
In this study, we adopt two methods to represent RNA secondary structures. The first is the are representation, where nucleotides are depicted as vertices and hydrogen bonds as ares (Figure 1). For secondary structures without pseudoknots, all ares are nested or parallel; crossed ares indicate the presence of pseudoknots. The second method the dot-bracket notation, where a represents an unpaired base (loop base), and paired brackets denote base pairs. In this notation, base pairs forming stems are denoted by parentheses 'O', and base pairs forming pseudoknots can be distinguished from stems by using square brackets' [[', angle brackets '(), and so on.
RNA secondary structures are crucial for determining the molecule's three-dimensional conforma- tion and functional properties (Tinoco Jr & Bustamante, 1999). Accurate prediction of these struc- tures aids in inferring tertiary interactions and has applications in drug design (Khatoon et al., 2014), gene regulation studies (Mortimer al., 2014), and --sddseed therapeutics (Yin et al., 2014). By modeling stems, loops, and pseudoknots, we aim to capture the full complexity of RNA secondary structures, enabling more accurate predictions and deeper understanding of RNA functionality.
DEPFOLD: METHODOLOGY
3.1 TRANSFORMATION OF RNA STRUCTURES TO DEPENDENCY
At the core of our algorithm, there is a mapping between RNA structures and dependency trees. Let 7: y/ -> 2 be such mapping. The dependency tree = T(y) attached to y includes all the alignment information in y, but also additional annotation, such as relationships of "lack of align- ment." This additional fine-grained annotated structure further constrains and informs the learning algorithm, and also formulates the basic alignment relationship as a nested structure, following works for grammar-based and energy- RNA structure prediction (Rivas & Eddy, 1999; Zuker & Stiegler, 1981; Dowell& & Eddy, 2004). The transformation process involves four key steps (de- tailed in Appendix A. and B):
Sequence Partitioning Given an RNA sequence x E X' and its secondary structure y E y repre- sented in bracket-dot notation, we partition into three subsets based on the structural information:
3

---

Published as a conference paper at ICLR 2025
S: The stem sequence, comprising nucleotides forming stem structures. In bracket-dot notation, these are represented by matching parentheses "(" and
P = , Pk J: A set of pseudoknot sequences, where each P. contains nucleotides forming distinct pseudoknot. In extended bracket-dot notation, these are typically represented by different types of brackets (e.g., square brackets '[I', curly braces '(". or angle brackets ()") to distinguish multiple pseudoknots.
L: The loop sequence, containing all remaining unpaired nucleotides. These are represented by dots in bracket-dot notation.
Binary Tree Construction For each sequence Q, where Q can be either the stem sequence or any pseudoknot sequence P., we construct a binary tree lQ that preserves its nested structure. The construction follows these rules:
TAg
Initialization: Begin with the first complete pair of matching brackets in Q. denoted by positions i and j. where i < j. This initial node is labeled as S to represent Start.
S11
2. Directionality: Assign the nucleotide at position j as the head and the nucleotide position as the dependent, forming an are (j. i) labeled appropriately (st (stem or pseudoknot).
3. Traversal Order: Proceed in left-first, then right traversal to recursively construct left and right subtrees, maintaining the nested structures. Nodes are labeled with L and R to denote left and right subtrees, respectively.
4. Are Creation and Labeling: For nucleotides under the same head node, we establish ares to connect them in a right-to-left se- quence. The ares labeled based on the structural relationship between the nuclcotides(c.g. Arrow lines Figure 1(bottom).):
Figure 2: Example of binary tree construction for an RNA stem sequence.
Stem Ares: If a pair of nucleotides is part of stem structure, the connecting are labeled as st et.
Pseudoknot Ares: If a pair of nucleotides is part of a pseudoknot structure, the are is labeled as pseudoknot.
Connector Ares: If the nucleotides are not part of either a stem or pscudoknot but are necessary to maintain tree connectivity, the are is labeled as connector.
Figure 2 illustrates the process of constructing binary tree for stem sequence example, where numbers indicate the construction order. Here, S represents the Start pair, and L and It denote the left and right subtrees, respectively. The pseudocode can be found Appendix Algorithm
ROOT Construction For RNA sequences that consist solely of stem structures, we select the overall head node of the stem tree is as the head node of the entire sequence, denoted node g. We then connect this node directly to the ROOT node, forming the complete dependency tree = 7
For RNA sequences that include pseudoknot structures, we first identify node g, and connect it to the ROOT node. We then integrate the stem tree ig with the pseudoknot trees tp, to form a unified tree structure. The steps are as follows:
Identify the head nodes of the stem tree and pseudoknot trees, denoted as Hs and Hr, respectively. Arrange these head nodes according to their positions in the original RNA sequence from right to left.
Head Node Ordering:
Designate the rightmost head node the sequence as the overall head node of the entire sequence, node g. Connect this node g to the ROOT node, Sequential Connection: Connect the remaining head nodes node g using ares labeled as connector, following the right-to-left direction. This forms larger tree structure t'.
ROOT Connection:
By connecting the stem and pseudoknot trees in this manner, ensure that the combined tree accurately reflects the structural relationships and sequence ordering the RNA molecule. The use of connector preserves the necessary dependencies between different structural components.
Tree Completion To ensure that every nucleotide in the sequence is connected and the dependency tree is complete, incorporate the loop nucleotides from T.. For each nucleotide &y E L., we add
4

---

Published as a conference paper at ICLR 2025
an are (k)a k), where: (k) k: ++,, 1, if < pos(g)
where pos(g) denotes the position
1, if k > pos(g)
index of node
The ares are labeled as Loop, and this approach ensures that loop nucleotides are connected their immediate neighbors, maintaining sequential order and tree completeness.
The final output our transformation is the dependency tree Z. which encapsulates the com- plete RNA secondary structure. This dependency tree is composed of two integral components: (1) The set of arcs representing the structural connections between nucleotides, capturing both pase-pairings and necessary connectors for tree completeness.
(2) The set of labels assigned to each are, indicating the type of relationship between nucleotides-such as stem, pseudoknot, connector, or loop. Every nucleotide in the RNA sequence is connected directly or indirectly to the ROOT node, ensuring that & fully connected and rooted dependency tree. The final set of five labels use is C = loop, root, stem, connector, pseudoknot J.e.g. labels in Figure 1(bottom).
This comprehensive representation allows
reformulate RNA secondary structure predic- tion as an optimization problem over dependency trees. Specifically, we aim to find the de- pendency that maximizes the conditional probability given the input RNA sequence æ: z" argmax,ez P(z | x), where z* is the predicted dependency tree, encompassing both the nucleotide connections and their labels.
3.2 UNDERLYING DEPENDENCY MODEL.
Based on the transformation $3.1, we use a biaffine parser as the core of our model for task parsing. Our proposed model, DEPfold, is composed of several key components. The overall archi- tecture is illustrated in Figure 3.
Foundation Model We input an RNA sequence of length N, x X, and embed using a foundation model to obtain contextual representation for each nucleotide in the sequence: ri Embed (x;). The foundation model dation model, such as RNA-fm (Chen et al., 2022),
be pretrained RNA foun-
(edes)
(kubd)
general natural language foundation model like RoBERTa (Liu, 2019).* During this embedding phase, each nucleotide's representation is treated as a word, obtaining its corresponding token represen- tation, and then deriving its contextual representa- tion in the entire sequence.
Biadline Parser
Bladfeslp
Bladf
MPp
Mippd
MLPdor'
MLppbax
MLPP Feature Extraction Dozat & Manning (2016) first proposed using biaffine attention to compute de- pendency relations. This method formulates the de- pendency parsing task as labeling each edge in di- rected graph, decomposing it into two modules: one predicting whether there is directed edge between two words, and another predicting the best label for each potential edge. Similarly, proach to RNA secondary structure model prediction.
Foundation Model
apply this ap-
Figure 3: DEPfold Architecture.
For each nucleotide, we use MLPs obtain dependent and head representations, as in the formulae:
h dep MLP4P((r):
head = MLpphend(n (r:).
where deepp and heaa are the representation vectors of x, as a dependent nucleotide and a head nucleotide, respectively.
'While it may sound counter- intuiti- to use standard language model for RNA sequences, we found out RoBERTa can he applied to RNA sequences effectively. We believe it is because the model is fine-tuned on the RoBERTa's representations, which carry information.
5

---

Published as a conference paper at ICLR 2025
Biaffine Scorer We then use biaffine classifiers to predict scores for edges and labels separately. The biaffine classifier is a generalization of linear classifiers, including multiplicative interactions between two vectors:
Bi e2) = ej Ue2 + W(e1 @ @e2) b, -Baaff(label) nn flabet-dep) (labek-boad)
(edgge) (i. = Biaff(sdge)
h (odgordep)
n ((dge-bhsu)) ((luube))
is a vector of length [c] ranging over labels. We denote by ((aahel) jt. E) the specific value for label l C. The tensor U can be chosen as diagonal matrix (making Ug,k. 0 when i * i) to save parameters. For the labeled parser, U will be (d x c x d)-dimensional, where c is the number of labels. This operation is highly computationally efficient on GPUs.
(i. In the above, (t,
Training Loss The model training is based on simple head nucleotide selection, without considering tree structure, and the losses for all words are accumulated in a mini-batch. For standard head dependent pair (Ii, 2z) with label in the training instance, the cross-entropy loss is:
exp (odge) (i,j))
exp exp (a(labe)) (i. (*)
L (odge) (i.j) log
L (label) (i,j.(") log
Eosren exp (slodge)(r,
Exec exp (s(label) (i, ())
In the overall system training, our goal is minimize the sum of both losses over all dependency (odge) (i, + I. (1,
structures in the training data D: Σ Σ
ZED (K-+),E")E=
Decoding After obtaining scores for all dependency relations, for the head selection of each nu- cleotide, we use the first-order Eisner algorithm (Eisner 2000; for projective structures) or graph spanning tree algorithms (Koo et al. 2007; for non-projective structures) to find the optimal tree 2* without labels: x" = arg max;
Σiijez (i. Based on the obtained optimal tree structure, we select the corresponding maximum label for each pair as the predicted value, leading eventually to the secondary structure y".
tostpprceessing RNA secondary structure only focuses on the connections we predict as stem and pseudoknots, and must comply with the rule that each nucleotide can only connect with one nu- cleotide, we first select those connections labeled as stem and pseudoknots from the predicted RNA dependency parsing structure and convert them into contact map M.
We then use Softmax on M to obtain probability distributions in the row and column directions:
exp(M C(M) Σ (x,(
exp(Mr))
R(M)
Ek (M.)
Finally, we retain the maximum value in the row direction as the connection obtain the final op- timized contact matrix M which ensures that the resulting connection structure is not confficting: M arg ma)(R(MM)..
4 EXPERIMENTAL SETUP
Dataset We evaluate DEPfold on four widely-used RNA structure prediction benchmark datasets:
RNAStrAlign (Tan al., 2017) contains 37,149 structures from 8 RNA familics. Following E2Efold (Chen et al., 2020) and MXfold2 (Sato et al., 2021), we processed the dataset, retaining 30,451 non- redundant structures. Archivell (Sloma & Mathews, 2016), comprising 3,975 structures from 10 RNA families, serves as a standard benchmark for classical RNA folding methods. Both datasets include sequences with pseudoknots.
bmRNA-Im (Singh et al., 2019) includes 102,318 structures from 2,588 RNA families. We pro- cessed it following SPOT-RNA (Singh et al., 2019), using CD-HIT (Fu et al., 2012) for redundancy removal and dataset splitting. bpRNA-new (Kalvari et al., 2017), derived from Rfam 14.2, contains sequences from 1,500 novel RNA families and is used assess cross- gross-family generalization. Consis- tent with UFold (Fu et al., 2022), we augmented the training data by randomly mutating bpRNA-new sequences and generating structure predictions using RNAfold (Lorenz et al., 201 1b). Sequences in bpRNA-In Im and neRNA-new are shorter than 500 nucleotides and lack pseudoknots, contrasting with the first two datasets. Table summarizes the key characteristics of each dataset.

---

Published as a conference paper at ICLR 2025
Baseline Methods We compare proposed DEPfold Table 1: Summary of datasets used in with several baseline methods, including:
experiments.
Energy-based folding methods: CONTRAfOld (Do et al., 2006b), RNAfold (Lorenz et al., 2011b), LinearFold (Huang al., 2019)using the thermodynamic free engy model from Vienna RNAfold(Lorenz et al., 20)1))) and RNAstructure (Reuter Mathews, 2010) the ProbKnot(Bellaousoy & Mathews, 2010) algorithm when predicting RNA datasets with pseudoknots). Learning- based folding methods: E2Efold (Chen et al., 2020), MX- fold2 (Sato et al., 2021), UFold (Fu et al., 2022), and RFold (Tan et al., 2024).
Dataset
Subset
#Seq.
Len. Range
RNAStrAlign
Train
28,969
30-1581
Val
3,629
96-1693
Test
2,810
57-1672
Archivell
3,975
28-2968
bpRNA-Im
TRO
10,814
33-498
VI.0
1,300
33-497
TSO
1,305
22-499
bpRNA-aug
TRI
220,431
33-498
Evaluation Metrics As standard in RNA structure pre- diction, we evaluated performance using precision (or PPV, Positive Predictive Value), recall (or SEN, sensitivity), and F1 score. More specifically, the set of all aligned pairs are extracted from both the predicted structure and the reference structure, and the macro-averaged statistics are calculated based on them.
bpRNA-new
5,401
33-489
5 RESULTS
To evaluate the performance of our DEPfold model relative to baseline models, we conducted two sets of experiments, following similar approach to that of Fu et al. (2022); Sato et al. (2021): (a) training the model on the RNAStrAlign training set and testing on the RNAStrAlign test set and the Archivell dataset; (b) training the same model the bpRNA-I training set (TRO) and testing on the bpRNA-Im test set (TSO), as well as training on bpRNA-Im augmentation set (TRI) and testing on the bpRNA- (bpnew) dataset. For detailed information on the model training process, see Appendix C.
5.1 PERFORMANCE ON RNASTRALIGN AND ARCHIVEII
We assessed the performance of DEPfold on the RNAStrAlign test set, and the results are presented in Table 2. DEP- fold achieved the best performance across all evaluation met- rics. Compared to traditional energy-based algorithms, DEP- fold demonstrated signíficant advantages over both traditional methods such LinearFold and RNAfold and other deep learning methods such as E2Efold and Ufold. In addition, DEPfold surpassed other deep learning methods in both preci- sion and recall. Finally, DEPfold can handle RNA sequences of arbitrary lengths, whereas E2Efold, RFold and UFold constrained by a fixed maximum sequence length (c.g., 1,800 nucleotides).
Table 2: Performance comparison on RNAStrAlign test set.
Method
Precision Recall
F
DEPfold UFold
0.988
0.983 0.985
0.959
0.965 0.962
RFold
0.942
0.780 0.797
E2Efold
0.866
0.788 0.821
ContraFold
0.600
0.647 0.621
LinearFold
0.523
0.576 0.547
RNAfold
0.515
0.568 0.539
RNAstructure
0.537 0.569 0.551
Pseudoknot Prediction To evaluate DEPfold's ability to handle complex RNA structures, particularly sequences containing pseudoknots, we analyzed sequences with pseudoknots in the RNAStrAlign test set. Following the methodology of E2Efold (Chen et al., 2020), we calcu- lated the average F, score (Set F2) for these sequences and counted the number of sequences where the presence or absence of pscudoknots was correctly predicted. Ta- ble 3 summarizes the evaluation results.
Table 3: Evaluation of pseudoknot pre- diction.
Method
Set Fi
TP
FP
TN
FN
DEPfold Ufold E2Efold
0.981
1258
20
1531
0.838
159
111
1397
0
0.710
1312
242
1271
0
RNAstructure
0.474
975
306
1245
284
Rfold
0.447
685
55
1470
122
DEPfold achieved the highest F1 score of 0.981 on this set, significantly outperforming other methods. It demonstrated high accuracy in identifying both pseudoknotted and non psuuskouoddotteed sequences, while maintaining low false positive and false negative rates. These results indicate that DEPfold exhibits exceptional capability in handling com-

---

Published as a conference paper at ICLR 2025
plex RNA structures containing pseudoknots, showeasing its potential to effectively capture the intricacies of RNA structural complexity.
Generalization to Archivell To assess DEPfold's generalization ability, directly tested the model trained on the RNAStrAlign training set on the Archivell dataset. Table 4 compares the performance of DEPfold with other methods the ArchivelI dataset. DEPfold achieved F₁ score of 0.920 on this dataset, significantly higher than other methods, and also obtained the highest precision and recall. This demonstrates that DEPfold not only achieves strong results on specific tasks but also has the capacity to adapt to wide range of RNA secondary structure prediction tasks.
Table 4: Performance comparison on
Table 5: bpRNA-TSO set.
Performance comparison on
Archivell set.
Method
Precision
Recall
Fi
Method
Precision
Recall
Fi
DEPfold
0,941
0.907
0.920
DEPfold
0.730
0,656 0.676
RFold
0.931
0.899 0.911
RFold
0.676
0.625 0.633
UFold
0.876
0.890
0.881
UFold
0.587
0.711 0.630
MXfold2
0.825
0,780 0.796
MXfold2
0,519
0.646 0.558
E2Efold
0.734
0.660 0.686
ContraFold
0.482
0.655 0.541
ContraFold
0.593
0.649 0.617
LinearFold
0.447
0,633 0,510
LincarFold
0,549
0.609 0,575
RNAfold
0.446
0.631 0.508
RNAfold
0,550
0.611 0.577
RNAstructure
0.446
0.622 0.505
RNAstructure
0.554
0.601 0.573
5.2
PERFORMANCE ON THE BPRNA DATASET
Following prior studies (Sato et al., 2021: Fu et al., 2022), trained on bpRNA-TRO and evaluated bpRNA-TSO using the best model obtained from -VO.. Detailed results presented in Table 5. DEPfold significantly out- performed UFold in terms of F, score, with an improve- ment of 7 percentage points, and achieved 25% enhance- ment over traditional methods.
Table 6: Performance on long-range
base pair prediction (bpRNA-TO) -SO)
Method DEPfold
Precision Recall
Fi
0.715 0.689 0.689
UFold
0.630 0.711 0.653
RFold
0.666 0.647 0.643
ContraFold
0.505 0.614 0.536
Long-range Interaction Prediction To evaluate whether DEPfold contributes to improved prediction of long-range RNAfold
LincarFold
0,502 0.629 0.542
0,499 0.627 0.539
interactions, we adopted the same experimental approach as UFold. We used the TSO dataset as the test set because it contains diverse sequences of vary- ing lengths from various RNA families. For a sequence of length L,, we define base pairs with separation greater than L/2 as long-range base pairs. As shown in Table 6, DEPfold is able to pre- dict long-range base pairs, outperforming UFold. Notably, DEPfold's performance in predicting long-range base pairs comparable to, even slightly better than, its performance in predicting short-range base pairs.
RNAstructure
0.490 0.603 0.523
Cross-family Evaluation bpRNA-new The bpRNA- new dataset a cross-family benchmark dataset that poses significant challenges purely deep learning methods be- cause these families are not represented in the training set. To address this issue, MXfold2 proposed combining free energy minimization with deep learning methods, achiev- ing performance similar to the searmoddyaaiee-bascee Con- traFold. The purely deep learning method DEPfold, which based on data augmentation (TRI dataset for training) from RNAfold, achieved an F1 score of 0.621 on the bpRNA-new dataset, exceeding RNAfold by 0.65 percent- age points. This result indicates that DEPfold can learn more useful structural information on top of what traditional which also uses data augmentation, performed slightly worse than RNAfold this dataset.
Table 7: Performance comparison on bpRNA-new.
Method
Precision Recall
DEPfold
0.650 0.624 0.621
UFold
0.527
0.695 0.590
RFold
0,528
0.306 0.369
MXfold2
0.585
0.710 0.632
ContraFold
0.578
0.736 0.639
LinearFold
0.551
0.719 0.615
RNAfold
0.552
0.720 0.617
RNAstructure
0.542
0.703 0.604
methods capture. In contrast, UFold,
5.3 ABLATION STUDY
To gain deeper insight into the contributions of various components of DEPfold, we conducted a series of ablation experiments.
8

---

Published as a conference paper at ICLR 2025
Pretrained Models We compared the effectiveness of us- ing RoBERTa and RNAfm as RNA sequence representa- DEPfold-Ro and
Table 8: Ablation Study on Pretrained
Models and Fine-Tuning (bpRNA- TSO).
tion generators. which are denoted DEPfold-fm, respectively. RoBERTa is a general-purpose large-scale language model, while RNAfm is pretrained model specifically designed for RNA sequences. Table 8 presents the results. The DEPfold model based on RNAfm achieved an F1 score of 0.618 on TSO, slightly lower than the version using RoBERTa. This suggests that although RNAfm is specialized for RNA sequences, the general language representations pro- vided by RoBERTa perform better in this task.
Method
Precision Recall
DEPfold Fo.FT
0.730
0.656
0.676
DEPfold-fm.
0.719
0.574
0.618
DEPfold-Ro,Fi DEPfold-fm.Fet
0.428
0.174 0.217
0.644
0.422 0.470
Fine-Tuning vs. Freezing Pretrained Models We further investigated the impact of fine-tuning versus freezing the pretrained models on DEPfold's performance. As shown in Table 8, fine-tuning the pretrained models (FT) significantly enhances the model's ability to predict RNA secondary structures. In contrast, freezing the pretrained models (FrZ) leads to substantial performance degra- dation, with the model nearly failing to learn meaningful representations for RNA secondary struc- ture prediction. Interestingly, under frozen conditions, the model using RNAfm performed slightly better than the one with RoBERTa, possibly because RNAfm, being specifically pretrained RNN sequences, had already captured some RNA-specific features during its pretraining phase.
Optimal Tree Decoding We evaluated the impact of the optimal tree decoding algo- rithm on DEPfold's performance by compar- ing the model with and without this strat- egy. The results are presented in Table 9, where "DEPfold w/o OT denotes the DEP- fold model without the Optimal Tree decod- ing strategy. The findings show that incor- porating Optimal Tree decoding consistently enhances performance across both datasets. On TSO, the F1 score increases from 0,671 to 0.676
Table 9: Ablation Study on Optimal Tree Decoding (bpRNA).
Dataset
Method
Precision
Recall
TSO
DEPfold DEPfold w/o OT
0.730
0,656
0.676
0.676
0.686 0.671
bpRNA-new DEPfold
0.650
0,624
0.621
DEPfold w/o OT
0.632
0.613
0.607
when optimal tree decoding is used, primarily due to an increase in precision from 0.676 to 0.730. Similarly, bpRNA-new, the F1 score improves from 0.607 to 0.621. These enhancements demon- strate that optimal tree decoding effectively enforces valid RNA structural constraints during decod- ing, leading to more accurate and biologically plausible predictions.
6 RELATED WORK
Traditional Methods Traditional approaches include alignment-based and single-sequence predic- tion methods. Alignment-based methods like the Sankoff algorithm (Sankoff, 1985) and its vari- ants ants-Dynalign (Mathews & Turner, 2002) and Carnac (Touzet & Perriquet, 2004) predict struc- tures by identifying conserved motifs among homologous sequences. However, their effectiveness is limited by the limited number of RNA families in databases like Rfam (Kalvari al., 2021) and low sequence conservation. Single-sequence methods, such as Vienna RNAfold (Lorenz et al., 10) and Mfold (Zuker, 2003), predict structures by minimizing free energy based on thermodynamic models. While effective for short sequences, they struggle with efficiency and accuracy on com- plex structures, particularly pseudoknots, which pose NP-complete challenges (Lyngsø & Pedersen, 2000). Tools like RNAsstructure (Reuter & Mathews, 2010) extend capabilities to include pseudo- knot prediction and external constraints but face computational bottlenecks with long sequences.
Machine Learning and Deep Learning Methods Deep learning models have been introduced for RNA structure prediction. SPOT-RNA (Singh et al., 2019) combines ResNet (Koonce Koonce, 2021) and bidirectional LSTM (Hochreiter, 1997) but lacks constraints to ensure valid structures, af- fecting generalization (Amos & Kolter, 2017). E2Efold (Chen et al., 2020) uses convex optimization and algorithm unrolling to constrain outputs. UFold (Fu et al., 2022) uses convolutional networks on image representations of sequences, enhancing pseudoknot prediction. MXfold2 (Sato et al., 2021) combines deep learning with thermodynamic models, generalizing well across families. However, these models generally struggle with long sequences; for example, SPOT-RNA supports up to 2000 nucleotides, E2Ffold up 1800, UFold up to 600, and MXfold2 up to 1000 nucleotides.
9

---

Published as a conference paper at ICLR 2025
NLP-Inspired Methods NLP techniques have been applied to RNA structure prediction. Linear- Fold (Huang et al., 2019) reduces prediction time from quadratic to linear using beam pruning (Huang et al., 2012), popular heuristic widely used in computational linguistics, but cannot predict pseudoknots. ContextFold (Zakov et al., 2011) and CONTRAfold (Do et al., 2006b) use context- free grammars for base-pair dependencies, improving accuracy but still struggling with complex structures like pscudoknots. Matsui et al. proposed a new structural alignment algorithm based on pair stochastic tree adjoining grammars (PSTAGs) to align and predict RNA secondary structures, including pseudoknots. NLP methods improve computational efficiency and handle some com- plex structures, but integrating deep learning for RNA secondary structure prediction, especially for pseudoknots and long sequences, remains challenging.
7 CONCLUSION
In this work, we introduced DEPfold, a novel RNA secondary structure prediction framework that reformulates the task as dependency parsing by leveraging advanced NLP techniques. DEPfold transforms RNA structures into labeled dependency trees, uses a biaffine attention mechanism for accurate base pairing prediction, and uses optimal tree decoding to ensure biologically valid struc- tures. Our approach significantly outperforms traditional energy- based methods and state-of-the-an art deep learning models, achieving Fl score of 0.985 on the RNAStrAlign dataset (which note, though, is a within-family dataset) and effectively capturing complex features such as pseudoknots and long-range interactions. Furthermore, DEPfold demonstrates robust cross-famile generalization on the bpRNA-new dataset, identifying structural nuances that conventional models miss. Ablation studies highlight the unexpected efficacy of general-purpose models like RoBERTa in fine-tuning, indicating potential for specialized pretraining strategies in RNA biology. While DEPfold marks significant advancement, future work will address challenges enhancing cross-family general- ization and model interpretability by expanding training data diversity, optimizing computational efficiency, and improving interpretability to broaden DFPfold's applicability in diverse biological research contexts.
LIMITATIONS
Our experiments on within-family datasets, such as RNAStrAlign and bpRNA-TSO, show that DEP- fold achieves high F, score, indicating effective learning from the training data. However, when evaluated on cross-family datasets like npwNNA-new-whin in the training sct-DEPiold's performance shows smaller margin of improvement (outperforming RNAfold by only 0.65 percentage points). This suggests that while DEPfold can capture structural information beyond traditional methods, its ability to generalize to entirely new RNA families is still limited. See discussion by Szikszai et al. (2022) and Bernett et al. (2024).
includes RNA families not represented
Our data augmentation strategy, which RNAfold-predicted structures, while beneficial, may reinforce existing biases in traditional energy-based models. While effective in increasing training data, this approach may limit DEPfold's ability learn non-traditional structural patterns. Future work should explore more diverse data augmentation techniques that introduce a wider range of structural variations. Additionally, scaling DEPfold to larger model sizes and datasets, and incorpo- rating neural dependency parsing models like stack-pointe (Ma, 2018) and TreeCRF (Zhang et al., 2020a;b), could enhance its ability learn from diverse syntactic representations and improve over- all capabilities.
interesting finding from our ablation studies is the superior performance of RoBERTa over RNA- fm in the fine-tuning stage. This result prompts us to rethink the optimal pretraining strategy for RNA structure prediction. RoBERTa's general language patterns seem to provide more valuable context for structure prediction than RNA-fm's RNA-specific features. This suggests that current RNA-specific models may not fully capture the characteristics needed for accurate structure predic- tion. Our findings suggest the need for developing more effective pretraining approaches specifically designed for RNA biology, which could potentially improve the accuracy and generalization capa- bilities of models like DEPfold.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers, Grzegorz Kudla, Mengyu Wang and Ajitha Rajan for feedback and useful comments. We appreciate the provision of compute resources through the Baskerville cluster (University of Birmingham). This work was supported by the United Kingdom Research and Innovation (grant EP/S02441X/II,, UKRI Centre for Doctoral Training Biomedical AI at the University of Edinburgh, School of Informatics.
REFERENCES
Rujira Achawanantakun and Yanni Sun. Shape and secondary structure prediction for nemas includ- ing pseudoknots based on linear svm. BMC bioinformatics, volume 14, pp. 1-11. Springer, 2013.
Brandon Amos and Zico Kolter. OptNet: Differentiable optimization as layer in neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 136-145. PMLR, 06-11 Aug 2017. URL https: http::::/proceedingg .ml. www..pres/vv00 amosl html.
John F Atkins, Raymond F Gesteland, and Thomas Cech. RNA worlds: from life 's origins to diver- sity in gene regulation, volume 2011, Cold Spring Harbor Laboratory Press New York,, 2011.
Stanislav Bellaousov and David Mathews. Probknot: fast prediction of RNA secondary structure 2010.
including pseudoknots. RNA, 16(
Judith Bernett, David B Blumenthal, Dominik Grimm, Florian Haselbeck, Roman Joeres, Olga Kalinina, and Markus List. Guiding questions to avoid data leakage in biological machine learning applications. Nature Methods, 21 21(8): 1444-143,, 2024.
Ian Brierley, Simon Pennell, and Robert JC Gilbert. Viral RNA pseudoknots: versatile motifs in
gene expression and replication. Nature Reviews Microbiology. 5(8):598-610) 610, 2007.
Ian Brierley, Robert JC Gilbert, and Simon Pennell. RNA pseudoknots and the regulation of protein synthesis. Biochemical Society Transactions, 36(4):684 689, 2008.
Jiayang Chen, Zhihang Hu, Siqi Sun, Qingxiong Tan, Yixuan Wang, Qinze Yu, Licheng Zong, Liang Hong, Jin Xiao, Tao Shen, et al. Interpretable RNA foundation model from unannotated data for highly accurate RNA structure and function predictions. arXiv preprint arXiv:2204. 00300, 2022.
Xinshi Chen, Yu Li, Ramzan Umarov, Xin Gao, and Le Song. RNA secondary structure prediction by learning unrolled algorithms. arXiv preprint arXiv:2002.05810, 2020.
Chuong B. Do, Daniel A. Woods, and Serafim Batzoglou. Contrafold: RNA secondary structure
prediction without physics- based models. Bioinformatics, 22 14:e90-8, 2006a. URL https:
//api. semanticscholle wwwpaachoaaarrre/.C..o wwtp//oopuueeeee 1646946..
Chuong B Do, Daniel A Woods, and Serafim Batzoglou. Contrafold: RNA secondary structure prediction without physics- based models. Bioinformaties, 22(14)x990-e98 2006b.
Robin Dowell and Sean Eddy. Evaluation of several lightweight stochastic context-free gram- mars for RNA secondary structure prediction. BMC bioinformatics, 5:1-14, 2004.
Timothy Dozat and Christopher D Manning. Deep biaffine attention for neural dependency parsing- arXiv preprint arXiv:1611.01734 2016.
Jason Eisner. Bilexical grammars and their cubic-time parsing algorithms. Advances in probabilistic and other parsing techmologies, pp. 29-61, 2000.
Laiyi Fu, Yingxin Cao, Jie Wu, Qinke Peng. Qing Nie, and Xiaohui Xie. Ufold: fast and accurate RNA secondary structure prediction with deep learning. Nucleic acids research, 50(3)ee14 e14, 2022.
11

---

Published as a conference paper at ICLR 2025
Limin Fu, Beifang Niu, Zhengwei Zhu, Sitao Wu, and Weizhong Li. CD-HIT: accelerated for clus- tering the geet-gennr sequencing data. Bioinformatiis, 28023):150-3115, oct oct 2012. doi: 10. 1093/bionformaticc//bssto URL 2Fbts565..
David P Giedroc and Peter V Cornish. Frameshifting RNA pseudoknots: structure and mechanism. Virus research, 139(2):193-22)) 2009.
Wade W. Grabow and Luc Jaeger. RNA self-assembly and RNA nanotechnology. Accounts of chemical research, 47 6: 1877108,, 2014. URL https: /ttt://apl www.ssetttccsooo....o.... Corpus
http:s//ep....emmtiiiiiiiiioeii .rrg/
Monir Hajiaghayi, Anne Condon, and Holger H. Hoos. Analysis of energy-based algorithms for RNA secondary structure prediction. BMC Bioinformatics, 13:22 22, 2012. URL https:
/ //ap.. www.atteeiii...................e comaaticcccollar... wtt.hoolla...r/ooooossstta 16689908.
S Hochreiter. Long thort-term memory. Neural Computation MIT-Press, 1997.
Liang Huang, Suphan Fayong, and Yang Guo. Structured perceptron with inexact search. In Pro- ceedings of the 2012 Conference of the North American Chapter of the Association for Computa- fional Linguistics; Human Language Technologies, pp. 142-151, 2012.
Liang Huang, He Zhang, Dezhong Deng, Kai Zhao, Kaibo Liu, David Hendrix, and David H Mathews. Linearfold: timear-time approximate RNA folding by 5' 3t-to-3' 3oo-3'dynamic programming and beam search. Bioinformatics, 35(1 35(14):1295-i304 2019.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger,
Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate 2021.
protein structure prediction with alphafold. nature, 596(7873):583-5555
Ioanna Kalvari, Joanna Argasinska, Natalia Quinones-Olvera Eric P Nawrocki, Elena Rivas, Sean R Eddy, Alex Bateman, Robert D Finn, and Anton I Petrov. Rfam 13.0: shifting a genome-centric resource for non-coding RNA families. Nucleic Acids Research, 46(D1): D342,, nov 2017. doi: 10. 10.109///ar//kx 1038. URL https: http:/::/doo..r/g/////// 100 /ttp://.....g..0......eeaaaa....
Ioanna Kalvari, Eric P Nawrocki, Nancy Ontiveros-Palaciae Joanna Argasinska, Kevin Lamkiewiez, Manja Marz, Sam Griffiths-Jones, Claire Toffano-Nioche, Daniel Gautheret, Za- sha Weinberg, et al. Rfam 14: expanded coverage of metagenomic, viral and microRNA families. Nucleic Acids Research, 49(D1):D192 22000,,2---00, 2021.
Kalli Kappel, Kaiming Zhang, Zhaoming Su, Andrew M. Watkins, Wipapat Kladwang, Shanshan Li, Grigore Pintilie, Ved V. Topkar, Ramya Rangan, Ivan N. Zheludev, Joseph D. Yesselman, Wah Chiu, and Rhiju Das. Accelerated cryo-EM-guided determination of three-dimensional RNA-only structures. Nature Methods, 17(7):699-700 707, jul 2020. doi: 00238/445922020-000 https: //tp:///oiii../oo /10 1038 4 11211922222 00000000000--0--
URL
Zainab Khatoon, Bryan Figler, Hui Zhang, and Feng Cheng. Introduction to RNA-Seq and its applications to drug discovery and development. Drug development research, 75(5)3324-330 2014.
Bjame Knudsen and Jotun Hein. RNA secondary structure prediction using stochastic context-
free grammars and evolutionary history. Bioinformatics, 15 6:446-54, 1999. URL https: / //api. www.seeaasnaaeeee www.eetticcchola..oooo...... wtt.oorrroorrp..::51111..
Terry Koo, Amir Globerson, Xavier Carreras, and Michael Collins. Structured prediction models via the matrix-tree theorem. In Jason Eisner (ed.), Proceedings of the 2007 Joint Conference on Empirical Methody Natural Language Processing and Computational Natural Language Learning SEMNLP-CONLLL pp. 141-150, Prague, Czech Republic, June 2007. Association for Computational Linguistics. URL https: / wtwp:/o000...r00000000001000
Brett Koonce and Brett Koonce. Resnet 50. Convolutional neural networks with swift for tensorflow: image recognition and dataset categorization, pp. 63-72, 2021.
12

---

Published as a conference paper at ICLR 2025
Sandra Kübler, Ryan McDonald, and Joakim Nivre. Dependency parsing. In Dependency parsing, Pp. 11-20. Springer, 2009.
Yinhan Liu. Roberta: robustly optimized bert pretraining approach. vrXiv:1907.1 2019.
arXiv preprint
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-14, 20
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. Algorithmss for Molecu- lar Biology, 6(1), nov 201 doi: 10.1186/1748-7188---2 URL https: http:://oooooooooo 1186 1122211481 748 1 6-26.
Rune B Lyngsø and Christian NS Pedersen. RNA pseudoknot prediction in energy-based models.
Journal of computational biology, 7(3-4):409-477 427, 2000.
X Ma. Stack-pointer networks for dependency parsing, arXiv preprint arXiv: 1.XXv:8805.000555 2018.
David H Mathews and Douglas H Turner. Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. Journal of molecular biology, 317
2002.
Hiroshi Matsui, Kengo Sato, and Yasubumi Sakakibara. Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures. In Proceedings. 2004 IEEE Computational Systems Bioinformatics Conference, 2004. CSB 2004., pp. 990-299. IEEE, 2004.
Stefanie A Mortimer, Mary Anne Kidwell, and Jennifer A Doudna. Insights into RNA structure and function from genome-wide studies. Nature Reviews Genetics, 15(7):469-4)) 2014.
Davoud Naderi, Raheba Jami, and F Rehman. review of RNA motifs, identification algorithms and their function on plants. Journal of Plant Bioinformatics and Biotechnology, 1(1):28-40, 2021.
Ian Kings Oluoch, Abdullah Akalin, Yilmaz Vural, and Yavuz Canbay. review on RNA sec- ondary structure prediction algorithms. 2018 International Congress Big Data, Deep Learn- ing and Fighting Cyber Terrorism (IBIGDELFT), pp. 18-23, 2018. URL https:/ app. semanticschol
org/ wtt.://aa.....ooooos.......... 592363881
Cristina Puzzarini and Vincenzo Barone. Diving for accurate structures in the ocean of molec- ular systems with the help of spectroscopy and quantum chemistry. Accounts of chemical re- search, 51 2:548-556, 2018. URL pestts://appt www.nticschooiie....e.. wwt.or////ooooooo htrg//orppss:: 206384444.
Jessica S Reuter and David H Mathews. RNAstructure: software for RNA secondary structure prediction and analysis. BMC bioinformatics, 11:1-9, 2010.
Elena Rivas and Sean R Eddy. A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of molecular biology, 285(5):2053-200 2068, 1999.
Vandana Saini, Rajni Dawar, Shilpa Suneja, Sukanya Gangopadhyay, and Charanjeet Kaur. Can microRNA become next-generation tools in molecular diagnostics and therapeutics? a sys- tematic review. Egyptian Journal of Medical Human Genetics, 22, 2021. URL https: seapppsssmmnnicccol.rrr..
Corpporruuuaaaa 231695552.
David Sankoff. Simultancous solution of the RNA folding, alignment and protosequence problems. SIAM journal on applied mathematics, 45(5):810 825, 1985.
Kengo Sato, Manato Akiyama, and Yasubumi Sakakibara. RNA secondary structure prediction
using deep learning with thermodynamic integration. Nature communications, 12(1):941, 2021.
Seema Sethi, Shadan Ali, Philip A Philip. and Fazlul H Sarkar. Clinical advances in molecular biomarkers for cancer diagnosis and therapy. International journal of molecular sciences, 14(7): 14771-14784, 2013.
13

---

Published as a conference paper at ICLR 2025
Jaswinder Singh, Jack Hanson, Kuldip Paliwal, and Yaoqi Zhou. RNA secondary structure predic- tion using an ensemble of two-dimensional deep neural networks and transfer learning. Nature communications, 10(1):5407, 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-811 oct 2016. doi: 10.1261. mm.0556944 115. URL httpp:://aet /dwi. org/ 1 0. 1261111668 $2F 053694. 115.
Bruce A. Sullenger and Smita K. Nair. From the RNA world the clinic. Science, 352:1417 1420, 2016. URL
sct.t/pp...atttiiccccccccoaaaaaa :tt.:oaaa..rr/rorrusiii:::0000 :0:64445330
Marcell Szikszai, Michael Wise, Amitava Datta, Max Ward, and David H Mathews. Deep learn- ing models for RNA secondary structure prediction (probably) do not generalize across families. Bioinformatics, 38( 38(16):3892-3899 2022.
Cheng Tan, Zhangyang Gao, Hanqun Cao, Xingran Chen, Ge Wang. Lirong Wu, Jun Xia, Jiang- bin Zheng, and Stan 7. Li. Deciphering RNA secondary structure prediction: probabilistic k- rook matching perspective. In International Conference Machine Learning, pp. 47564-47578 PMLR, 2024.
Zhen Tan, Yinghan Fu, Gaurav Sharma, and David H. Mathews. TurboFold II: RNA structural alignment and secondary structure prediction informed by multiple homologs. Nucleic Acids Research, 1570-11111 sep 2017. doi: (0.1093//r// URL https::////....... /doii org/
Lucien Tesnière. Elements of structural synlax. John Benjamins Publishing Company, 2015.
The RNAcentral Consortium. RNAcentral: comprehensive database of non-coding RNA
quences. Nucleic Acids Research, 45(D1):D128-D134 10 2016. ISSN 0305-1048. doi: 10. 10.1093/nar/gkw11000 1008. URL https: : / doi. org/10 101.1093//aa 1.93//arrgg<w1003.
Ignacio Tinoco Jr and Carlos Bustamante. How RNA folds. Journal of molecular biology, 293(2): 271-281, 1999.
Hélene Touzet and Olivier Perriquet. Carnac: folding families of related RNAs. Nucleic acids research, 32(suppl_2): WWWWW112WWWF- 142-5145, 2004.
Douglas Turner and David Mathews. NNDB: the nearest neighbor parameter database for pre- dicting stability of nucleic acid secondary structure. Nucleic Acids Research, 1 D282, oct 2009. doi: n0.1099/ma//kkp892. URL https: /ttps://dalt /ttp:///oii..ii. org/10 111.0....13..aaa 2F 2kgkp892.
Hao Yin, Rosemary L Kanasty, Ahmed A Eltoukhy, Arturo J Vegas, Robert Dorkin, and Daniel G Anderson. Non-viral vectors for gene-based therapy. Nature reviews genetics, 15(8)5541-555, 2014.
Shay Zakov, Yoav Goldberg, Michael Elhadad, and Michal Ziv-Ukelson. Rich parameterization improves RNA structure prediction. Journal of Computational Biology, 18(1 18(11) 2011.
Jinsong Zhang, Yuhan Fei, Lei Sun, and Qiangfeng Cliff Zhang. Advances and opportunities in RNA structure experimental determination and computational modeling. Nature Methods, 19 110):1193-1207, 2022.
Yu Zhang, Zhenghua I.,, and Zhang Min. Efficient second-order TreeCRF for neural dependency parsing. Proceedings of ACI., pp. 3295-3305, 2020a. URL https: //tp://wwwwww///. acl web. org/
mathology/2023 acll mamin.300
Yu Zhang, Houquan Zhou, and Zhenghua Li. Fast and accurate neural CRF constituency parsing. In Proceedings of IJCAL, pp. 4046-4053, 2020b. doi: 10.24963ijcaii.22205566 URL https:
/ //doi. oaallorrg100.1 0ttp:/.1..4966/// 22993/iiccai htt////caaa.22005/.13.. 2020/5620
M. Zuker. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Research, 31(13):3406-3415 jul 2003. doi: 10.1093/ma//kkg555. URL https: : /oo.. .rg/
10. www.11999nnn22ggk..no.
14

---

Published as a conference paper at ICLR 2025
Michael Zuker and Patrick Stiegler. Optimal computer folding of large RNA sequences using ther- modynamics and auxiliary information. Nucleic acids research, 1()):133-148, 1981.
15

---

Published as a conference paper at ICLR 2025
A PSEUDOCODE FOR RNA SECONDARY STRUCTURE TO DEPENDENCY STRUCTURE
To clearly explain the algorithmic logic for converting RNA secondary structures into dependency structures, we present the following pseudocode. Algorithm the main program, which uses the get-pair function defined in Algorithm 2 to generate binary tree structures from stem and pseudo- knot sequences. The Get_Pail function, during its processing, utilizes the Is Is_Connect function defined in Algorithm 3 for decision decision-making, When handling unpaired structures, the algorithm em- ploys the get pairs function defined in Algorithm 4.
The primary input to the algorithm consists of the RNA sequence, the base pairs of stems and pseudoknots, and a list of indices representing unpaired dots. Through this algorithm, one can derive the arc connections and labels of the dependency structure for the given RNA sequence.
Algorithm 1: Algorithm for Converting RNA Secondary Structure Dependency Structure
Input: RNA sequence length stem base pairs S, pseudoknot base pairs P, unpaired base indices D, dot-bracket notation dot, connectivity table ctList
Output: Tree structure arcs and (abels("sten)
"pseudoknot', 'loop', 'connector', 'root")
Initialize empty lists: last_node list + [] Sp + []. Pp + 1l, Lp + []:
Initialize -ndices
dorli] =' }]
// Process Stem Pairs if S is not empty then Initialize dol <- ['-] X vı;
foreach (1,r) in S do
dot(1 1 +' dor - 1] <');:
end
Convert dot to a string:
Identify stem indices <- {i dorli] E (Y
10
Sp < get wwt.tpttttireeeeeee (dor stem indices), stem setessteeiieee indices); dast_node list;
11
Append stem indices(dii)) end
// Process Pseudoknot Pairs if P is not empty then
13
foreach in P do Initialize dot <- ['-1] x n;; foreach (1.r) in set do
15
dor[l 1] +' (', dor|r 1] +';;
end
19
Convert dot to string;
Identify pse indices {i dorli] (C have pair get pair(dol(pse indices), pse indices);
20
22
Extend P, with have_pair;
Append pse_indices[-]] to lost
end 24
25
end
// Combine Trees Together
16 Sort last node in decreasing order;
27 connect-pair + (llast_node list((, last.node.lisffi + 1]) t llaet_nooe Jist - -2};
28 Extend S. with connect pair,
// Process Unpaired Bases Initialize result list t []. temp list <- []:
16

---

Published as a conference paper at ICLR 2025
Continue the algorithm from previous part; for i from (dot_indices do
if or dot indices = dot inddiesss 1] + then
Append dot inndices list.
else
Append temp list to result list;
temp_list < [dot_ :
Append temp_list to result_litt;
Lp < get.pairs irettpaaiisrssllul.u... (result last nod)_ls(())))
// Are Creation and Labeling
Adjust indices in Sp. Pp. Lp to be based-1 (if necessary);
n Initialize arrays are t [0] x (n + 1), rel + [0] x (n + 1);
Initialize empty dictionaries heads () relations 0:
foreach (head, dep) in Sp do heads] Reads[dep] <- head; if (head, dep) or (dep, head) in S then relations[dep) t 'stem";
14
16
17
else relations(depl < connector';
18
19
foreach (head, dep) in Pp do
20
heads [dep t- head;
(head, dep) or (dep, head) P then relations (deo] < pseudoknot';
21
22
23
else
relations
connector';
25 foreach (head, dep) in lp do heads (dep) + head;
27
relations depp + 'loop';
28
for i from 1 to do if's is in heads then arc i + heads[i]: rell relations []
29
30
31
32
else
33
arcli]
+ O;
34
rel] 'root':
17

---

Published as a conference paper at ICLR 2025
Algorithm 2: Function get.pair for binary tree construction in stem/pseudoknot Structures
Input: Sequence seq of symbols ',,"), and indices idx Output: Paired indices parse pair representing arcs Initialize t- 0, parse pair +- []:
while + -1 and |seq] do
index + i;
// Determine a, b, preindex, change.idx based on seg[index] if seg(index) == then
t seq lindex 1], b + seqlindex);
preindex +- index 1, change idx <- index; else
if seqlindex]
and seglindex
== then
a - seq index - 1), b < seql indli:: preindex +- index change idx index; else
t seq[index]. b seq index + 1]; preindex t index, change idx index +
13
14
dc t -is.connect(a.bb b); i # then
15
Append (idx(change idx), idx(preindex) to parse pair, seqlchange c c;
16
18
Remove seq reqlchange.ids _dxx 1] and idx[change idx - 1]:
19
iiitd
return
Algorithm 3: Function is-connect for Pairing Symbols
Input: Symbols b (can be '(",'), 0, 1) Output:
New symbol c, index adjustment then i = (' then return (2,1) // Keep processing
if
else
if
b == then return (0,0) // Pair formed
else
b = then return (0, 11) // Pair formed, move back
else if
0 then
11
b ) then
return (1,0) // Pair formed
13
else
if 6 = 0 then
15
return (0, -1) // Pair formed, move back
else
b = ( then
17
return (2, // Keep processing
18

---

Published as a conference paper at ICLR 2025
Algorithm 4: Function get.pairrs iss for Generating Loop Pairs
Input:
List of index sequences 1st, last node index last node Output: List of loop pairs result
Initialize result + []:
if 1st is empty or all sublists in lst are empty then
L return result;
foreach sub lut in Ist do
if sub 1st is empty then continue:
if sub 1st is the last sublist and last_node < sub sub_lsr(0) then for i &- 0 to |sub Jsr] do
Append (sub [sti] 1, sub 1s((i)) to result;
10
else
11
for i 4- 1 to |sub Isrj - do
Append (sub Ist(i, sub Asdii 1)) to result; if sublst([ < laat_noot then
12
Append [subJs([-1] + sub [s(-]s(-11]) to result;
14
return result
B EXAMPLE WORKFLOW FOR CONVERTING RNA SECONDARY STRUCTURES INTO DEPENDENCY STRUCTURES
To provide a more intuitive illustration of the RNA secondary structure conversion process. we present example depicted in Figure B1, which demonstrates the transformation through series of steps.
Step 1: Sequence Partitioning involves dividing the RNA sequence into stems (blue), pseudoknots (red), and loops (black) based on its secondary structure.
Step 2: Binary Tree Construction for Stem Sequences entails building binary trees for each stem sequence using the Get_Pair function.
Step 3: Binary Tree Construction for Pseudoknot Sequences similarly constructs binary trees for pseudoknot sequences using the same method. In the example sequence, only one pscudoknot set present. If multiple pseudoknots exist, separate binary trees are created for each set to accurately represent their interactions.
Step 4:
Integration of Binary Trees and Root Selection involves integrating the multiple binary trees by selecting the last node of each tree as the root and connecting the remaining last nodes to this root node, thereby forming a unified hierarchical structure.
Loop Sequence Connections based on root position establishes connections among nu- cleotides within loop sequences based on the position the root node.
Step 5:
Step 6: Comprehensive Structure Integration and labeling consolidates all the constructed struc- tures sures-stems, pseudoknots, and dependency structure for the given RNA sequence.
and assigns appropriate labels, resulting in comprehensive
This workflow ensures that the input RNA sequence, along with its stem and pseudoknot base pairs and the list of unpaired dot indices, is systematically transformed into dependency structure with are connections and labels.
19

---

Published as a conference paper at ICLR 2025
stem base-pairs
stem base-pale pairs
pseudoknot base-pale peee-piirs
10
20
30
Step 1. Sequence Partitioning
last node
(<(E(E
Step Binary Tree Construction for Stem Sequences
last node
[ [
Step Binary Tree Construction for Pseudoknot Sequences
root
Step 4. Integration of Binary Trees and Root Selection
Step 5. Loop Sequence Connections based on root position
stem
stem
pseudoknot
root
loop
loop
connector
loop
loop
connector
Step 6. Comprehensive Structure Integration and labeling
Figure B1: An example illustrating the workflow for converting RNA secondary structures into dependency structures
20

---

Published as a conference paper at ICLR 2025
C TRAINING DETAILS
The code used in DEPfold primarily draws from parts of the SuPar (Zhang et al., 2020a;b) GitHub repository (https: //t/t//gttbb/////// com con/yythancssparseee..ee.oe git). We implemented DEPfold using PyTorch. The architecture uses RoBERTa-base as the encoder within biaffine framework. Specifically, the model uses the first four layers of RoBERTa-base applying mean pooling to generate a 768- 008-dimensional representation. This encoded output is subsequently processed by two dedicated multilayer perceptrons (MLPs).
MLP of edges: Transforms the f68-dimensional input to a 500-dimensional output. MLP of lables: Transforms the 768-dimensional input to a 100-dimensional output.
The outputs from these MLPs are then fed into biaffine attention layers perform the final predic- tions. To mitigate overfitting, we applied a dropout rate of 0.1 to the encoder outputs and a dropout rate of 0.33 to the MLP layers.
For optimization, we used the A optimizer with dual learning rate strategy: the encoder parameters were assigned a learning rate of x 10-5, while the non-encoder parameters were set to 1x10-3. This approach effectively fine-tunes the pretrained encoder while allowing the task-specifer layers to adapt rapidly. The model was trained end-to-end using cross-entropy loss function for both are and relation predictions, with a weight decay factor of 0.01 to further prevent overfitting.
During training, we used a batch size of 32 to maximize GPU use. The training process was capped at 100 epochs, incorporating an early stopping mechanism based on the Fi score on the validation set. Training was terminated when the validation Fi score ceased to improve, ensuring optimal model performance and preventing overfitting. All experiments were conducted on four NVIDIA A A100-40GB GPUs, enabling efficient training and scalability.
D INFERENCE TIME COMPARISON
We evaluated the inference time of various RNA secondary structure prediction methods on the Archivell dataset, as summarized in Table Al. DEPfold without Optimal Tree (OT) decoding, achieved an average inference time of approximately 0.027 seconds per sequence, markedly outperform- ing UFold (0.071 seconds) and LinearFold (0.075 seconds). However, the full version of DEPfold, which incorporates OT, exhibited significant in- crease in inference time to 1.072 seconds per se- quence, making it time-consuming among those evaluated, though still within an acceptable range.
Table Al: Inference time on the ArchivelI dataset
Method
Time Is pseudoknot?
DEPfold w/o OT (Pytorch)
0.027s
Yes
DEPfold (Pytorch)
1.072s
Yes
Ufold (Pytorch)
0.071s
Yes
MXfold2 (Pytorch)
0.477s
No
RNAfold (C)
0.134s
ContraFold (C++)
0.390s
No
Linearfold (C+)
0.075s
No
RNAstructure (C)
4.454s
Yes
This disparity underscores the trade-off between prediction quality and computational efficiency in- troduced by OT, primarily attributable to the increased complexity of parsing pseudoknot structures. Despite the higher inference time, both versions of DEPfold retain the capability handle pseudo- knot structures, a feature absent in many traditional methods such as RNAfold and ContraFold. As result, DEPfold without OT offers maximum inference speed, ideal for rapid predictions. Con- versely, the full DEPfold version, while slower, delivers higher predictive accuracy by effectively modeling complex pseudoknots. This versatility makes DEPfold robust tool for RNA secondary structure prediction, allowing users to balance speed and accuracy according to their research needs.
E VISUALIZATION
To intuitively demonstrate DEPfold's prediction performance, we visualized the predicted structures of three representative RNA sequences using ViennaRNA (Lorenz et al., 201 1a). As illustrated in Figure E2, these sequences correspond to short RNA. a medium-length RNA without pseudoknots, and a long RNA with pseudoknots, respectively. DEPfold's predicted results are highly consistent with the ground truth structure. In contrast, the energy-base method ContraFold failed to effectively
21

---

Published as a conference paper at ICLR 2025
predict this secondary structure. Although UFold achieved higher F₁ score than other baseline methods, its predicted results visually differed significantly from the ground truth and erroneously predicted pseudoknots that should not exist. DEPfold accurately captured these complex structural features.
DEPiold
0.857)
ContraFold =..)
True Structure
DEPfold (F, 1.0)
UFold (P1 0.817)
ContraFold (P. = 0.615)
True Structure
DEPiold (F: 1.0)
UFold (Fi 0.919)
ContraFFold (F; 0.695)
Figure E2: Comparison of RNA secondary structure predictions.
22


Reviews:
[{"review_id": "uWWpsDwzuw", "reviewer": "Reviewer_ubS6", "summary": "After the author response, I appreciate the efforts that the authors made to make the paper more readable. I especially found the more explicit inclusion of pseudoknots and the workflow in Figure B1 quite helpful. I thus adjusted my score from a 5 to a 6.\n\n----\n\nThe paper presents a novel and interesting approach for RNA secondary structure prediction. The authors frame this problem as dependency parsing in NLP. This first involves mapping the RNA structure to a dependency tree (this can be challenging because of pseudo-knots that result in non-projectivity).\n\nThe authors then use a neural network biaffine parser (based on Dozat and Manning - 2016) for this task which predicts the pairwise edges + labels. The authors then use either Eisener algorithm (for projective structures or Kirchoff's Matrix-Tree Theorem (for non-projective structure) to find the optimal tree.\n\nExperiments show that the authors achieve strong performance on multiple datasets.", "questions": "I have many questions about the RNA secondary structure and the transformation to dependency trees as described above in Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper tackles an important problem.\n\n-The method is interesting and novel. \n\n-Empirical results are strong.", "weaknesses": "Overall I found the description of the RNA secondary structure and how to transform it into a dependency tree to be confusing and non-rigorous.\n\n-There is brief notation given in Section 2 and it states how a typical RNA secondary structure is composed of linear sequences (dots) and then different types of brackets. However, this is all quite vague and non-rigorous.\n\n It would be great to see an example of each type of label and how it is represented in this notation (e.g. stems, loops, pseudoknots etc.) I feel these concepts are not rigorously defined i.e. despite the importance of pseudo-knots I do not see a clear example/definition in the paper. \n\n-The description of 3.1 (transformation of RNA structures to dependency) would be clearer with a running example that shows what happens at each step. Moreover, I am confused about whether the transformation is a 1:1 mapping. Is it provable the case that for any RNA secondary structure it maps to a unique dependency tree and vice versa? Or is this a heuristic.", "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": "", "extra_scores": {}}, {"review_id": "vyERa7mMe9", "reviewer": "Reviewer_XEMD", "summary": "This paper introduces a new NLP dependency parsing-inspired algorithm for RNA secondary structure prediction, DEPfold. The paper's results suggest that DEPfold performs much better than other methods on within-family and cross-family RNA datasets, getting near perfect results on several datasets. \n\nAs a \"positionality statement\" for this review, I'll mention that I'm expert in NLP dependency parsing, and assume that I was chosen to review for that reason, but I have little understanding of the biology and am generally not familiar with the test sets and performance of other methods in the RNA structure prediction domain.", "questions": "This largely duplicates what I put in \"weaknesses\". \n\n- Lines 165-187: While a projective dependency diagram is isomorphic to a certain kind of binary tree (a single-level X' CFG), a pure dependency grammar presentation would not normally evoke tree structure. Is it necessary? I would guess not and that the algorithm could be described directly in terms of creating dependency arcs. Things might even be clearer that way, given what is in Fig. 1.\n\n- Tree completion (lines 210-215): AFAICS, g is never defined. Is it the root node, or the \"grandparent\" (parent of the head node)?\n\n- Most importantly, I don't think the section 3.1 presentation of the algorithm even attempts to explain rigorously the treatment of pseudoknots. They're mentioned, as on line 223, but what is the details of their dependency grammar representation. Are they just treated as some kind of not fully labeled clump, as perhaps suggested by the notation introduced for P_i on line 159? I know vaguely that there is an older thread of work crossing from NLP to bioinformatics arguing that giving powerful enough grammars to describe pseudoknots requires more powerful \"mildly context sensitive\" grammars like tree-adjoining grammar, beyond the power of dependency grammars (e.g., https://academic.oup.com/bioinformatics/article/21/11/2611/294713 ). Is that still true? Is having a non-projective dependency tree grammar sufficient?\n\n- Can the post-processing (line 291ff) be incorporated into the decoding algorithm with some appropriate constraint?\n\n- Clarify the relation between this algorithm and E2Efold (from ICLR 2020)\n\n- Clarify the relation and what you're citing as results between E2Efold and E2Efold-3D\n\n- Clarify whether there are results from 2023 or 2024 that should be included as comparisons and how the methods and results of algorithms from these years relate to yours.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The approach to treating RNA secondary structure prediction via NLP dependency parsing, and largely using the biaffine dependency parsing algorithm of Dozat and Manning (2016) seems largely original.\n- The results of the paper, as presented, are very strong. If this all checks out, the method provides a new much more accurate RNA secondary structure prediction and this would be quite significant", "weaknesses": "- I feel that the presentation of the paper should have been clearer. It might have been better to move Fig. 1 to section 3 and to have referred to it when presenting the algorithm. The algorithm for conversion to dependency trees is presented somewhat informally. Something more precise would have been better. Among other things: (i) The algorithm is presented with reference to \"bracket-dot notation\" for RNA secondary structure (lines 126-136) but this is never rigorously defined. This notation may be well known in bioinformatics, but not to me. If this is the starting point of the algorithm, it would minimally be really useful to have shown the example sequence in Fig. 1 in bracket-dot notation. Indeed, it seems like the two subdiagrams in the top right of Figure 1 do not add much to understanding and at least one of them could have been deleted. Lines 165-187: While a projective dependency diagram is isomorphic to a certain kind of binary tree (a single-level X' CFG), a pure dependency grammar presentation would not normally evoke tree structure. Is it necessary? I would guess not and that the algorithm could be described directly in terms of creating dependency arcs. Things might even be clearer that way, given what is in Fig. 1. Tree completion (lines 210-215): AFAICS, g is never defined. Is it the root node, or the \"grandparent\" (parent of the head node)? Most importantly, I don't think the section 3.1 presentation of the algorithm even attempts to explain rigorously the treatment of pseudoknots. They're mentioned, as on line 223, but what is the details of their dependency grammar representation. Are they just treated as some kind of not fully labeled clump, as perhaps suggested by the notation introduced for P_i on line 159? I know vaguely that there is an older thread of work crossing from NLP to bioinformatics arguing that giving powerful enough grammars to describe pseudoknots requires more powerful \"mildly context sensitive\" grammars like tree-adjoining grammar, beyond the power of dependency grammars (e.g., https://academic.oup.com/bioinformatics/article/21/11/2611/294713 ). Is that still true? Is having a non-projective dependency tree grammar sufficient? This paper left me no wiser. Finally, I wondered whether the post-processing (line 291ff) couldn't have been incorporated into the decoding algorithm with some appropriate constraint.\n\n - Results: I'm not really the person to judge the appropriateness and completeness of all the results presented, but to the extent that I tried to look other things up on the web for a few minutes, I seemed to be left with more questions than answers. The algorithm referred to in this paper as \"E2Efold\" is referred to by the authors of the cited reference as E2Efold-3D. There is actually a different algorithm by different authors called E2Efold that appear at ICLR in 2020 (https://openreview.net/forum?id=S1eALyrYDH) and which itself used an algorithm \"close to\" biaffine dependency parsing. At least it is mentioned as related work. How does this paper refer to that paper. This paper is not in the references, and there is no explicit comparison in related work. But then the RNAStrAlign results in Table 2 seem to be the results of E2Efold not E2Efold-3D. They're identical to the ones in the E2Efold paper. Somehow this isn't giving me confidence.... I don't really know what are the best datasets or perceived best methods in this domain, but it then also seems like there are other recent methods claiming good results, such as RNAformer (https://icml-compbio.github.io/2023/papers/WCBICML2023_paper43.pdf) or DEBFold (https://pubs.acs.org/doi/10.1021/acs.jcim.4c00458) which aren't mentioned in the references here. Am I getting the best most up-to-date comparisons? It's not clear to me. The latest, best algorithm compared to is UFold from 2022, but there are clearly papers on this topic from 2023 and 2024, but it's not trivial for me to compare since there seem to be a lot of different datasets around, etc.", "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": "", "extra_scores": {}}, {"review_id": "XSk3YsPqDw", "reviewer": "Reviewer_SsoD", "summary": "The paper proposes to use deep dependency parsing technique to predict RNA secondary structures. The paper shows how RNA structures can be mapped to dependency structures and via verse. Then now, the problem of predicting RNA structures is casted to dependency parsing, a classical task in NLP. The paper uses the Dozat & Manning 2016 parsing method, in which nucleotides are represented by RNA-fm or Roberta contextual embeddings. \n\nThe paper shows experiments with popular datasets, RNAStrAlign, ArchiveII, and bpRNA-*. The proposed method substantially outperforms strong baselines (UFold, MXfold2, E2Efold). The paper also presents analyses showing a surprising result that Roberta contexutal embeddings actually are effective for this problem.", "questions": "* Did the authors try \"undirected\" dependency structures? if yes, what are the performance?\n* Because a RNA sequence can be very long (>1500), could the authors explain how to use Roberta effectively?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper showcases a very interesting application of NLP (more specifically, dependency parsing) to biology. The authors propose an effective way to translate the RNA structure prediction to dependency parsing, connecting the two challenges. The experiment results are evidence for the effectiveness of the proposed method.", "weaknesses": "The paper only mentions methods and work from 2022 backward, and only one published in 2024. However, I found several publications in 2023, such as [1,2,3]. I thus question about the up-to-date information in the paper. \n\n(I'm willing to raise my overall score if the authors can provide comparison with the most up-to-date work in the literature).  \n\n\n1. Chen, CC., Chan, YM. REDfold: accurate RNA secondary structure prediction using residual encoder-decoder network. BMC Bioinformatics 24, 122 (2023). https://doi.org/10.1186/s12859-023-05238-8\n2. Wang, W., Feng, C., Han, R. et al. trRosettaRNA: automated prediction of RNA 3D structure with transformer network. Nat Commun 14, 7266 (2023). https://doi.org/10.1038/s41467-023-42528-4\n3. Tzu-Hsien Yang. DEBFold: Computational Identification of RNA Secondary Structures for Sequences across Structural Families Using Deep Learning. Journal of Chemical Information and Modeling 2024 64 (9), 3756-3766. DOI: 10.1021/acs.jcim.4c00458", "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": "", "extra_scores": {}}, {"review_id": "vO9OOqw1Wh", "reviewer": "Reviewer_vMAF", "summary": "This paper introduces a novel method named DEPfold, which reframes the prediction of RNA secondary structures as a dependency parsing task. \n\nDuring training, given an RNA sequence, DEPfold constructs a dependency tree from the sequence using three types of arcs/labels: stem, pseudoknot, and connector. DEPfold then employs Biaffine parsers to learn these trees. \nDuring inference, DEPfold first predicts the tree from the raw sequence and subsequently recovers the internal secondary structures through several post-processing steps.\n\nThe authors have experimented with various base models, including RNAfm and RoBERTa, and different learning strategies such as fine-tuning and freezing pretrained models. They found that DEPfold outperforms existing models across multiple datasets in the field of RNA structure prediction.", "questions": "* > Pseudoknots, we find, are equivalent to adding a certain level of non-projectivity to the dependency parsing model.\n\nI can't build the connection between the non-projectivity and Pseudoknots. Can the authors give me more details?\n\n* There are some length limitatations for RoBETa that make it hard to extrapolate to longer sequences, how did you handle RNA sequence with thoundands of nucleotides?\n\n* I'm very curious about the effectiveness of extending DEPfold to structured learning algorithms like TreeCRF, which has been proven very useful in the field of dependency Parsing [1,2,3]\n\n* How about the speed of optimal tree decoding. Did you use any parallelized implementations of MST/Eisner in [torchstruct](https://github.com/harvardnlp/pytorch-struct) or [SuPar](https://github.com/yzhangcs/parser) for acceleration?\n\n[1] Neural Probabilistic Model for Non-projective MST Parsing  \n[2] Efficient Second-Order TreeCRF for Neural Dependency Parsing  \n[3] Headed-Span-Based Projective Dependency Parsing", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is a novel work, which, to my knowledge, is the first to frame RNA structure prediction as dependency parsing. \n\nI am excited to see that the wisdom from traditional NLP parsing tasks can still play important roles in a wider range of structured prediction tasks, such as RNA secondary structures.\nDEPfold is built on the biaffine parser, a widely known neural-based dependency parser, and demonstrates very strong performance by leveraging the power of pretrained masked language models like RoBERTa.\n\nI am very optimistic about further improving the performance of DEPfold by scaling it to larger model sizes and larger datasets.\nAlso, beyond the scope of this work, I believe DEPfold opens the door for utilizing some other parsing methods like stack-pointer [1] networks or modeling RNA structures via context-free grammars [2].\n\n[1] Stack-Pointer Networks for Dependency Parsing  \n[2] Strongly Incremental Constituency Parsing with Graph Neural Networks", "weaknesses": "* I suggest that the authors elaborate further on the definitions of RNA structures. For instance, a small figure illustrating the differences between stem and pseudoknot would be helpful. As someone who is not an expert in RNA structure prediction, I find it challenging to fully understand the details of the paper without resorting to external resources like Wikipedia or search engines.\n* Line 284, Decoding: The Matrix-Tree Theorem is used for calculating the normalization term of the probabilities of non-projective trees. For decoding, one should use O(N^2) MST algorithms to decode non-projective trees.\n* Lines 126-129: It would be beneficial if the authors could provide examples to demonstrate the bracketing structures.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)