# An Empirical Study of Cross-Lingual Transferability in Generative Dialogue
State Tracker

Yen-Ting Lin, Yun-Nung Chen

###### Abstract

There has been a rapid development in data-driven task-oriented dialogue
systems with the benefit of large-scale datasets. However, the progress of
dialogue systems in low-resource languages lags far behind due to the lack of
high-quality data. To advance the cross-lingual technology in building dialog
systems, DSTC9 introduces the task of cross-lingual dialog state tracking,
where we test the DST module in a low-resource language given the rich-
resource training dataset.

This paper studies the transferability of a cross-lingual generative dialogue
state tracking system using a multilingual pre-trained seq2seq model. We
experiment under different settings, including joint-training or pre-training
on cross-lingual and cross-ontology datasets. We also find out the low cross-
lingual transferability of our approaches and provides investigation and
discussion.

## Introduction

Dialogue state tracking is one of the essential building blocks in the task-
oriented dialogues system. With the active research breakthrough in the data-
driven task-oriented dialogue technology and the popularity of personal
assistants in the market, the need for task-oriented dialogue systems capable
of doing similar services in low-resource languages is expanding. However,
building a new dataset for task-oriented dialogue systems for low-resource
language is even more laborious and costly. It would be desirable to use
existing data in a high-resource language to train models in low-resource
languages. Therefore, if cross-lingual transfer learning can be applied
effectively and efficiently on dialogue state tracking, the development of
task-oriented dialogue systems on low-resource languages can be accelerated.

The Ninth Dialog System Technology Challenge (DSTC9) Track2 (Gunasekara et al.
2020) proposed a cross-lingual multi-domain dialogue state tracking task. The
main goal is to build a cross-lingual dialogue state tracker with a rich
resource language training set and a small development set in the low resource
language. The organizers adopt MultiWOZ 2.1 (Eric et al. 2019) and CrossWOZ
(Zhu et al. 2020) as the dataset and provide the automatic translation of
these two datasets for development. In this paper’s settings, our task is to
build a cross-lingual dialogue state tracker in the settings of CrossWOZ-en,
the English translation of CrossWOZ. In the following, we will refer cross-
lingual datasets to datasets in different languages, such as MultiWOZ-zh and
CrossWOZ-en, and cross-ontology datasets to datasets with different
ontologies, such as MultiWOZ-en and CrossWOZ-en.

The cross-lingual transfer learning claims to transfer knowledge across
different languages. However, in our experiments, we experience tremendous
impediments in joint training on cross-lingual or even cross-ontology
datasets. To the best of our knowledge, all previous cross-lingual dialogue
state trackers approach DST as a classification problem (Mrkšić et al.
2017)(Liu et al. 2019), which does not guarantee the success of
transferability on our generative dialogue state tracker.

The contributions of this paper are three-fold:

  * •

This paper explores the cross-lingual generative dialogue state tracking
system’s transferability.

  * •

This paper compares joint training and pre-train then finetune method with
cross-lingual and cross-ontology datasets.

  * •

This paper analyzes and open discussion on colossal performance drop when
training with cross-lingual or cross-ontology datasets.

## Problem Formulation

In this paper, we study the cross-lingual multi-domain dialogue state tracking
task. Here we define the multi-domain dialogue state tracking problem and
introduce the cross-lingual DST datasets.

### Multi-domain Dialogue State Tracking

The dialogue state in the multi-domain dialogue state tracking is a set of
(domain, slot name, value) triplets, where the domain indicates the service
that the user is requesting, slot name represents the goal from the user, and
value is the explicit constraint of the goal. For dialogue states not
mentioned in the dialogue context, we assign a null value, $\emptyset$, to the
corresponding values. For example, (Hotel, type, luxury) summarizes one of the
user’s constraints of booking a luxury hotel, and (Attraction, fee, 20 yuan or
less) means the user wants to find a tourist attraction with a ticket price
equal to or lower than 20 dollars. An example is presented in Figure1.

Our task is to predict the dialogue state at the $t^{th}$ turn,
$\mathcal{B}_{t}=\\{(\mathcal{D}^{i},\mathcal{S}^{i},\mathcal{V}^{i})\,|\,1\leq
i\leq I\\}$ where $I$ is the number of states to be tracked, given the
historical dialogue context until now, defined as
$\mathcal{C}_{t}=\\{\mathcal{U}_{1},\mathcal{R}_{1},\mathcal{U}_{2},\mathcal{R}_{2},\dots,\mathcal{R}_{t-1},\mathcal{U}_{t}\\}$
where $\mathcal{U}_{i}$ and $\mathcal{R}_{i}$ is the user utterance and system
response, respectively, at the $i^{th}$ turn.

Figure 1: Illustration of dialogue state tracking. The dialogue is sampled
from CrossWOZ-en.

### Dataset

MultiWOZ is the task-oriented dataset often used as the benchmark dataset for
task-oriented dialogue system tasks, including dialogue state tracking,
dialogue policy optimization, and NLG. MultiWOZ 2.1 is a cleaner version of
the previous counterpart with more than 30% updates in dialogue state
annotations. CrossWOZ is a Chinese multi-domain task-oriented dataset with
more than 6,000 dialogues, five domains, and 72 slots. Both of the above
datasets collects human-to-human dialogues in Wizard-of-Oz settings. Table 1
lists the details of the dataset.

In DSTC9 Track 2, the organizers translate MultiWOZ and CrossWOZ into Chinese
and English, respectively, and we refer the translated version of MultiWOZ and
CrossWOZ as MultiWOZ-zh and CrossWOZ-en, respectively. The public and private
test of CrossWOZ-en in DSTC9 has 250 dialogues, but only the public test set
has annotations. Therefore, we use the public one as the test set in our
experiments.

Metric | MultiWOZ | CrossWOZ
---|---|---
Language | English | Chinese (Simplified)
# Dialogues |  8,438 |  5,012
Total # turns | 113,556 | 84,692
# Domains | 7 | 5
# Slots | 24 | 72
# Values | 4,510 | 7,871
Table 1: Statistics of MultiWOZ and CrossWOZ. Note that the translated version
of these two datasets have the same metrics

## Related Work

### Dialogue State Tracker

Traditionally, dialogue state tracking depends on fixed vocabulary approaches
where retrieval-based models ranks slot candidates from a given slot ontology.
(Ramadan, Budzianowski, and Gašić 2018)(Lee, Lee, and Kim 2019)(Shan et al.
2020) However, recent research efforts in DST have moved towards generation-
based approaches where the models generate slot value given the dialogue
history. (Wu et al. 2019) proposed a generative multi-domain DST model with a
copy mechanism which ensures the capability to generate unseen slot values.
(Kim et al. 2019) introduced a selectively overwriting mechanism, a memory-
based approach to increase efficiency in training and inference. (Le, Socher,
and Hoi 2020) adopted a non-autoregressive architecture to model potential
dependencies among (domain, slot) pairs and reduce real-time DST latency
significantly. (Hosseini-Asl et al. 2020) took advantage of the powerful
generation ability of large-scale auto-regressive language model and
formulated the DST problem as a casual language modeling problem.

