# Self-Playing RNA Inverse Folding

Stephen Obonyo, Nicolas Jouandeau, Dickson Owuor

► To cite this version:

Stephen Obonyo, Nicolas Jouandeau, Dickson Owuor. Self-Playing RNA Inverse Folding. SN Computer Science, 2024, 5, 10.1007/s42979-024-02659-x. http://dx.doi.org/10.3389/fscs.2024.00265

HAL Id: hal-05487894

https://hal.science/hal-05487894v1

Submitted on 27 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Self Playing RNA Inverse Folding

Stephen Obonyo

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Paris 8 University, France
Strathmore University, Kenya

Nicolas Jouandeau

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

Paris 8 University, France

Dickson Owuor

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

Strathmore University, Kenya

## Abstract

Self Play (SP) is a method in Reinforcement Learning where an agent learns by playing against itself until state-action or state-value evaluation functions converge. The SP method has recorded state of the art results in playing different computer games including Chess, Go and Othello. In this paper, we propose a SP based agent dubbed Self Player RNA (SPRNA) applied to Ribonucleic acid (RNA) Inverse Folding where a sequence is designed to match a given target structure. We also present an encoding scheme for both the known and unknown RNA Inverse Folding states and the corresponding Gym Environment. We show that the optimal policies in RNA Inverse Folding can be learned by just performing a one-step look-ahead state-value evaluation using a deep value network. SPRNA learns to design RNA sequences recording very competitive results across different RNA sequence design benchmark datasets.

**2012 ACM Subject Classification** Computing methodologies→Machine learning→Machine learning algorithms→Dynamic programming for Markov decision processes→Policy iteration

**Keywords and phrases** Self Playing, RNA Inverse Folding, Reinforcement Learning, Computational Biology

**Digital Object Identifier** 10.4230/LIPIcs.CVIT.2016.23

**Acknowledgements** We would wish to thank Strathmore University and the French Embassy in Kenya for providing an environment which enabled this research work.

## 1 Introduction

Ribonucleic Acid (RNA) is a molecule which plays a key role in protein synthesis and gene expression in the human body. Generally, it is composed of a sequence of bases (or nucleotides) namely Adenine (A), Uracil (U), Guanine (G) and Cytosine (C). The success of designing RNA sequences which fold according to a defined target; RNA Inverse Folding, holds great potential for the design of functional RNA molecules *in vitro*, biotechnology, synthetic biology, design of non-coding RNA molecules, drug design and healthcare [12, 9, 13, 11].

RNA molecules have primary, secondary and tertiary structures. The primary structure is composed of a sequence of nucleotides while the secondary structure is composed of bulges, internal loops and hairpins. Tertiary structure on the other hand is generally composed of the 3-D representation of the RNA building units. Due to base pairing properties (Watson-Crick base pairs), the bases A-U and G-C often bond in secondary structures. G-U pairing is also exhibited in certain secondary RNA structures and pseudoknotted RNA molecules; albeit not common. The pairing dictates the functional effectiveness of the RNA molecule [21].

RNA Inverse Folding is an active research problem in Bioinformatics. It involves designing a sequence which can fold to match a predefined structure. As shown in Figure 1, Figure 1(a) is the target structure, Figure 1(b) the designed sequence and Figure 1(c) the predicted structure. The target structure is given in Dot-bracket notation where the matching parenthesis ( )

<figure><img src="image_8.png" /></figure>

© Stephen Obonyo, Nicolas Jouandeau and Dickson Owuor;

licensed under Creative Commons License CC-BY 4.0

42nd Conference on Very Important Topics (CVIT 2016).

Editors: John Q. Open and Joan R. Access; Article No. 23; pp. 23:1–23:13

<figure><img src="image_9.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
23:2 Self Playing RNA Inverse Folding

<figure><img src="image_10.png" /><figcaption>■ **Figure 1** Target structure (a), designed sequence (b) and predicted structure (c). The nucleotides are marked with numbers 1 to 16. In (a), the locations (1, 16), (2, 15), (3, 14), (4, 13) and (5, 12) are paired hence can be simultaneously assigned any value from {GC, CG, AU, UA, GU, UG} while locations 6 to 11 are unpaired thus can be assigned a value from {A, U, C, G}. In (b) location (1, 16) is assigned C and G simultaneously, similarly, location (3, 14) is assigned U and A respectively. The same concept applies to positions (2, 15), (3, 14), (4, 13) and (5, 12). In contrast, locations 6 - 11 are not paired and thus have been assigned value from {A, U, C, G}. The designed sequence is folded using Vienna package [13] resulting in a predicted structure (c). The Hamming loss between the predicted structure and target structure is 0 thus the designed sequence folds to match the target structure (a).</figcaption></figure>

corresponds to the paired bases whereas the • represents the unpaired bases (single sites).
Figure 1 shows a successful RNA Inverse Folding Design as the target structure is similar
the predicted structure.

The quality of the designed sequence can be measured using three different methods.
Firstly, by computing the Hamming loss between target and predicted structure; a Hamming
loss of 0.0 means that the designed sequence folds perfectly according to the target structure.
Secondly, by calculating the Minimum Free Energy (MFE) of the predicted sequence; the
RNA molecules with lower MFE values tend to be more stable and thus more effectively
functional [36]. Thirdly, by calculating the GC content of the designed sequence; this is the
proportion of G's and C's. Generally, the desired GC content value ranges between 50 to 60
[25].