### Multilingual Transfer Learning in Task-oriented Dialogue

(Schuster et al. 2019) introduced a multilingual multi-domain NLU dataset.
(Mrkšić et al. 2017) annotated two additional languages to WOZ 2.0 (Mrkšic et
al. 2017) and (Liu et al. 2019) proposed a mixed-language training for cross-
lingual NLU and DST tasks. Noted that all previous multilingual DST methods
modeled the dialogue state tracking task as a classification problem. (Mrkšić
et al. 2017)(Liu et al. 2019)

## Methods

This paper considers the multi-domain dialogue state track-ing as a sequence
generation task by adopting a sequence-to-sequence framework.

### Architecture

Following (Liu et al. 2020), we use the sequence-to-sequence Transformer
architecture (Vaswani et al. 2017) with 12 layers in each encoder and decoder.
We denote seq2seq as our model in the following.

### DST as Sequence Generation

The input sequence is composed of the concatenation of dialogue context
$\mathbf{x^{t}}=\\{\mathcal{U}_{1};\mathcal{R}_{1};\mathcal{U}_{2};\mathcal{R}_{2};\dots;\mathcal{R}_{t-1};\mathcal{U}_{t}\\}$
where ; denote the concatenation of texts.

For the target dialogue state, we only consider the slots where the values are
non-empty. The target sequence is consist of the concatenation of the (domain,
slot, value) triplets with a non-empty value,
$\mathbf{y^{t}}=\\{\mathcal{D}^{i};\mathcal{S}^{i};\mathcal{V}^{i}|1\leq i\leq
I\wedge\mathcal{S}^{i}\neq\emptyset\\}$.

$\mathbf{\hat{y}^{t}}=seq2seq(\mathbf{x^{t}})$

We fix the order of the (domain, slot name, value) triplets for consistency.

The training objective is to minimize the cross-entropy loss between the
ground truth sequence $\mathbf{y^{t}}$ and the predicted sequence
$\mathbf{\hat{y}^{t}}$.

### Post-processing

The predicted sequence $\mathbf{\hat{y}^{t}}$ is then parsed by heuristic
rules to construct
$\hat{\mathcal{B}_{t}}=\\{\mathcal{D}^{i};\mathcal{S}^{i};\hat{\mathcal{V}}^{i}|1\leq
i\leq I\\}$.

By utilizing the possible values of slots in the ontology, for predicted slot
values $\hat{\mathcal{V}}$ that do not appears in the ontology, we choose the
one with the best match to our predicted value. 111This is implemented by
difflib.get_close_matches in Python

## Experiments

In the following section, we describe evaluation metrics, experiment setting
and introduce experimental results.

### Evaluation Metrics

We use joint goal accuracy and slot F1 as our metrics to evaluate our dialogue
state tracking system.

  * •

Joint Goal Accuracy: The proportion of dialogue turns where predicted dialogue
states match entirely to the ground truth dialogue states.

  * •

Slot F1: The macro-averaged F1 score for all slots in each turn.

### Experiments Settings

We want to examine how different settings affect the performance of the target
low-resource dataset: CrossWOZ-en.222In our experimental circumstance, English
is the low-resource language since the original language of CrossWOZ is
Chinese. We will conduct our experiments in the settings below.

  * •

Direct Fine-tuning

  * •

Cross-Lingual Training (CLT)

  * •

Cross-Ontology Training (COT)

  * •

Cross-Lingual Cross-Ontology Training (CL/COT)

  * •

Cross-Lingual Pre-Training (CLPT)

  * •

Cross-Ontology Pre-Training (COPT)

  * •

Cross-Lingual Cross-Ontology Pre-Training (CL/COPT)

Table 2 and 3 show the datasets for training and pre-training in different
settings. For experiments with pre-training, all models are pre-trained on the
pre-training dataset and then fine-tuned on CrossWOZ-en.

The baseline model provided by DSTC9 is SUMBT (Lee, Lee, and Kim 2019), the
ontology-based model trained on CrossWOZ-en.

### Multilingual Denoising Pre-training

All of our models initialize from mBART25. (Liu et al. 2020) mBART25 is
trained with denoising auto-encoding task on mono-lingual data in 25
languages, including English and Simplified Chinese. (Liu et al. 2020) shows
pre-training of denoising autoencoding on multiple languages improves the
performance on low resource machine translation. We hope using mBART25 as
initial weights would improve the cross-lingual transferability.

### Implementation Details

In all experiments, the models are optimized with AdamW (Loshchilov and Hutter
2017) with learning rate set to $1e^{-4}$ for 4 epochs. The best model is
selected from the validation loss and is used for testing.

During training, the decoder part of our model is trained in the teacher
forcing fashion (Williams and Zipser 1989). Greedy decoding (Vinyals and Le
2015) is applied when inference. Following mBART (Liu et al. 2020), we use
sentencespiece tokenizer. For GPU memory constraints, source sequences longer
than 512 tokens are truncated at the front and target sequences longer than
256 tokens are truncated at the back.

The models are implemented in Transformers (Wolf et al. 2019), PyTorch (Paszke
et al. 2019) and PyTorch Lightning (Falcon 2019).

## Results and Discussion

The results for all experiment settings are shown in Table 2 and 3.

Experiment | Training Data | JGA | SF1
---|---|---|---
MultiWOZ | CrossWOZ
en | zh | en | zh
Baseline |  |  | ✓ |  |  7.41 |  55.27*
Direct Fine-tuning |  |  | ✓ |  | 16.82 | 66.35
CL/COT | ✓ | ✓ | ✓ | ✓ |  4.10 | 26.50
COT | ✓ |  | ✓ |  |  0.95 | 19.60
CLT |  |  | ✓ | ✓ |  0.53 | 13.45
Table 2: Experimental results on CrossWOZ-en with different training data (%). *: This slot f1 is averaged over both the public and private test dialogues. JGA: Joint Goal Accuracy. SF1: Slot F1. Experiment | Pre-training Data | JGA | SF1
---|---|---|---
MultiWOZ | CrossWOZ
en | zh | en | zh
Direct Fine-tuning |  |  |  |  | 16.82 | 66.35
CL/COPT | ✓ | ✓ |  |  |  5.94 | 38.36
COPT | ✓ |  |  |  |  2.52 | 27.01
CLPT |  |  |  | ✓ |  0.11 | 15.01
Table 3: Experimental results on CrossWOZ-en with pre-training (%).

### Additional Training Data Cause Degeneration

Direct Fine-tuning significantly outperforms other settings, including the
official baseline. We assume English and Chinese data with the same ontology
to train the mBART would bridge the gap between the two languages and increase
the performance. However, in Cross-Lingual Training, training on English and
Chinese version of CrossWOZ leads to catastrophic performance on CrossWOZ-en.

In the Cross-Ontology Training where combine two data in the same language.
However, with different ontologies, the performance marginally increases from
Cross-Lingual Training, which shows more extensive mono-lingual data with the
unmatched domain, slots, and ontology confuses the model during inference. In
the Cross-Lingual Cross-Ontology Training, we collect all four datasets for
training, and the performance is still far from Direct Fine-tuning.

In conclusion, additional data deteriorate the performance on CrossWOZ-en even
whether the language or ontology matches or not.

### Does ”First Pre-training, then fine-tuning” Help?

We hypothesize that training with additional data causes performance
degeneration, and therefore one possible improvement could be first pre-
training the model on cross-lingual / cross-ontology data and then fine-tuning
on the target dataset CrossWOZ-en. Table 3 shows the results.

By comparing COPT to COT and CL/COPT  to CL/COP, the relative performance gain
by over 37% with regards to slot F1. ”Pre-training, fine-tuning” framework may
partially alleviate the problem of catastrophic performance drop in joint
training.

### Domain Performance Difference across Experiment Settings?

This section further investigates the cause of the performance decrease by
comparing the slot F1 of different models across five domains in Figure 2.

Generally speaking, in attraction, restaurant, and hotel domains, ”pre-train
then fine-tune” methods beat their ”joint training” counterparts by an
observable margin. By contrast, in metro and taxi domains, despite poor
performance among all, ”joint training” settings beat their”pre-train then
fine-tune” counterparts.

The only two trackable slots in the metro and taxi domain, ”from” and ”to,”
usually take the address or name of buildings, are highly non-transferable
across datasets. We conjecture that pretraining on cross-lingual or cross-
ontology datasets does not help or even hurt those non-transferable slots.

Figure 2: Slot F1 across 5 domains in CrossWOZ-en in different settings.

## Conclusion

In this paper, we build a cross-lingual multi-domain generative dialogue state
tracker with multilingual seq2seq to test on CrossWOZ-en and investigate our
tracker’s transferability under different training settings. We find that
jointly trained the dialogue state tracker on cross-lingual or cross-ontology
data degenerates the performance. Pre-training on cross-lingual or cross-
ontology data, then fine-tuning framework may alleviate the problem, and we
find empirically evidence on relative improvement in slot F1. A finding from
the domain performance shift is that performance on some non-transferable
slots, such as name, from, to, may be limited by the previous pretraining
approach. A future research direction would investigate why such a significant
performance declines in joint training and tries to bridge it.

## References

  * Eric et al. (2019) Eric, M.; Goel, R.; Paul, S.; Kumar, A.; Sethi, A.; Ku, P.; Goyal, A. K.; Agarwal, S.; Gao, S.; and Hakkani-Tur, D. 2019.  MultiWOZ 2.1: A Consolidated Multi-Domain Dialogue Dataset with State Corrections and State Tracking Baselines.
  * Falcon (2019) Falcon, W. 2019.  PyTorch Lightning.  _GitHub. Note: https://github.com/PyTorchLightning/pytorch-lightning_ 3\.
  * Gunasekara et al. (2020) Gunasekara, C.; Kim, S.; D’Haro, L. F.; Rastogi, A.; Chen, Y.-N.; Eric, M.; Hedayatnia, B.; Gopalakrishnan, K.; Liu, Y.; Huang, C.-W.; Hakkani-Tür, D.; Li, J.; Zhu, Q.; Luo, L.; Liden, L.; Huang, K.; Shayandeh, S.; Liang, R.; Peng, B.; Zhang, Z.; Shukla, S.; Huang, M.; Gao, J.; Mehri, S.; Feng, Y.; Gordon, C.; Alavi, S. H.; Traum, D.; Eskenazi, M.; Beirami, A.; Eunjoon; Cho; Crook, P. A.; De, A.; Geramifard, A.; Kottur, S.; Moon, S.; Poddar, S.; and Subba, R. 2020.  Overview of the Ninth Dialog System Technology Challenge: DSTC9 URL https://arxiv.org/abs/2011.06486.
  * Hosseini-Asl et al. (2020) Hosseini-Asl, E.; McCann, B.; Wu, C.-S.; Yavuz, S.; and Socher, R. 2020.  A Simple Language Model for Task-Oriented Dialogue URL http://arxiv.org/abs/2005.00796.
  * Kim et al. (2019) Kim, S.; Yang, S.; Kim, G.; and Lee, S.-W. 2019.  Efficient Dialogue State Tracking by Selectively Overwriting Memory.  _arXiv_ URL http://arxiv.org/abs/1911.03906.
  * Le, Socher, and Hoi (2020) Le, H.; Socher, R.; and Hoi, S. C. H. 2020.  Non-Autoregressive Dialog State Tracking 1–21.  URL http://arxiv.org/abs/2002.08024.
  * Lee, Lee, and Kim (2019) Lee, H.; Lee, J.; and Kim, T.-Y. 2019.  SUMBT: Slot-Utterance Matching for Universal and Scalable Belief Tracking 5478–5483.  doi:10.18653/v1/p19-1546.
  * Liu et al. (2020) Liu, Y.; Gu, J.; Goyal, N.; Li, X.; Edunov, S.; Ghazvininejad, M.; Lewis, M.; and Zettlemoyer, L. 2020.  Multilingual Denoising Pre-training for Neural Machine Translation URL https://arxiv.org/abs/2001.08210.
  * Liu et al. (2019) Liu, Z.; Winata, G. I.; Lin, Z.; Xu, P.; and Fung, P. 2019.  Attention-Informed Mixed-Language Training for Zero-shot Cross-lingual Task-oriented Dialogue Systems.  _arXiv_ URL http://arxiv.org/abs/1911.09273.
  * Loshchilov and Hutter (2017) Loshchilov, I.; and Hutter, F. 2017.  Decoupled Weight Decay Regularization URL http://arxiv.org/abs/1711.05101.
  * Mrkšic et al. (2017) Mrkšic, N.; Séaghdha, D.; Wen, T. H.; Thomson, B.; and Young, S. 2017\.  Neural belief tracker: Data-driven dialogue state tracking.  _ACL 2017 - 55th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference (Long Papers)_ 1: 1777–1788.  doi:10.18653/v1/P17-1163.
  * Mrkšić et al. (2017) Mrkšić, N.; Vulić, I.; Séaghdha, D. Ó.; Leviant, I.; Reichart, R.; Gašić, M.; Korhonen, A.; and Young, S. 2017.  Semantic Specialisation of Distributional Word Vector Spaces using Monolingual and Cross-Lingual Constraints.  _arXiv_ URL http://arxiv.org/abs/1706.00374.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32_ , 8024–8035. Curran Associates, Inc.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Ramadan, Budzianowski, and Gašić (2018) Ramadan, O.; Budzianowski, P.; and Gašić, M. 2018.  Large-Scale Multi-Domain Belief Tracking with Knowledge Sharing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , 432–437. Melbourne, Australia: Association for Computational Linguistics.  doi:10.18653/v1/P18-2069.  URL https://www.aclweb.org/anthology/P18-2069.
  * Schuster et al. (2019) Schuster, S.; Gupta, S.; Shah, R.; and Lewis, M. 2019.  Cross-lingual Transfer Learning for Multilingual Task Oriented Dialog.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 3795–3805. Minneapolis, Minnesota: Association for Computational Linguistics.  doi:10.18653/v1/N19-1380.  URL https://www.aclweb.org/anthology/N19-1380.
  * Shan et al. (2020) Shan, Y.; Li, Z.; Zhang, J.; Meng, F.; Feng, Y.; Niu, C.; and Zhou, J. 2020.  A Contextual Hierarchical Attention Network with Adaptive Objective for Dialogue State Tracking 6322–6333.  URL http://arxiv.org/abs/2006.01554.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention Is All You Need.
  * Vinyals and Le (2015) Vinyals, O.; and Le, Q. 2015.  A neural conversational model.  _arXiv preprint arXiv:1506.05869_ .
  * Williams and Zipser (1989) Williams, R. J.; and Zipser, D. 1989.  A learning algorithm for continually running fully recurrent neural networks.  _Neural computation_ 1(2): 270–280.
  * Wolf et al. (2019) Wolf, T.; Debut, L.; Sanh, V.; Chaumond, J.; Delangue, C.; Moi, A.; Cistac, P.; Rault, T.; Louf, R.; Funtowicz, M.; Davison, J.; Shleifer, S.; von Platen, P.; Ma, C.; Jernite, Y.; Plu, J.; Xu, C.; Scao, T. L.; Gugger, S.; Drame, M.; Lhoest, Q.; and Rush, A. M. 2019.  HuggingFace’s Transformers: State-of-the-art Natural Language Processing.  _ArXiv_ abs/1910.03771.
  * Wu et al. (2019) Wu, C.-S.; Madotto, A.; Hosseini-Asl, E.; Xiong, C.; Socher, R.; and Fung, P. 2019\.  Transferable Multi-Domain State Generator for Task-Oriented Dialogue Systems 808–819.  doi:10.18653/v1/p19-1078.
  * Zhu et al. (2020) Zhu, Q.; Zhang, W.; Liu, T.; and Wang, W. Y. 2020.  Counterfactual Off-Policy Training for Neural Response Generation URL http://arxiv.org/abs/2004.14507.