In this research, we propose a Self Play (SP) Reinforcement Learning based agent called SPRNA which can learn to excel in RNA Inverse Folding. According to [2], an SP agent learns to play against itself without human intervention over several simulations. The SP concept has been successfully applied to Computer Game Playing and Game Intelligence [6, 31, 32, 3]

In Reinforcement Learning (RL), an agent is tasked with learning by exploring and exploiting and taking actions leading to an optimal future return. The reward in RL is characteristically scarce and time delayed with states assuming non i.i.d (independent and identically distributed). This is in contrast to supervised learning where there is an immediate reward and states (training examples) assuming i.i.d.

Any RL problem can be formally expressed as a Markov Decision Process (MDP)
{S, A, R, P, R, γ}; where S is a finite set of states, A set of possible actions, P the state
transition model, R the reward and γ the discount factor [34]. If P and R are known then
solving the MDP is tractable through iterative or dynamic programming methods. Modelling
P and R, however, for most RL problems can be resource-intensive and intractable leading to
the sampling of the environment through methods such as Monte Carlo (MC) and Temporal
Difference (TD) Learning.

The return, *G*, obtained from MC or TD sampling can then be used to estimate the
reward (*R*) and the state transition function (*P*) [34]. In MC, the agent learns by directly
sampling the environment and estimating *R* by computing the expectation of the return,
$\mathbb{E}[G]$, obtained from the environment when an episode terminates. $\mathbb{E}[G]$ then informs the $\mathcal{P}$. Contrary to MC which learns from the complete episodes, TD can learn from incomplete episodes by performing a *n*-step look-ahead.

Classically in RL, the transition function $\mathcal{P}$ is generally represented as a state-action table for small and tractable MDPs. However, effectively modelling MDPs with very large state-action values can be daunting, complex and computationally expensive, thus, lately, Deep Learning (DL) models have been introduced to model the state-action function as demonstrated by [23]. Representation of the state-action function by a DL is plausible due to two key reasons; (i) big data from the agent's environment enables better generalization and (ii) development of novel DL techniques and architectures [19, 18, 33, 14, 39, 12, 37].

A DL model, $f_\theta$, can be used to represent state-value and the state-action evaluation functions e.g. $f_\theta: s_t \to v_\pi(s_t)$ and $f_\theta: s_t \to q_\pi(s_t, a_t)$ respectively [23, 28]. The ability to model $v_\pi(s_t)$ and $q_\pi(s_t, a_t)$ with $f_\theta$ is the core of Deep Reinforcement Learning (Deep RL). Deep RL and SP methods have been used to design several state of the art game playing agents such as Alpha Go [30] and Alpha Zero [32].

Alpha Go recorded state of the art results by using two DL models; one for value evaluation of the board position ($s_t$) and the other for policy evaluation to select the best action to maximize the expected future reward. The Alpha Go DL evaluation models were trained in a supervised learning fashion on expert knowledge moves and also through SP. By contrast and extension, Alpha Zero DL evaluation models were not trained on the expert knowledge moves. The value network was trained through SP while minimizing the Mean Squared Error (MSE) of the target (reward) values; +1 win and -1 loss. The policy network on the other hand was trained through SP and tree search. The Alpha Zero RL agent recorded superhuman results outperforming the predecessor (Alpha Go).

The SP in Alpha Go and Alpha Zero is characterized by simulation of several game episodes which the RL agent then plays against itself. When an episode ends in SP, all the observed states {$s_0, s_1, s_2, ..., s_n$} are assigned a scalar reward {$(s_0, r), (s_1, r), (s_2, r), ..., (s_n, r)$} where $r \in \{+1, -1\}$ (win or loss respectively). The value and policy networks are then trained in a supervised learning manner on the collected samples. The success of SP has since been extended to other computer games [3, 7] and this trend excites its application to other research areas such as Bioinformatics where problems such as RNA Inverse Folding and molecular design share similar problem structures to computer games.

SPRNA interacts with the RNA environment to design a sequence matching a given target structure. Given a state, $s_t$, and a set of valid actions, SPRNA performs a one-step look-ahead evaluation using the value network (DL model) which then informs the policy. In contrast to the existing SP methods which are characterized by both the value and policy networks, SPRNA has a value network only.

SPRNA can generate RNA sequences which fold to match a given target structure with desirable Minimum Free Energy (MFE) and the GC content while recording competitive and promising results on different benchmark datasets. In addition, we also present an RNA encoding scheme for both the known and unknown RNA Inverse Folding states and the corresponding design Environment (Gym) which exposes the problem to a wide variety of existing RL and SP algorithms workhouse.

The next sections of this paper are organized as follows; section 2 presents Related Work, section 3 contains a summary of our contribution, section 4 outlines the methods employed in this research, and section 5 covers the results which were obtained during the study including the comparative analysis, section 6 contains discussion of the obtained results followed by conclusion and future research in section 7.
## 2 Related Work