# Towards Automated Design of Riboswitches

Frederic Runge  Jörg K.H. Franke  Frank Hutter

###### Abstract

Experimental screening and selection pipelines for the discovery of novel
riboswitches are expensive, time-consuming, and inefficient. Using
computational methods to reduce the number of candidates for the screen could
drastically decrease these costs. However, existing computational approaches
do not fully satisfy all requirements for the design of such initial screening
libraries. In this work, we present a new method, _libLEARNA_ , capable of
providing RNA focus libraries of diverse variable-length qualified candidates.
Our novel structure-based design approach considers global properties as well
as desired sequence and structure features. We demonstrate the benefits of our
method by designing theophylline riboswitch libraries, following a previously
published protocol, and yielding 30% more unique high-quality candidates.

Machine Learning, ICML

##  1 Introduction

Riboswitches (Mironov et al., 2002) are regulatory RNA elements, typically
located in the 5$\text{}^{\prime}$ untranslated region of messenger RNAs
(mRNAs), that can specifically bind certain metabolites (ligand) to alter gene
expression. They consist of an _aptamer_ for recognizing the ligand, closely
connected to an _expression platform_ that couples ligand binding with gene
regulation. The binding signal is transduced by a conformational change of the
switch. Riboswitches are typically found in bacteria but can also be
artificially constructed. Since aptamers are capable of binding nearly every
molecular and supramolecular target (Vorobyeva et al., 2018), riboswitches
have become interesting tools for different applications including modulation
of cellular functions (Hallberg et al., 2017) or the development of biosensors
(Findeiß et al., 2017).

However, the discovery of new functional riboswitches and aptamers is a
challenging process. Current experimental screening procedures, e.g.
systematic evolution of ligands by exponential enrichment (SELEX) (Tuerk &
Gold, 1990), use RNA libraries of up to $10^{16}$ fixed-length random
sequences (Vorobyeva et al., 2018) for a single target, resulting in
expensive, time-consuming, and inefficient screens. It is common knowledge
that the length, the secondary structures, their diversity, and the nucleotide
composition of the sequences in the initial library are crucial for a
successful SELEX (Vorobyeva et al., 2018; Kohlberger & Gadermaier, 2022).
However, random libraries of fixed-length sequences are still most widely
used. Focused design can help to decrease the size of the initial library and
therefore drastically reduce the costs of these SELEX pipelines.

To tackle the problem of library generation, there exists different
computational approaches. While earlier work focused on candidate selection
from fixed-length random libraries (Kim et al., 2010; Zhou et al., 2015) based
on different features, more recent approaches seek to tackle the problem with
generative algorithms, employing recurrent neural networks (Im et al., 2019),
Restricted Boltzmann Machines (Di Gioacchino et al., 2022), variational
autoencoders (VAE) (Iwano et al., 2022), Monte-Carlo Tree Search(Lee et al.,
2021), or evolutionary algorithms (Andress et al., 2022). However, these
methods require initial libraries either from previous SELEX data (Di
Gioacchino et al., 2022; Iwano et al., 2022), of known good binders (Andress
et al., 2022), or even known interaction scores (Im et al., 2019; Lee et al.,
2021), which is often unavailable for the discovery of novel aptamers.
Further, the design process works with sequence information only, ignoring
nucleotide compositions or using secondary structure only to enable docking
simulations for scoring.

As an alternative, rational structure-based RNA design algorithms have
previously been employed to successfully design riboswitches (Wachsmuth et
al., 2012; Ender et al., 2021). The general goal of these algorithms is to
find an RNA sequence that folds into a desired secondary structure. However,
all structure-based RNA design algorithms are either limited to the design of
fixed-length candidates (Hofacker et al., 1994; Andronescu et al., 2004;
Taneda, 2010; Kleinkauf et al., 2015; Eastman et al., 2018; Runge et al.,
2019) or require a fully defined pairing scheme of the input structure which
is a strong restriction on the structural diversity and hinders their
applicability to larger scale library designs. This is also true for tools
that were specifically developed for the task of riboswitch design, like the
sampling approach proposed by Hammer et al. (2017).

In this work, we present a novel structure-based RNA design algorithm,
_libLEARNA_ , that is capable of designing large amounts of diverse candidate
sequences with different lengths, while considering desired sequence and
structural constraints, as well as nucleotide distributions, during the design
process. In particular, our contributions are as follows:

  * •

We introduce a novel RNA design paradigm that enables the design of variable-
length RNA sequences from desired arbitrary sequence and structure parts.

  * •

We improve an existing RNA design algorithm, _LEARNA_ (Runge et al., 2019),
with a masked training objective to enable efficient RNA library generation,
including global sequence properties due to the robustness of our approach.

  * •