Several RNA Inverse Folding models which optimize the Hamming loss Minimum Free Energy (MFE) and the GC content have been proposed by different researchers. These models are majorly inspired by problem-solving methods including brute force, genetic algorithms, dynamic programming, evolutionary search, constraint programming, tree search, RL, general search and thermodynamics.

A Monte Carlo Tree Search algorithm proposed by [38] jointly optimized the GC content and Hamming loss recording remarkable results across multiple datasets. The model included a local search which generated a candidate solution by randomly creating the missing pairings and breaking illegal ones in the predicted structure. Another Monte Carlo Tree Search model was proposed by [8]. Notably, in [8] the authors presented a unique coding of the moves while concurrently optimizing the GC content and Hamming loss with a Generalized Nested Policy Adaptation (GNPA) framework.

INFO-RNA, a dynamic programming based model proposed by [5] was optimized with local search to get the candidate sequences matching the target while also constraining them to the given MFE range. The work is an extension of [13] which was one of the early RNA Inverse Folding methods.

RNA-SSD is another RNA Inverse Folding model proposed by [1]. The model also performs minimization of the structural difference (Hamming loss) which is reinforced by a recursive stochastic local search. RNA-SSD approach is similar to [20] but the local search is replaced by the global search.

The AntaRNA model by [16] proposed a different approach from the aforementioned studies. They presented an Ant Colony based model to optimize both the structural difference (Hamming loss) constrained with the GC content. The AntaRNA design was adopted and extended by [15] for the RNA Inverse Folding on more complicated structures (the pseudoknots).

The RNA Inverse Folding approach proposed by [10] was based on an evolutionary algorithm dubbed ERD. The model design was unique as it allowed the user to specify the MFE constraints of the designed sequence. Apart from the MFE constraints the model also allowed for the specification of fixed base locations over the sequence design iterations.

The RNAiFOLD model by [11] also adopted a unique approach. They employed constraint programming where a wider local search was constrained with specified molecule properties such as the GC content and the RNA-RNA intramolecular interactions. As argued by the authors the model was more suitable for longer RNA sequence design.

Modena proposed by [35] is a genetic-based algorithm characterized as multi-objective. It explored the weak Pareto solutions in the space of two objective functions; the Hamming loss between the target and predicted structure and the MFE of the designed sequence. In addition, the sequence design was constrained by a set of user-defined rules such as the weights of bases A, U, G and C. A comparative study of Modena with other models such RNAInverse, INFO-RNA, and RNA-SSD showed remarkable variation in performance.

Another RNA Inverse Folding algorithm which adopted a unique approach is Learna [26]. It is a policy gradient model (a model free based) which learned to design RNA sequences by minimizing the Hamming loss with a local improvement search constrained by a threshold given that the predicted structure does not match the target structure. It directly learned to optimize the valid actions A using PPO [29]. Instead of modelling the evaluation function, Learna directly learns the best action to take given the state $s_t$.

While most of the reviewed RNA Inverse Folding solutions have largely exploited general
search, Tree Search, evolutionary algorithms, genetic algorithms and dynamic programming, other methods such as [27, 17, 22, 36] have presented the fundamental physics-first methods. Another key feature attributed to the existing methods is that they are primarily reinforced by expert knowledge such as the weight distributions (Table 1) and known molecular and chemical properties.

<table><caption>**Table 1** General base weight distributions</caption><thead><tr><th>Sites</th><th>Base</th><th>Distribution</th></tr></thead><tbody><tr><td rowspan="4">unpaired bases</td><td>A</td><td>93%</td></tr><tr><td>G</td><td>5%</td></tr><tr><td>C</td><td>1%</td></tr><tr><td>U</td><td>1%</td></tr><tr><td rowspan="3">paired bases</td><td>GC/CG</td><td>60%</td></tr><tr><td>AU/UA</td><td>33%</td></tr><tr><td>GU/UG</td><td>7%</td></tr></tbody></table>

# 3 Contributions

We present our contributions as follows:

1. Self Play RL Inverse Folding agent - We present an RL Inverse Folding agent called SPRNA. As opposed to the current SP agents which learn based on policy and value networks, SPRNA learns to design RNA sequences matching a given target structure by evaluating state $s_t$ using the value network only. Given a set of valid actions at time $t$, SPRNA performs a one-step look-ahead state evaluation using a value network to select the best action.

2. Encoding scheme - We present a new encoding scheme used by SPRNA for both the known and unknown RNA Inverse Folding states. It allows the evaluation of RNA Inverse Folding states even before the end of an episode. Besides usage by SPRNA, the scheme is extensible to other Computational Biology problems.

3. RNA Inverse Folding Design environment - We present the RNA Gym Design Environment. Gym [4] is an open source RL environment design tool. While the environment is common for gaming applications, we show that the existing interface can also support RNA Inverse Folding environment. The environment is based on the encoding scheme in (2) above and allows for the exposure of the RNA Inverse Folding problem to the classical RL algorithms present in Gym and its compatible programming interfaces (APIs). This exposure enables research extension and inspires the development of new methods for RNA Inverse Folding.

# 4 Methods

This section covers the design of SPRNA and its state encoding. The dataset, SPRNA playout and evaluation algorithms, the value network design and training are also presented in this section.
## 4.1 SPRNA Design

The SPRNA agent requires no expert knowledge to learn except the rules of the RNA Inverse Folding. Given a set of valid actions and the coded state $s_t$, a one-step look-ahead state evaluation is performed by the value network on the resulting coded states and the best action selected.

If the current move position is a paired, then the best action is obtained by performing a one-step look-ahead evaluation over the valid action space constrained by Equation 1. For example given a target structure •(••)•, the move positions are defined by {1, (2, 5), 3, 4, 6}. Assuming that the state value, $s_t = A(••)•$, if after one time step, $s_{t+1}$, the current move position is (2, 5) and the value network returns GC as the best action then base G and C are assigned simultaneously resulting in $s_{t+1} = AG••C•$ or $s_{t+1} = AA••U•$ in case the best move returned by the value network is AU.

The SPRNA RL constraints - {$S, A, R, P, R, \gamma$} - is defined as follows;

- **Action space (A):** Set of valid actions is defined by Equation 1. If the current move location is paired the valid actions are also paired or unpaired otherwise.

$$A = \begin{cases} \{GC, CG, AU, UA, GU, UG\} & \text{paired}(\text{move\_location}) \\ \{A, U, C, G\} & \text{otherwise} \end{cases} \qquad (1)$$

- **State space (S):** Every symbol in state value is coded using the binary code sequences shown in Table 2 and the resulting values are concatenated. The state space of sequence $\mathcal{L}$ can therefore be defined as $\bigcup_{i=1}^{|\mathcal{L}|} C_i$ where $C_i$ any binary code of a given state value symbol and $i$ is the the base/nucleotide assignment location and $|\mathcal{L}|$ the length of the RNA sequence to be designed.

- **Reward (R):** The immediate reward in every non-terminal state is 0. In the terminal state (all paired and unpaired locations assigned) the reward is 1 if the Hamming loss between the predicted and target structure is 0 and -1 otherwise. This is defined by Equation 2.

$$\mathcal{R} = \begin{cases} +1 & \text{hamming(target, predicted)} = 0 \\ -1 & \text{otherwise} \end{cases} \qquad (2)$$

- **Transition Function (P):** The value of each valid action at time step $t$ is predicted by the value network ($f_\theta$) shown in Figure 2. It is stochastic (decayed $\epsilon$-greedy; to encourage exploration) during training time and deterministic during evaluation time.

Every coded state value in each episode is saved for training the value network. When an episode is over, the collected samples are assigned a target value according to the reward constraint shown in Equation 2. The value network was trained by minimizing the Mean Squared Loss (MSE) between the prediction and the target as shown in Equation 3 where $N$ is the batch size. After multiple iterations, SPRNA eventually starts to learn the patterns over the state spaces which leads to correct folds. This is a key fundamental principle in SP.

$$\mathcal{L} = \sqrt{\left(\frac{1}{N}\right) \sum_{i=1}^{N} (f_{\theta}(s_t) - y)^2} \qquad (3)$$

We define a sliding window parameter, $W$, as the feature set parameter specified as the size of overlapping sequence of move locations e.g in the •(••)• example, if move locations
are defined by the set $\{(1), (2, 5), (4), (3), (6)\}$ then $W = 1$. If $W=2$, then the set defining move locations becomes $\{(1, (2, 5)), ((2, 5), 4), (4, 3), (3, 6)\}$ and $\{(1, (2, 5), 4), ((2, 5), 4), (4, 3, 6)\}$ when $W=3$. We experimented with $W$ of different sizes.

The SPRNA episodes were played by Algorithm 1 while the states were evaluated by Algorithm 2.

<table><caption>Table 2 Binary Coding Schemes</caption><thead><tr><th>state value</th><th>character</th><th>code</th></tr></thead><tbody><tr><td rowspan="4">known unpaired</td><td>A</td><td>0000</td></tr><tr><td>G</td><td>0001</td></tr><tr><td>U</td><td>0001</td></tr><tr><td>C</td><td>0011</td></tr><tr><td rowspan="6">known paired</td><td>GC</td><td>0100</td></tr><tr><td>CG</td><td>0111</td></tr><tr><td>AU</td><td>0101</td></tr><tr><td>UA</td><td>1000</td></tr><tr><td>UG</td><td>1001</td></tr><tr><td>GU</td><td>0110</td></tr><tr><td rowspan="2">unknowns</td><td>( )</td><td>1010</td></tr><tr><td>•</td><td>1011</td></tr></tbody></table>

Algorithm 1 SPRNA batch layout. $\mathcal{B}$ is the target batch RNA structures, $\mathcal{P} = \{\text{GC}, \text{CG}, \text{AU}, \text{UA}, \text{GU}, \text{UG}\}$ the paired actions and $\mathcal{U} = \{\text{A}, \text{U}, \text{C}, \text{G}\}$ the unpaired actions. The state-value evaluation (line 8 & 9) is performed through a one-step look-ahead using the value network given the set of current valid actions ($\mathcal{P}$ or $\mathcal{U}$). The `local_search()` function (line 11) improves the designed sequence if the Hamming loss between the predicted and target structure is greater than 0. The function is similar to the Local improvement step proposed by [26]