We show the benefits of our approach by exemplarily designing theophylline
riboswitch libraries, following a previously proposed protocol by Wachsmuth et
al. (2012), yielding 30% more unique candidates compared to the original
approach and up to 47% when designing sequences with desired G and C
nucleotide ratios, while providing greater structural diversity across nearly
uniformly distributed sequence lengths.

##  2 Method

We first recap the foundation of our method, the _LEARNA_ algorithm, followed
by the changes we apply to the state representations, the training procedure,
and the meta-optimization process which leads to its successor _libLEARNA_.

###  2.1 Background

_LEARNA_ is a generative automated deep reinforcement learning (AutoRL)
(Parker-Holder et al., 2022) algorithm for the inverse RNA folding problem
(Hofacker et al., 1994). The algorithm samples RNA sequences from a learned
policy given a target secondary structure. In an inner-loop, a deep
reinforcement learning (RL) algorithm meta-learns an RNA design policy across
thousands of different inverse RNA folding tasks. The validation loss is
communicated to an efficient Bayesian Optimization method, BOHB (Falkner et
al., 2018), which jointly optimizes the configuration of the RL system in the
outer-loop. The actions of the RL agent correspond to placing a nucleotide (A,
C, G, or U) for each position, or directly placing Watson-Crick pairs (A-U,
U-A, G-C, or C-G) in case the structure indicates that the given position is
paired to another nucleotide. States are defined as local representations of
the input structure in dot-bracket format (Hofacker et al., 1994) using an
n-gram centered around the current position. After applying a folding
algorithm to the designed sequence, the reward function is based on the
Hamming distance between the folded candidate and the desired structure.
Finally, the best-performing configuration on the validation set is evaluated
at test time.

Table 1: Originally proposed theophylline riboswitch constructs and partial
RNA design space formulation. (Top) The sequence parts of the six originally
proposed riboswitch constructs by Wachsmuth et al. (2012) and the sequence
part of the design space. (Bottom) The corresponding structure parts of the
constructs and the structural part of the design space. Red: TCT8-4
theophylline aptamer; green: variable length spacer domain; blue: domain ought
to pair with the aptamer (complementary to the 3′-end of the aptamer sequence
in the original design); black: 8-U-stretch. Masked positions are indicated
with ?, positions for extensions are indicated with $\hat{?}$.

Construct | Aptamer | Spacer | Complementary Region | 8-U-Stretch
---|---|---|---|---
RS1 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | UUACAUC | UGAAGUGCUGCC | UUUUUUUU
RS2 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | UGAUCUCGCU | UGAAGUGCUGC | UUUUUUUU
RS3 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | UUUACAUACUCGGUAAAC | UGAAGUGCUGCCA | UUUUUUUU
RS4 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | AACCGAAAUUUGCGCU | UGAAGUGCUGC | UUUUUUUU
RS8 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | CUCCUAGUGGAG | UGAAGUGCUG | UUUUUUUU
RS10 Sequence | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA | GAAAUCUC | UGAAGUGCUG | UUUUUUUU
Task Sequence Parts | AAGUGAUACCAGCAUCGUCUUGAUGCCCUUGGCAGCACUUCA |  $\hat{?}$??????$\hat{?}$ | UGAAGUGCUG$\hat{?}$ | UUUUUUUU
RS1 Structure | ...........(((((.....)))))....(((((((((((( | ....... | )))))))))))) | ........
RS2 Structure | ...........(((((.....)))))....(((((((((((( | .......... | ))))))))))) | ).......
RS3 Structure | ...........(((((.....)))))...((((((((((((( | (((((.......))))). | ))))))))))))) | ........
RS4 Structure | ...........(((((.....)))))....(((((((((((( | (..((.......)).) | ))))))))))) | ).......
RS8 Structure | ........((((((((.....)))))...)))(((((((((( | ((((....)))) | )))))))))) | ........
RS10 Structure | ........((((((((.....)))))...)))(((((((((( | ((....) | ))))))))))) | ........
Task Structure Parts | ........???(((((.....)))))...???(((((((((( |  $\hat{?}$??....$\hat{?}$ | ))))))))))$\hat{?}$ | ?.......

###  2.2 libLEARNA

We improve _LEARNA_ to design RNA candidates from arbitrary sequence and
structure constraints due to an extended state representation, changes in the
training procedure, and additional dimensions, as well as changes to the
general objective of the meta-optimization process.

State Representations To inform _libLEARNA_ about constraints in the sequence
and the structure, we extend the state representations of _LEARNA_. In
particular, we numerically encode pairs of a sequence symbol and its
corresponding structure symbol for each position of the design task. This
enlarges the state space of _libLEARNA_ compared to _LEARNA_ but allows
_libLEARNA_ to be more flexible in terms of design tasks it can be applied to.

Training Instead of training on tasks of the inverse RNA folding problem, we
use a masked training objective similar to the masked language model training
in BERT (Devlin et al., 2018). In particular, we follow Runge et al. (2019) to
generate three training datasets with different length distributions ($\leq
200$ nucleotides (nt), $\geq 200$ nt, random length) of $100000$ samples each,
and a non-overlapping validation set of $100$ samples from the Rfam
(Griffiths-Jones et al., 2003) database version 14.1 using _RNAfold_ (Lorenz
et al., 2011) for folding the sequences. However, in contrast to Runge et al.
(2019) we do not mask the entire sequences but derive tasks that correspond to
the design of RNAs from desired sequence and structure parts by applying a
random masking procedure to the sequences and the structures detailed in
Appendix A. The task of _libLEARNA_ during training then is to fill the masked
parts of the sequence such that, after applying a folding algorithm to the
designed sequence, all positions of the resulting folding satisfy the given
positional constraints of the masked structure. Similar to Runge et al.
(2019), the reward is based on the Hamming distance, while masked positions in
the structure are ignored. Our design procedure describes a completely new
structure-based RNA design paradigm since the design algorithm is not informed
about the pairing conditions _a priori_. This is in contrast to previous work
in the field of structure-based RNA design and enables the design of RNAs from
arbitrary sequence and structure parts while creating larger structural
diversity and further allowing us to extend the task at any given point since
we are no longer bound to explicit pairing positions. However, we allow
indexing pairs to explicitly indicate pairing positions if desired. More
details and examples of tasks for the datasets can be found in Appendix A.