1 function SPRNA_BatchPlayout($\mathcal{D}$, $\mathcal{P}$, $\mathcal{U}$):
2 &nbsp;&nbsp; $\mathcal{R} \leftarrow \emptyset$;
3 &nbsp;&nbsp; for seq $\in \mathcal{B}$ do
4 &nbsp;&nbsp;&nbsp;&nbsp; state $\leftarrow \text{RNA\_GymEnv}(seq)$;
5 &nbsp;&nbsp;&nbsp;&nbsp; sites $\leftarrow \text{state.available\_sites}(\cdot)$;
6 &nbsp;&nbsp;&nbsp;&nbsp; sites $\leftarrow \text{state shuffling sites}(\cdot)$;
7 &nbsp;&nbsp;&nbsp;&nbsp; for each $s \in \text{sites}$ do
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if pair(s) then best $\leftarrow$ value(state, $\mathcal{P}$);
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else best $\leftarrow$ value(state, $\mathcal{U}$);
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; state $\leftarrow$ state. apply\_move(best);
11 &nbsp;&nbsp;&nbsp;&nbsp; if state. hamming\_loss() > 0 then
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; state. designed\_seq $\leftarrow$ local\_search(state. designed\_seq, seq);
13 &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{R} \leftarrow \mathcal{R} \cup \{\text{state}\}$;
14 &nbsp;&nbsp; return $\mathcal{R}$;
## 23:8 Self Playing RNA Inverse Folding

<figure><img src="image_11.png" /></figure>

■ **Figure 2** The value network. It accepts the coded state value ($s_t$) as the input and computes the value of that state. The network is composed of Convolutional Layers (CONV), Rectified Linear Units (ReLU), Batch Normalization (BN), Dropout ($p = 0.5$), Adaptive Pooling (AD. Pool) and Fully Connected layers (FC). The tanh activation was used in the output layer. CONV1 is the first Convolution while BN3 is the third Batch Normalization. Each layer(s) input/output value(s) have also been shown e.g. in CONV1 layer the numbers 1, 64 correspond to the input channels and output channels respectively while in layer BN3 the number 256 corresponds to the size of the input volume. In FC layers, the numbers correspond to the size of input and output neurons. Adaptive Pool allowed playing variable sized state episodes.

■ **Algorithm 2** State evaluation algorithm. The value network, $f_\theta$, accepts state value $s_t$, codes it then returns the best action $a \in \mathcal{P}$ or $a \in \mathcal{U}$. The best action is returned over all the actions using a decaying $\epsilon$-greedy fashion. The decaying $\epsilon$-greedy methods allows for exploration during the early training iterations. During evaluation, the decaying $\epsilon$-greedy is replaced by the argmax function

1 function value(state, A):
2     v ← ∅;
3     for each a ∈ A do
4         state ← state.apply_move(a);
5         input ← state.code();
6         v(state, a) ← f_θ(input);
7         state ← state.undo_move(a);
8     return decaying_egreedy(v, A);

## 4.2 The Value Network

The value network, $f_\theta$, is a Convolutional Neural Network (CNN) composed of 14 layers. The architecture shown in Figure 2 is inspired by AlexNet [18] design. However, $f_\theta$ has BatchNorm, Adaptive Pool and Softmax Layers which are not in AlexNet. It is also important to note that while AlexNet was composed of 3 fully connected layers, $f_\theta$ has 4. The kernel size in the Convolutional layers is also different between the two architectures. The value network was trained at the end of one full pass over the target RNA batch sequences for 30 epochs with a batch size of 64 with Adam optimizer ($\alpha=0.0001$). All the experiments were run on an NVIDIA Quadro T2000 GPU card.

## 4.3 Dataset

SPRNA was trained using Dataset E while evaluated on Datasets A, B, C and D (validation set). During training, each batch $\mathcal{B}$ was composed of 100 sampled target structures was used
to create the environment and train the agent. The attribute of each dataset has been shown in Table 3.

<table><caption>**Table 3** SPRNA Train & Test Datasets</caption><thead><tr><th>ID</th><th>Total Target Structures</th><th>Source</th><th>Train/validation</th></tr></thead><tbody><tr><td>Dataset A</td><td>63</td><td>[16]</td><td>validation</td></tr><tr><td>Dataset B</td><td>83</td><td>[16]</td><td>validation</td></tr><tr><td>Dataset C</td><td>29</td><td>[35]</td><td>validation</td></tr><tr><td>Dataset D (valid)</td><td>100</td><td>[26]</td><td>validation</td></tr><tr><td>Dataset E</td><td>65,000</td><td>[26]</td><td>train</td></tr></tbody></table>

# 5 Results

The total number of instances where the Hamming loss between the target and predicted structure is 0 is labelled as Correct in the results tables. Apart from the Hamming loss metric, the average of both Minimum Free Energy (MFE) and GC content was also computed for each resulting designed sequence. The sliding windows size (W) was varied between 1 and 6. The results are shown in Table 4, Table 5 and Table 6. SPRNA agent was also compared with other four existing RNA Inverse Folding models including RNAInverse [13], RNAiFOLD [11], incaRNAfbinv [24] and Modena [35]. Each of these models was allocated a maximum of 1 minute RNA Inverse Folding time for each sequence design session. The comparative results are recorded in Tables 8, 9, 10 and 11. The GC and MFE entries are average values.