Meta-Optimization For _libLEARNA_ , we mainly adopt the configuration space
proposed by Runge et al. (2019) but introduce four new dimensions. (1) While
algorithms for the inverse RNA folding problem typically benefit from directly
predicting Watson-Crick base pairs at sites that are known to be paired with
another nucleotide, the pairing partners for many paired sites are not
trivially distinguishable as a result of our masking procedure during
training. However, we include the choice to make use of the direct prediction
of pairs if the pairing partner can be identified, i.e. there is no masking
between the pairing positions. (2) We add a choice to the configuration space
to dynamically adapt the states based on the design progress to inform the
agent about its own decisions. (3) The choice of training data and (4) the
schedule of the tasks during training can have a strong impact on the final
performance of the learning algorithm. We, therefore, include two dimensions
to choose from three different training data distributions and curricula
(unsorted tasks or sorted by length). We further allowed searching over an
additional LSTM layer. The result is an 18-dimensional search space to jointly
optimize over the network architecture, all parts of the MDP, as well as
training hyperparameters, task distributions, and schedule, using BOHB
(Falkner et al., 2018). We use the exact same setup during meta-optimization
as Runge et al. (2019), with the same training budgets and validation
protocols. However, while Runge et al. (2019) optimized for an RL algorithm
without any policy updates at test time, we directly optimize for an algorithm
with policy updates at evaluation time to increase the adaptation capabilities
of our approach. The meta-optimization procedure, the configuration space, as
well as the final configuration of _libLEARNA_ are detailed in Appendix B.

##  3 Riboswitch Library Generation

After describing the procedure of the original design and evaluation of
candidates for synthetic riboswitches for theophylline-dependent regulation of
transcription proposed by Wachsmuth et al. (2012) we detail our approach for
the construction of an RNA design space and the design of RNA libraries and
evaluate both methods.

###  3.1 Original Setup

#### Initial Setting

Originally, Wachsmuth et al. (2012) constructed riboswitch candidates from (1)
the TCT8-4 theophylline aptamer sequence and structure, (2) a spacer sequence
of 6 to 20 nucleotides (nt), (3) a sequence of 10nt to 21nt complementary to
the 3′-end of the aptamer, and (4) a U-stretch of 8nt at the 3′-end of the
construct.

#### Design Procedure

To generate candidates, Wachsmuth et al. (2012) designed a large library of
random sequences for the spacer region (6-20nt) and a library of sequences
complementary to the 3′-end of the aptamer (10-21nt). From these sets,
randomly sampled sequences were combined with the aptamer and the 8-U-stretch.

###  3.2 libLEARNA Setup

#### Design Space Formulation

We start the formulation of our design space from the entire sequence and the
structure part of the unbound aptamer, a spacer region of unknown sequence, a
region complementary to the 3$\text{}^{\prime}$-end of the aptamer of at least
10nt and the unpaired 8-U-stretch, similar to Wachsmuth et al. (2012). To
ensure a length of 6nt of the spacer region, we use the shared structure
constraints of the six final constructs proposed by Wachsmuth et al. (2012),
which were also used to restrict the unknown parts of the aptamer. We then
introduce three positions where the task can be extended (indicated by
$\hat{?}$ in Table 1) to fit the requirements and fix the length of the design
space to 66nt-91nt according to Wachsmuth et al. (2012). The final definition
of the design space and the proposed constructs of Wachsmuth et al. (2012) are
shown in Table 1.

#### Design Procedure

The input to _libLEARNA_ is the design space shown in Table 1. To generate
candidates, _libLEARNA_ internally first samples a masked task from the design
space by uniformly sampling a sequence of masking tokens for each extension
position considering the length constraints and then tries to solve the task
with a single shot.

Table 2: Overview of candidates that satisfy the design criteria. All numbers
are averages across five runs with different random seeds.

Method | Valid Candidates [%] | Unique Structures
---|---|---
Wachsmuth et al. (2012) | 41,7 | 6316.6
_libLEARNA_ | 70,9 | 8269.6

###  3.3 Experiments

We assess the performance of _libLEARNA_ against the originally proposed
library generation procedure proposed by Wachsmuth et al. (2012) in two
experiments: (1) The design of a library based on sequence and structure
constraints only, and (2) the design of candidates when additionally querying
_libLEARNA_ to design candidates with a specific G and C nucleotide ratio (GC-
content), given a tolerance of $0.01$. We note that _libLEARNA_ was never
trained for predictions with desired GC-contents but that a GC-content loss-
term (the absolute deviation of the GC-content of the current candidate
sequence from the desired GC-content) was simply added to the reward function
of _libLEARNA_. The reward function then is a weighted sum (without any
tuning, setting all weights to 1) of the structure- and the GC-loss. However,
similar to the structural improvement step described by Runge et al. (2019),
we implement a GC-improvement step to guide the agent for this challenging
task, detailed in Appendix C. For each experiment, we generate 50000
candidates with the approach of Wachsmuth et al. (2012) and _libLEARNA_ and
evaluate them as follows.

#### Evaluation

The evaluation of the designed candidates was performed following Wachsmuth et
al. (2012): after dropping duplicates, the designed sequences were folded
using _RNAfold_ and verified for (1) the existence of two hairpin structure
elements, the aptamer hairpin for binding the ligand and the terminator
hairpin formed between the 3$\text{}^{\prime}$-end of the aptamer, the spacer
and the region complementary to the aptamer sequence, (2) no pairing within
the last seven nucleotides of the 8-U-stretch, (3) no pairing between the
spacer and the aptamer in a sequence of folding steps, simulating co-
transcriptional folding with a fixed elongation speed of five. A candidate
that did not pass all criteria was rejected.

#### Results

We observe that _libLEARNA_ generates considerably more candidates that pass
the design criteria compared to the original procedure proposed by Wachsmuth
et al. (2012), yielding 30% more satisfying candidates on average (Table 2).
Further, the candidates are nearly uniformly distributed across the lengths of
the design space, especially for the longer sequences (Figure 1 left), and the
structure diversity generated by _libLEARNA_ is around 23% higher (Table 2).
When designing candidates with desired GC-contents, _libLEARNA_ provides up to
47% more candidates that satisfy the design criteria and contain the specific
G and C nucleotide distribution (Figure 1 right). Remarkably, _libLEARNA_ can
also design such candidates on the margins of possible GC-contents ($0.3$ and
$0.6$) which lay between $0.29$ and $0.63$ for the given riboswitch design
space.

Figure 1:  Length and GC-content distribution in the generated libraries.
(Left) The plot displays the distribution of the candidates across different
lengths. (Right) The plot shows the number of unique candidates that satisfy
all design criteria and have the specified G and C nucleotide distribution
when running _libLEARNA_ with a desired GC-content. All numbers are averages
across five runs with different random seeds.

##  4 Conclusion

We propose a new RNA design paradigm based on a masked prediction task that
enables the design of RNA libraries with large structure diversity from
arbitrary sequence and structure constraints. We use the paradigm and develop
a new algorithm, _libLEARNA_ , capable of generating these libraries. We
exemplarily demonstrate the benefits of our method on the design of variable-
length riboswitches, showing the efficiency of our approach. Our results for
library generation with desired G and C nucleotide distributions show that
_libLEARNA_ can handle global constraints, while the robustness to reward
changes suggests potential for handling more constraints, e.g. a desired
energy threshold of the structures, which we will assess in future work.
Overall, our approach bears great potential to support experimental pipelines.

## Acknowledgements

This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under grant number 417962828. The authors further
acknowledge support by the state of Baden-Württemberg through bwHPC and the
German Research Foundation (DFG) through grant no INST 39/963-1 FUGG.