<table><caption>**Table 4** Results on the Dataset A</caption><thead><tr><th>W</th><th>Correct / 63</th><th>MFE</th><th>GC</th></tr></thead><tbody><tr><td>1</td><td>48</td><td>-57.22</td><td>54.16</td></tr><tr><td>2</td><td>50</td><td>-62.18</td><td>51.62</td></tr><tr><td>3</td><td>53</td><td>-60.57</td><td>53.14</td></tr><tr><td>4</td><td>57</td><td>-63.35</td><td>52.62</td></tr><tr><td>5</td><td>53</td><td>-49.83</td><td>46.45</td></tr><tr><td>6</td><td>46</td><td>-60.09</td><td>53.36</td></tr></tbody></table>

<table><caption>**Table 6** Results on the Dataset C</caption><thead><tr><th>W</th><th>Correct / 29</th><th>MFE</th><th>GC</th></tr></thead><tbody><tr><td>1</td><td>18</td><td>-59.96</td><td>49.15</td></tr><tr><td>2</td><td>18</td><td>-59.76</td><td>49.15</td></tr><tr><td>3</td><td>17</td><td>-60.88</td><td>47.64</td></tr><tr><td>4</td><td>22</td><td>-59.47</td><td>51.82</td></tr><tr><td>5</td><td>20</td><td>-59.62</td><td>50.33</td></tr><tr><td>6</td><td>21</td><td>-44.59</td><td>59.09</td></tr></tbody></table>

<table><caption>**Table 5** Results on the Dataset B</caption><thead><tr><th>W</th><th>Correct / 83</th><th>MFE</th><th>GC</th></tr></thead><tbody><tr><td>1</td><td>60</td><td>-61.20</td><td>49.21</td></tr><tr><td>2</td><td>62</td><td>-62.89</td><td>52.16</td></tr><tr><td>3</td><td>63</td><td>-62.76</td><td>53.02</td></tr><tr><td>4</td><td>69</td><td>-62.19</td><td>54.55</td></tr><tr><td>5</td><td>64</td><td>-64.63</td><td>52.91</td></tr><tr><td>6</td><td>62</td><td>-61.10</td><td>51.85</td></tr></tbody></table>

<table><caption>**Table 7** Results on the Dataset D</caption><thead><tr><th>W</th><th>Correct / 100</th><th>MFE</th><th>GC</th></tr></thead><tbody><tr><td>1</td><td>80</td><td>-40.21</td><td>58.08</td></tr><tr><td>2</td><td>85</td><td>-47.38</td><td>56.74</td></tr><tr><td>3</td><td>90</td><td>-58.90</td><td>57.26</td></tr><tr><td>4</td><td>88</td><td>-49.92</td><td>51.64</td></tr><tr><td>5</td><td>86</td><td>-60.28</td><td>58.23</td></tr><tr><td>6</td><td>82</td><td>-52.45</td><td>57.68</td></tr></tbody></table>
23:10 Self Playing RNA Inverse Folding

<table><caption>**Table 8** Comparative Analysis on Dataset A</caption><thead><tr><th>Method</th><th>MFE</th><th>GC</th><th>X/63</th></tr></thead><tbody><tr><td>RNAInverse</td><td>-27.47</td><td>48.20</td><td>40</td></tr><tr><td>RNAiFold</td><td>-52.67</td><td>50.06</td><td>50</td></tr><tr><td>incaRNAfbinv</td><td>-35.05</td><td>62.50</td><td>12</td></tr><tr><td>Modena</td><td>-49.35</td><td>50.52</td><td>27</td></tr><tr><td>SPRNA[W=4]</td><td><strong>-63.35</strong></td><td><strong>52.62</strong></td><td><strong>57</strong></td></tr></tbody></table>

<table><caption>**Table 9** Comparative Analysis on Dataset B</caption><thead><tr><th>Method</th><th>MFE</th><th>GC</th><th>X/83</th></tr></thead><tbody><tr><td>RNAInverse</td><td>-29.02</td><td>48.23</td><td>47</td></tr><tr><td>RNAiFold</td><td>-53.30</td><td>49.15</td><td>75</td></tr><tr><td>incaRNAfbinv</td><td>-34.47</td><td>46.67</td><td>13</td></tr><tr><td>Modena</td><td>-51.01</td><td>-49.90</td><td>37</td></tr><tr><td>SPRNA[W=4]</td><td><strong>-62.19</strong></td><td><strong>54.55</strong></td><td><strong>69</strong></td></tr></tbody></table>

<table><caption>**Table 10** Comparative Analysis on Dataset C</caption><thead><tr><th>Method</th><th>MFE</th><th>GC</th><th>X/29</th></tr></thead><tbody><tr><td>RNAInverse</td><td>-26.08</td><td>48.00</td><td>16</td></tr><tr><td>RNAiFold</td><td>-58.90</td><td>45.89</td><td>18</td></tr><tr><td>incaRNAfbinv</td><td>-46.08</td><td>48.00</td><td>10</td></tr><tr><td>Modena</td><td>-59.64</td><td><strong>52.09</strong></td><td><strong>22</strong></td></tr><tr><td>SPRNA[W=4]</td><td>-59.47</td><td><strong>51.82</strong></td><td><strong>22</strong></td></tr></tbody></table>