## References

  * Andress et al. (2022) Andress, C., Kappel, K., Cuperlovic-Culf, M., Yan, H., and Li, Y.  Daptev: Deep aptamer evolutionary modelling for covid-19 drug design.  _bioRxiv_ , pp. 2022–11, 2022.
  * Andronescu et al. (2004) Andronescu, M., Fejes, A. P., Hutter, F., Hoos, H. H., and Condon, A.  A new algorithm for rna secondary structure design.  _Journal of molecular biology_ , 336(3):607–624, 2004.
  * Devlin et al. (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Di Gioacchino et al. (2022) Di Gioacchino, A., Procyk, J., Molari, M., Schreck, J. S., Zhou, Y., Liu, Y., Monasson, R., Cocco, S., and Šulc, P.  Generative and interpretable machine learning for aptamer design and analysis of in vitro sequence selection.  _PLoS computational biology_ , 18(9):e1010561, 2022.
  * Eastman et al. (2018) Eastman, P., Shi, J., Ramsundar, B., and Pande, V. S.  Solving the rna design problem with reinforcement learning.  _PLoS computational biology_ , 14(6):e1006176, 2018.
  * Ender et al. (2021) Ender, A., Etzel, M., Hammer, S., Findeiß, S., Stadler, P., and Mörl, M.  Ligand-dependent trna processing by a rationally designed rnase p riboswitch.  _Nucleic acids research_ , 49(3):1784–1800, 2021\.
  * Falkner et al. (2018) Falkner, S., Klein, A., and Hutter, F.  BOHB: Robust and efficient hyperparameter optimization at scale.  In Dy, J. and Krause, A. (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 1437–1446, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Findeiß et al. (2017) Findeiß, S., Etzel, M., Will, S., Mörl, M., and Stadler, P. F.  Design of artificial riboswitches as biosensors.  _Sensors_ , 17(9):1990, 2017.
  * Griffiths-Jones et al. (2003) Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., and Eddy, S. R.  Rfam: an RNA family database.  _Nucleic Acids Research_ , 31(1):439–441, 01 2003\.  ISSN 0305-1048.
  * Hallberg et al. (2017) Hallberg, Z. F., Su, Y., Kitto, R. Z., and Hammond, M. C.  Engineering and in vivo applications of riboswitches.  _Annual review of biochemistry_ , 86:515–539, 2017.
  * Hammer et al. (2017) Hammer, S., Tschiatschek, B., Flamm, C., Hofacker, I. L., and Findeiß, S.  Rnablueprint: flexible multiple target nucleic acid sequence design.  _Bioinformatics_ , 33(18):2850–2858, 2017.
  * Hofacker et al. (1994) Hofacker, I., Fontana, W., Stadler, P., Bonhoeffer, S., Tacker, M., and Schuster, P.  Fast Folding and Comparison of RNA Secondary Structures.  _Monatshefte fuer Chemie/Chemical Monthly_ , 125:167–188, 02 1994.
  * Im et al. (2019) Im, J., Park, B., and Han, K.  A generative model for constructing nucleic acid sequences binding to a protein.  _BMC genomics_ , 20(13):1–13, 2019.
  * Iwano et al. (2022) Iwano, N., Adachi, T., Aoki, K., Nakamura, Y., and Hamada, M.  Generative aptamer discovery using raptgen.  _Nature Computational Science_ , 2(6):378–386, 2022.
  * Kim et al. (2010) Kim, N., Izzo, J. A., Elmetwaly, S., Gan, H. H., and Schlick, T.  Computational generation and screening of rna motifs in large nucleotide sequence pools.  _Nucleic acids research_ , 38(13):e139–e139, 2010\.
  * Kleinkauf et al. (2015) Kleinkauf, R., Houwaart, T., Backofen, R., and Mann, M.  antaRNA–Multi-objective inverse folding of pseudoknot RNA using ant-colony optimization.  _BMC bioinformatics_ , 16(1):389, 2015.
  * Kohlberger & Gadermaier (2022) Kohlberger, M. and Gadermaier, G.  Selex: Critical factors and optimization strategies for successful aptamer selection.  _Biotechnology and Applied Biochemistry_ , 69(5):1771–1792, 2022.
  * Lee et al. (2021) Lee, G., Jang, G. H., Kang, H. Y., and Song, G.  Predicting aptamer sequences that interact with target proteins using an aptamer-protein interaction classifier and a monte carlo tree search approach.  _PloS one_ , 16(6):e0253760, 2021.
  * Lorenz et al. (2011) Lorenz, R., Bernhart, S. H., Höner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P. F., and Hofacker, I. L.  Viennarna package 2.0.  _Algorithms for Molecular Biology_ , 6(1):26, Nov 2011.  ISSN 1748-7188.
  * Mironov et al. (2002) Mironov, A. S., Gusarov, I., Rafikov, R., Lopez, L. E., Shatalin, K., Kreneva, R. A., Perumov, D. A., and Nudler, E.  Sensing small molecules by nascent rna: a mechanism to control transcription in bacteria.  _cell_ , 111(5):747–756, 2002.
  * Parker-Holder et al. (2022) Parker-Holder, J., Rajan, R., Song, X., Biedenkapp, A., Miao, Y., Eimer, T., Zhang, B., Nguyen, V., Calandra, R., Faust, A., Hutter, F., and Lindauer, M.  Automated reinforcement learning (autorl): A survey and open problems.  _Journal of Artificial Intelligence Research (JAIR)_ , 74:517–568, 2022.
  * Runge et al. (2019) Runge, F., Stoll, D., Falkner, S., and Hutter, F.  Learning to design RNA.  In _International Conference on Learning Representations_ , 2019.
  * Taneda (2010) Taneda, A.  Modena: a multi-objective rna inverse folding.  _Advances and Applications in Bioinformatics and Chemistry_ , pp. 1–12, 2010.
  * Tuerk & Gold (1990) Tuerk, C. and Gold, L.  Systematic evolution of ligands by exponential enrichment: Rna ligands to bacteriophage t4 dna polymerase.  _science_ , 249(4968):505–510, 1990.
  * Vorobyeva et al. (2018) Vorobyeva, M. A., Davydova, A. S., Vorobjev, P. E., Pyshnyi, D. V., and Venyaminova, A. G.  Key aspects of nucleic acid library design for in vitro selection.  _International journal of molecular sciences_ , 19(2):470, 2018.
  * Wachsmuth et al. (2012) Wachsmuth, M., Findeiß, S., Weissheimer, N., Stadler, P. F., and Mörl, M.  De novo design of a synthetic riboswitch that regulates transcription termination .  _Nucleic Acids Research_ , 41(4):2541–2551, 12 2012.  ISSN 0305-1048.
  * Zhou et al. (2015) Zhou, Q., Xia, X., Luo, Z., Liang, H., and Shakhnovich, E.  Searching the sequence space for potent aptamers using selex in silico.  _Journal of chemical theory and computation_ , 11(12):5939–5946, 2015.

##  Appendix A Data

Table 3: Overview of the training and validation sets.
Data Set | Tasks | Mean Length | Median Length | Min/Max Length
---|---|---|---|---
Training1 (“long”) | 100000 | 470.9 | 300 | 200–8033
Training2 (“short”) | 100000 | 103.9 | 99 | 23–200
Training3 (“random”) | 100000 | 142.7 | 106 | 23–6361
Validation | 100 | 135.8 | 94 | 46–1802

Following Runge et al. (2019), we generate training data from the Rfam
database version 14.1 by folding all sequences using _RNAfold_. We build three
training sets of 100000 samples each with different length distributions, and
a non-overlapping validation set of 100 samples. The datasets are described in
Table 3. Instead of specifically training for the task of inverse RNA folding
by masking the sequences of the samples only, we first mask up to five parts
of the structures, each covering up to 20% of the total length, while the
positions, the lengths, and the number of parts are sampled uniformly at
random. In the second step, we mask corresponding parts of the sequences that
remain unmasked in the structures to derive tasks of alternating sequences and
structure constraints. Finally, we randomly mask the sequences of $\sim$20% of
the samples to derive tasks that correspond to RNA design from arbitrary
sequence and structure parts. Examples of the resulting training tasks are
shown in Table 4.

Table 4: Examples of different tasks in the training data.
Task Description | Task Space | Example | Percentage of Data
---|---|---|---
Inverse RNA Folding | Structure | ...........((((....))))...... | 11,5
Sequence | ?????????????????????????????
Alternating Constraints | Structure | ?....???.?.((((...??????????? | 66,7
Sequence | C????UAU?C????????UCAGAUAAAAC
Random Masking | Structure | ?....???.?.((((...??????????? | 21,8
Sequence | C????U?U?C????????UCAGA????AC

##  Appendix B Meta-Optimization

We use an automated deep reinforcement learning (AutoRL) approach that
automatically selects the best RL setting for _libLEARNA_ , given a rich
configuration space as proposed by Runge et al. (2019). In particular, we use
a meta-optimization process to jointly optimize the formulation of our RL
algorithm: in the outer loop, the meta-learner iteratively samples a
configuration that defines an RL algorithm, which is then used to learn an RNA
design policy in the inner loop. The resulting policy is evaluated on a
validation data set and the meta-learner observes the validation loss to
update its own model accordingly. The meta-optimization loop for _libLEARNA_
is illustrated in Figure 2.

Figure 2: Meta-optimization loop. In each iteration, the meta-learner samples
a configuration from a rich configuration space. The sampled configuration
defines the learning algorithm’s hyperparameters, a specific environment, a
particular network architecture of the agent, a training curriculum, and a
training data set. These components together formulate the learner; a deep
reinforcement learning algorithm, which is trained on the selected training
set and evaluated on a validation set. The resulting validation loss is
communicated to the meta-learner to update its model, seeking to learn to
sample better configurations with each iteration.

For _libLEARNA_ , we mainly adopt the configuration space proposed by Runge et
al. (2019) but introduce four novel dimensions, described in the following.

#### Action Semantics

Inverse RNA folding algorithms typically benefit from directly predicting
Watson-Crick base pairs at paired sites. For _libLEARNA_ , however, many
paired sites are not trivially distinguishable and we included a dimension via
the _action semantics_ parameter to either use direct prediction of pairs or
not, to potentially exploit predictions of non-Watson-Crick base pairs.

#### Training Data

The choice of training data and the schedule of the tasks during training can
have a strong impact on the final performance of the learning algorithm. We,
therefore, include two dimensions to choose from different training data
distributions (_training data_ parameter) and curricula (_curriculum_
parameter).

#### Individual State Composition

The predictions of the RL agent are based on the presented states. While the
formulation of individual states in Runge et al. (2019) was based only on the
provided target structure, we decide to add a choice to formulate states that
provide the agent with information about its own decisions. We use the _state
composition_ parameter $\sigma$ to choose either to define states based on the
target task or to define states using the design process of the agent
(updating the representation at each time step).

Overall, our design choices yield an 18-dimensional configuration space,
encompassing a broad range of neural architectures to formulate the agent
(including elements of recurrent neural networks (RNNs) and convolutional
neural networks (CNNs)), a variety of different environment formulations,
three distinct training data distributions, two training curricula, and
training hyperparameters. The complete list of parameters, their types,
ranges, and the priors we used over them as well as the final selected
configuration of _libLEARNA_ are listed in Table 5.

Table 5: Configuration space and finally selected parameters of _libLEARNA_. Parameter Name | Type | Range | Prior | libLEARNA
---|---|---|---|---
state radius $\kappa$ | integer |  [$0$, $32$] | uniform | 10
individual state composition $\sigma$ | categorical | [“target”, “design”] | uniform | “target”
action semantics | categorical | [“pair”, “single”] | uniform | “pair”
reward exponent $\alpha$ | float |  [$1$, $12$] | uniform | 10.76
filter size in $1^{\text{st}}$ conv layer | integer | $\\{0\\}\cup\\{3,\,5,\,\ldots,\,17\\}$ | uniform | 0
filter size in $2^{\text{nd}}$ conv layer | integer | $\\{0,\,3,\,5,\,7,\,9\\}$ | uniform | 0
# filter in $1^{\text{st}}$ conv layer | integer |  [$1$, $32$] | log-uniform | 17
# filter in $2^{\text{nd}}$ conv layer | integer |  [$1$, $32$] | log-uniform | 24
# LSTM layers | integer |  [$0$, $3$] | uniform | 0
# units in every LSTM layer | integer |  [$1$, $64$] | log-uniform | 20
# fully connected layers | integer |  [$1$, $2$] | uniform | 2
# units in fully connected layers | integer |  [$8$, $64$] | log-uniform | 12
embedding dimensionality | integer |  [$0$, $21$] | uniform | 17
batch size | integer |  [$32$, $256$] | log-uniform | 247
entropy regularization | float |  [$1\cdot 10^{-7}$, $1\cdot 10^{-2}$] | log-uniform | $4.46\cdot 10^{-7}$
learning rate for PPO | float |  [$1\cdot 10^{-6}$, $1\cdot 10^{-3}$] | log-uniform | $5.9\cdot 10^{-4}$
training data | categorical | [“random”, “short”, “long”] | uniform | “short”
training curriculum | categorical | [“random”, “sorted”] | uniform | “sorted”

##  Appendix C Improvement Steps

_LEARNA_ employs a local improvement step (LIS) to exhaustively search over
neighboring sequences if the agent is close to a solution for a given task to
account for the stochasticity of the agent. We adopt this procedure to improve
the structure loss for a given task. During evaluations, we add a desired GC-
content to the task. We, therefore, develop a GC-improvement step (GIS) to
guide the agent, either increasing or decreasing the GC content of the
designed sequence by replacing nucleotides at random positions with their
respective counterparts (either A or U by G or C if the GC-content is too low,
or vice-versa). The GIS becomes active whenever the LIS becomes active and
changes to the sequence are only applied if the structure loss is at least as
low as before the GIS.