<table><caption>**Table 11** Comparative Analysis on Dataset D</caption><thead><tr><th>Method</th><th>MFE</th><th>GC</th><th>X/100</th></tr></thead><tbody><tr><td>RNAInverse</td><td>-29.56</td><td>51.31</td><td>79</td></tr><tr><td>RNAiFold</td><td>-48.25</td><td>52.78</td><td>78</td></tr><tr><td>incaRNAfbinv</td><td>-19.70</td><td>57.50</td><td>60</td></tr><tr><td>Modena</td><td>-47.48</td><td>48.40</td><td>75</td></tr><tr><td>SPRNA[W=3]</td><td><strong>-58.90</strong></td><td>57.26</td><td>90</td></tr></tbody></table>

# 6 Discussion

The existing RNA Inverse Folding methods are primarily based on dynamic programming, constraint programming, evolutionary algorithms, genetic algorithms, tree search and general search. These methods are majorly constrained by prior RNA expert knowledge of chemical, molecular and base distributions.

In this paper, we have shown that by leveraging SP and no prior expert knowledge and by performing a one-step look-ahead evaluation using the value network, we can generate RNA sequences which fold to match a given target structure. The inference time of the existing search based and dynamic programming models are generally bounded by $O(Kn)$; where K is the number of iterations to get candidate sequence(s) and n is the length of the designed sequence. The SPRNA inference time on the other hand is bounded by $O(n)$; where n is the length of the designed sequence. Interestingly, a base assignment at any given time step (episode) is bounded by $O(1)$ e.g. once the value network is trained, the policy is generated by a forward propagation which takes constant time.

In RNA Inverse Folding, it is imperative to design a sequence that not only folds to match a given target structure but also possesses a desired MFE and the GC content values. The MFE and GC content properties determine the functional effectiveness of the designed RNA sequence. Generally, sequences with GC content ranging between 50 and 60 and lower MFEs are preferred [25, 36].

Based on the Hamming loss (the Correct entries), the SPRNA model recorded the best result on dataset A (57/63) and dataset D (90/100). The model tied the score with Modena on dataset C (22/29) while RNAiFold recorded the best score on dataset B (75/83). In addition, SPRNA recorded the best MFE score on datasets A, B and D with the GC content value ranging within the expected values as shown in Tables 8, 9, 10 and 11.

The sliding window parameter $W=4$ and $W=3$ recorded the best performance (on the Hamming loss). However, it is important to note that the sequences designed by SPRNA
when $W=5$ on dataset B, $W=3$ on dataset C and $W=5$ on dataset D are more stable considering their MFE scores thus $W$ values between 3 - 5 is best suited for designing RNA sequences with lower MFE values (or more stable sequences).

In general, the results recorded by SPRNA are competitive and promising. The agent can evaluate both known and unknown states to generate policies at any given time step $t$ in the RNA Inverse Folding environment. Importantly, even though the SPRNA agent learns through SP to minimize the MSE between predicted and target structure, it can optimize other RNA Inverse Folding metrics such as the MFE and the GC content implicitly.

However, the SPRNA results are competitive and promising, the model failed to design several sequences e.g 10/100 (Dataset D). This raises the question of whether using a different encoding scheme, deeper value network, other network architecture or novel network learning methods would improve the performance of SPRNA. This excites future work in RNA Inverse Folding.

# 7 Conclusions and Future Work

In this paper, we have presented a new Self Play RNA Inverse Folding agent called SPRNA. An encoding scheme for both the known and unknown RNA Inverse Folding states is also presented. By performing a one-step look-ahead using a value network, SPRNA can select the best action recording competitive results over different RNA Inverse Folding datasets. The proposed encoding scheme is also used to design a Gym Environment for RNA Inverse Folding which allows research extension and development of new RNA Inverse Folding methods. Although SPRNA results were generally competitive, the agent failed to design several sequences. In future research, it would be interesting to investigate if other encoding scheme or different value network architecture or novel learning methods would yield better results. In addition, an extension of Self Play to other real-world problems such as drug design, genetics, protein folding and protein-protein interaction also remains an interesting future research endeavour.

# 8 Supplementary Material

The code and data used in the research is available at https://github.com/kobonyo/sprna
References

1 Mirela Andronescu, Anthony P Fejes, Frank Hutter, Holger H Hoos, and Anne Condon. A new algorithm for rna secondary structure design. *Journal of molecular biology*, 336(3):607-624, 2004.

2 Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In *International conference on machine learning*, pages 551–560. PMLR, 2020.

3 Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. *arXiv preprint* 1912.06680, 2019.

4 Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. arXiv: arXiv preprint 1606.01540.

5 Anke Busch and Rolf Backofen. Info-rna a fast approach to inverse rna folding. *Bioinformatics*, 22(15):1823-1831, 2006.

6 Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. *Artificial intelligence*, 134(1-2):57-83, 2002.

7 Tristan Cazenave, Yen-Chi Chen, Guan-Wei Chen, Shi-Yu Chen, Xian-Dong Chiu, Julien Dehos, Maria Elsa, Qucheng Gong, Hengyuan Hu, Vasil Khalidov, et al. Polygames: Improved zero learning. *ICGA Journal*, pages 1-13, 2020.

8 Tristan Cazenave and Thomas Fournier. Monte carlo inverse folding. arXiv preprint 2005.09961, 2020.

9 Alexander Churkin, Matan Drory Retwitzer, Vladimir Reinharz, Yann Ponty, Jérôme Waldispühl, and Danny Barash. Design of rna's: comparing programs for inverse rna folding. *Briefings in bioinformatics*, 19(2):350-358, 2018.

10 Ali Esmaili-Taheri and Mohammad Ganjtabesh. Erd: a fast and reliable tool for rna design including constraints. BMC bioinformatics, 16(1):1–11, 2015.

11 Juan Antonio Garcia-Martin, Peter Clote, and Ivan Dotu. Rnaifold: a constraint programming algorithm for rna inverse folding and molecular design. *Journal of bioinformatics and computational biology*, 11(02):1350001, 2013.

12 Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In *IEEE conference on computer vision and pattern recognition*, pages 770–778, 2016.

13 Ivo L Hofacker, Walter Fontana, Peter F Stadler, L Sebastian Bonhoeffer, Manfred Tacker, and Peter Schuster. Fast folding and comparison of rna secondary structures. *Monatshefte für Chemie/Chemical Monthly*, 125(2):167–188, 1994.

14 Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In *International conference on machine learning*, pages 448–456. PMLR, 2015.

15 Robert Kleinkauf, Torsten Houwaart, Rolf Backofen, and Martin Mann. antarna-multi-objective inverse folding of pseudoknot rna using ant-colony optimization. BMC bioinformatics, 16(1):1–7, 2015.

16 Robert Kleinkauf, Martin Mann, and Rolf Backofen. antarna: ant colony-based rna sequence design. *Bioinformatics*, 31(19):3114–3121, 2015.

17 Bjarne Knudsen and Jotun Hein. Pfold: Rna secondary structure prediction using stochastic context-free grammars. Nucleic acids research, 31(13):3423-3428, 2003.

18 Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. *Advances in neural information processing systems*, 25:1097–1105, 2012.

19 Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. IEEE, 86(11):2278-2324, 1998.

20 Alex Levin, Mieszko Lis, Yann Ponty, Charles W O'donnell, Srinivas Devadas, Bonnie Berger, and Jérôme Waldispühl. A global sampling approach to designing and reengineering rna secondary structures. Nucleic acids research, 40(20):10041-10052, 2012.
21 Zhipeng Lu and Howard Y Chang. The rna base-pairing problem and base-pairing solutions. *Cold Spring Harbor perspectives in biology*, 10(12):a034926, 2018.

22 Nicholas R Markham and Michael Zuker. Unafold. In *Bioinformatics*, pages 3–31. Springer, 2008.

23 Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. *arXiv preprint* 1312.5602, 2013.

24 Matan Drory Retwitzer, Vladimir Reinharz, Alexander Churkin, Yann Ponty, Jérôme Waldispühl, and Danny Barash. incarnafbinv 2.0: a webserver and software with motif control for fragment-based design of rna's. *Bioinformatics*, 36(9):2920–2922, 2020.

25 Davide Risso, Katja Schwartz, Gavin Sherlock, and Sandrine Dudoit. Gc-content normalization for rna-seq data. *BMC bioinformatics*, 12(1):1–17, 2011.

26 Frederic Runge, Danny Stoll, Stefan Falkner, and Frank Hutter. Learning to design rna. *arXiv preprint arXiv:1812.11951*, 2018.

27 Yasubumi Sakakibara, Michael Brown, Richard Hughey, I Saira Mian, Kimmen Sjölander, Rebecca C Underwood, and David Haussler. Stochastic context-free grammers for trna modeling. *Nucleic acids research*, 22(23):5112–5120, 1994.

28 Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. *arXiv preprint* 1511.05952, 2015.

29 John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. *arXiv preprint arXiv:1707.06347*, 2017.

30 David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. *nature*, 529(7587):484–489, 2016.

31 David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. *arXiv preprint* 1712.01815, 2017.

32 David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. *nature*, 550(7676):354–359, 2017.

33 Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. *The journal of machine learning research*, 15(1):1929–1958, 2014.

34 Richard S Sutton and Andrew G Barto. *Reinforcement learning: An introduction*. MIT press, 2018.

35 Akito Taneda. Multi-objective genetic algorithm for pseudoknotted rna sequence design. *Frontiers in genetics*, 3:36, 2012.

36 Edoardo Trotta. On the normalization of the minimum free energy of rna's by sequence length. *PloS one*, 9(11):e113380, 2014.

37 Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In *IEEE conference on computer vision and pattern recognition*, pages 1492–1500, 2017.

38 Xiufeng Yang, Kazuki Yoshizoe, Akito Taneda, and Koji Tsuda. Rna inverse folding using monte carlo tree search. *BMC bioinformatics*, 18(1):1–12, 2017.

39 Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. *arXiv preprint* 1605.07146, 2016.