Inverse RNA folding, known as RNA design, has been developed since the early 1990’s in a variety of directions and has been applied to diverse applications in biotechnology and RNA research. There is also a citizen science game called eteRNA that introduces RNA design and RNA folding principles to human players with no previous knowledge required. The approach to solve RNA design problems and eteRNA challenges has mostly been centered on a variety of Monte Carlo strategies, but without advanced machine learning except for some data taken from eteRNA human players. Recently, a language model has been proposed to learn a prior on non-human data taken from the RNA families database (Rfam) with RNA folding predictions performed, and thereby improve the performance of a Monte Carlo search strategy. Further, we apply this new approach using the Wolfram language towards the solution of difficult eteRNA challenges and especially the solution of biologically meaningful RNA design problems by improving any Monte Carlo strategy being used, offering initial RNA sequences that are trained by our model instead of random guesses or human-led prior before the mutations start in any Monte Carlo scheme. The language model used for proof of concept is an encoder-decoder transformer neural network architecture. All three components (the Monte Carlo strategy, the language model, and the data) can be further extended for an improved RNA design. In this contribution we focus on extending the language model and the data.
RNA Folding from Sequence to Structure
RNA Folding from Sequence to Structure
The RNA molecule is assembled as a chain of nucleotides an consists of the building blocks “A”, “C”, “G”, “U” (representing adenine, cytosine, guanine, uracil). The primary sequence folds into a secondary structure, which represents the base pairing interactions in two dimensions, before assuming a refined tertiary structure in three dimensions. RNA folding prediction from primary sequence to secondary structure is a classical problem in RNA computational biology, solved by optimization using dynamic programming. One of the first prediction algorithms aimed to maximize the number of base pairs, while the more advanced prediction algorithms aimed to minimize the free energy incorporating energy parameter values derived by biochemists. The most well known prediction algorithms that utilize the latter strategy are mfold, RNAfold, and RNAstructure.
A simple example of RNA folding prediction
A simple example of RNA folding prediction
One of the first algorithms to predict an RNA structure from sequence, developed in the 1970’s by Nussinov et al., computed the maximum base pairings from all possible combinations. Here is a simple illustration of how it works:
[1] Predict the maximum base pairings of an RNA sequence and plot the RNA secondary structure
In[]:=
seq=[BioSequence["RNA","ACUUAGU"],"Expanded"]
Out[]=
{{{2,6},{1,7}}}
In[]:=
BioSequencePlot[BioSequence["RNA","ACUUAGU",Bond/@#]]&/@seq
Out[]=
[2] Determine the number of base pairs under maximum base pairing
In[]:=
Out[]=
2
[3] Plot the RNA secondary structure of a longer sequence that was forced to bond in some way
In[]:=
BioSequencePlot[BioSequence["RNA","CCGCAGUCACACGAGCG",Bond/@{{3,16},{4,15},{6,12},{7,11}}]]
Out[]=
A simple example of calculating the distance between two RNA secondary structures
A simple example of calculating the distance between two RNA secondary structures
A common way to represent an RNA secondary structure is to use the so-called “dot-bracket notation” [1]. Each time there is an unpaired base, it is represented by a dot, whereas each time there is a pairing it is represented by an opening bracket and its corresponding closing bracket. Consequently, one of the simplest ways to measure the distance between two RNA secondary structures (another is the Hamming distance between two dot-bracket strings) is specialized for RNA secondary structures and is called “base pair distance” [1]. It is given by the number of base pairs that occur in one structure, but not in the other. Here is an efficient implementation of the base pair distance that is O(n) where n is the number of bases, using stacks to gain efficiency:
[4] Calculate the base pair distance between two RNA secondary structures
AddToStack[stack_,data_]:=Prepend[stack,data]RemoveFromStack[stack_]:=If[stack==={},0,With[{x=First[stack]},{x,Rest[stack]}]]CalculateBasePairDistance[rep1_,rep2_]:=Module[{sum=0,len1,len2,maxLen,stack={},arr1,arr2,place,i},len1=StringLength[rep1];len2=StringLength[rep2];maxLen=Max[len1,len2];arr1=ConstantArray[-1,maxLen];arr2=ConstantArray[-1,maxLen];(*Processrep1*)Do[If[i<=len1,If[StringTake[rep1,{i}]=="(",stack=AddToStack[stack,i],If[StringTake[rep1,{i}]==")",{place,stack}=RemoveFromStack[stack];arr1[[place]]=i]]],{i,1,maxLen}];(*Resetstackforrep2*)stack={};(*Processrep2*)Do[If[i<=len2,If[StringTake[rep2,{i}]=="(",stack=AddToStack[stack,i],If[StringTake[rep2,{i}]==")",{place,stack}=RemoveFromStack[stack];arr2[[place]]=i]]],{i,1,maxLen}];(*Calculatedistance*)sum=Sum[If[(arr1[[i]]==-1&&arr2[[i]]!=-1)||(arr1[[i]]!=-1&&arr2[[i]]==-1),1,If[arr1[[i]]!=arr2[[i]],2,0]],{i,1,maxLen}];sum](*Testcase*)rep1="((((..))))";rep2="((......))";distance=CalculateBasePairDistance[rep1,rep2];Print["The base-pair distance between ",rep1," and ",rep2," is: ",distance]
The base-pair distance between ((((..)))) and ((......)) is: 2
Armed with a method to predict RNA secondary structure from sequence, and compute distances between two RNA secondary structures, we can move onwards to perform the inverse problem to predict sequences that will fold into a given RNA secondary structure. This is known as RNA design, because we are designing RNA sequences that fold into a given structure.
Inverse RNA Folding from Structure to Sequence (RNA Design)
Inverse RNA Folding from Structure to Sequence (RNA Design)
While the classical problem of predicting structure from sequence can be solved using a deterministic optimization method, by way of dynamic programming, the inverse RNA folding problem from structure to sequences needs a stochastic optimization approach to solve it. It was also shown that inverse RNA folding is a hard computational problem. The first algorithm to solve this problem, know as RNAinverse, was developed in Vienna in the early 90’s [1]. The input is a target secondary structure. RNAinverse starts from an initial sequence that is a random guess. In its main part, Vienna’s RNAinverse predicts the secondary structure of the initial sequence by Vienna’s RNAfold (as mentioned above, mfold/RNAfold/RNAstructure are more advanced dynamic programming algorithms as compared to the RNAFoldingMaximumBasePairing that was illustrated above, and they incorporate energy parameter values derived by biochemists [2]). It then measures the distance between the predicted secondary structure by RNAfold and the target structure, and performs a mutation on the RNA sequence, after which the distance between the predicted secondary structure of the mutated sequence and the target structure is minimized by an iterative procedure (in each iteration, a mutation is performed). The distance to be minimized is commonly measured using Vienna’s RNAdistance, which by default is an edit distance between two full tree representations of the RNA secondary structure, but it can also be measured using the simple base pair distance that was illustrated above. Thus, the ingredients illustrated above, namely a folding prediction algorithm and a distance measure, are what is basically needed in order to solve the inverse RNA folding. In eteRNA, which is a citizen science game with inverse RNA folding challenges, and in most inverse RNA folding methods to date, Vienna’s RNAfold is used for the prediction of structure from sequence and RNAdistance is used to calculate the distance between two RNA secondary structures that needs to be minimized. Historically, RNAFoldingMaximumBasePairing is from the 70’s (with initial works on the RNA folding prediction problem by Waterman and by Nussinov et al.), Zuker’s mfold that markedly improved the predictions by a wide gap and provided a milestone is from the 80’s, Hofacker & Stadler’s RNAfold is from the 90’s, and Mathews’ RNAstructure is from the 2000’s. It should be noted that the predictions of the RNA folding by energy minimization in mfold/RNAfold/RNAstructure are close to each other, and they all use the energy parameter values derived by biochemists [2].
Since the random walk strategy that was mentioned above for RNAinverse (describing it in a simplistic way), many inverse RNA folding methods were developed by various approaches. Commonly, almost all use a Monte Carlo scheme to solve the inverse problem, whether it is a simple random walk as in the original RNAinverse [1] or an advanced Monte Carlo tree search taken from general game playing [3] or a Monte Carlo replica exchange strategy that is a super simulated annealing with different temperatures running all in parallel as in DesiRNA (to be published). In order to improve their initial condition, before this year, instead of starting from a random sequence, researchers have tried improving RNA design by using a stochastic sampling approach (as in incaRNAtion in incaRNAfbinv) or imitating human RNA designers (as in NEMO, to solve eteRNA game challenges). None used machine learning with a larger dataset of natural RNA sequences until this year.
Since the random walk strategy that was mentioned above for RNAinverse (describing it in a simplistic way), many inverse RNA folding methods were developed by various approaches. Commonly, almost all use a Monte Carlo scheme to solve the inverse problem, whether it is a simple random walk as in the original RNAinverse [1] or an advanced Monte Carlo tree search taken from general game playing [3] or a Monte Carlo replica exchange strategy that is a super simulated annealing with different temperatures running all in parallel as in DesiRNA (to be published). In order to improve their initial condition, before this year, instead of starting from a random sequence, researchers have tried improving RNA design by using a stochastic sampling approach (as in incaRNAtion in incaRNAfbinv) or imitating human RNA designers (as in NEMO, to solve eteRNA game challenges). None used machine learning with a larger dataset of natural RNA sequences until this year.
The recent novel approach
The recent novel approach
This year in 2024, a new chapter [3] that will be published in the book at https://link.springer.com/book/9781071640784 presented a unique approach whereby a language model is trained with data coming from the RNA families database (Rfam) in order to improve RNA design. It is shown in [3] that this strategy is improving on the NEMO prior, where NEMO (NEsted MOnte Carlo) is a state-of-the-art method to solve eteRNA game challenges developed in 2018. The data being prepared for the training are natural RNA sequences taken from the RNA families database (Rfam) and their secondary structure prediction is by Vienna’s RNAfold. In this contribution, we have improved the language model presented in [3] and trained with a larger dataset in the Wolfram Language. Moreover, we have come to realize that the approach is more general than learning a prior with a language model and improving on the NEMO prior. This approach, for example, can be used instead of the current initial collection of sequences that provide a starting point to the powerful Monte Carlo replica exchange strategy used in DesiRNA, a state-of-the-art approach in 2024, to improve the RNA design in both solving the most difficult eteRNA game challenges faster and also in finding solutions faster to real-life natural RNA design problems. It can be used to provide a boost to basically any inverse RNA folding solver that is chosen for a particular problem.
The language model
The language model
Here is the step-to-step procedure of how our language model, an encoder-decoder transformer model, is trained:
Importing Dataset and Preparing the Training Dataset
Importing Dataset and Preparing the Training Dataset
In[]:=
dataset=Import["add your file path here..."];
In[]:=
examples=StringSplit[dataset,"\n"];
In[]:=
Length@examples
Out[]=
200000
In[]:=
Length@Union@examples
Out[]=
149694
In[]:=
First@examples
Out[]=
................((((...((((((((((((((((.((((.((..(((((.((((......)))).))))).)).)))).))).......)))))...))))))))..))))..;A A A A A U A G C A A G A A A C CG CG UA GU A A C GC CG GU CG CG CG GC AU UA CG UG CG GU UA CG UG G AU UA CG UG C GU GC A A GU CG UA AU AU G CG AU GC GC G U C C G G / / / / G / / / / / A / / U / / / / G / / / G A C C G C C / / / / / A U A / / / / / / / / U G / / / / C U
◼
Splitting the sequences into “dot-bracket sequence” and “RNA NEMO sequence”:
Shuffling the order of the training pairs:
Converting the sequences into list of tokens:
Adding a start and end token to the RNA sequences:
◼
Longest sequences:
◼
Visualizing one pair of sequences:
We define the encoder vocabulary and its corresponding net encoder as follows:
◼
Adding the start of sequence token “Start” and the end of token sequence “End”:
Encoder-Decoder Transformer with 4 Encoder and Decoder Blocks and 4 Heads of Self-Attention
Encoder-Decoder Transformer with 4 Encoder and Decoder Blocks and 4 Heads of Self-Attention
For explanations of each transformer part you can check the following post: The Encoder-Decoder Transformer Neural Network Architecture
Encoder Block Components
Encoder Block Components
Encoder Stack
Encoder Stack
Decoder Stack
Decoder Stack
Training Net
Training Net
Number of Total Parameters
Number of Total Parameters
Training Process
Training Process
◼
Creating the predictor to generate next tokens:
“Start A GC ........./// A End”
Concluding Remarks
Concluding Remarks
In this project, we re-visited the inverse RNA folding problem to check how a language model can be beneficial to designing RNA sequences that fold to a given RNA secondary structure. Any method to solve this inverse problem requires a stochastic optimization approach and utilizes many calls to the direct problem of predicting RNA secondary structure from sequence . There is also a research direction to try and use machine learning for the direct problem of predicting the secondary structure from sequence, e.g. RNAformer, but because of biases in the data the vast majority of RNA design methods are utilizing a biophysical model like mfold/RNAfold/RNAstructure. In eteRNA, Vienna’s RNAfold is used as the basic model, and methods to solve eteRNA game challenges are calling RNAfold and RNAdistance multiple times, at each iteration.
Language models are powerful in game playing, and the initial idea that started this project inspired by an LLMs/AI workshop in Mathematica was to use large language models to solve eteRNA game challenges. Coincidentally, reference [3] below appeared as a book chapter that uses exactly this concept. Because the input tokens and the output tokens are small in number, a language model is sufficient, and an encoder-decoder transformer model (the vanilla model) can be trained with a dataset of around 150,000 natural RNA sequences taken from the RNA families database (Rfam) along with their predicted folded structure (dot-brackets strings that serve as input, in which the input tokens are an opening bracket “(“ and a closing bracket “)” and a dot “.”). The RNA folding prediction to generate the dataset is performed using RNAfold. Thus, the machine learning is not aiming to replace the RNA folding prediction method from sequence to structure, but rather to enhance the biophysical model being used for that, or any other model used instead for the prediction of structure from sequence. In the game playing community, this is generally known as the scoring function [3]. Thus, a combination of three modular components can be used to solve the eteRNA game challenges: a dataset, a language mode, and a Monte Carlo scheme. Each one of the three modular components can be extended in a way that will result in an improved RNA design. In our project we concentrate on the first two components, namely the dataset from Rfam and the language model, as a pre-processing step before the Monte Carlo scheme. This ensures that the input to the Monte Carlo scheme is much more powerful than any other initial condition to the Monte Carlo scheme. The Monte Carlo scheme can be an advanced Monte Carlo tree search taken from game playing [3], but it can also be a simple Monte Carlo scheme as in the original RNAinverse [1] or a Monte Carlo replica exchange strategy that is a super simulated annealing with different temperatures running all in parallel as in DesiRNA.
Improved RNA design in practically any RNA design tool being used should result with this approach. Difficult eteRNA game challenges that take many hours to solve by a computer can potentially be solved much faster. Moreover, because the language model training is performed with natural RNA sequences taken from Rfam, this approach is especially promising when solving real-life RNA design problems.
Language models are powerful in game playing, and the initial idea that started this project inspired by an LLMs/AI workshop in Mathematica was to use large language models to solve eteRNA game challenges. Coincidentally, reference [3] below appeared as a book chapter that uses exactly this concept. Because the input tokens and the output tokens are small in number, a language model is sufficient, and an encoder-decoder transformer model (the vanilla model) can be trained with a dataset of around 150,000 natural RNA sequences taken from the RNA families database (Rfam) along with their predicted folded structure (dot-brackets strings that serve as input, in which the input tokens are an opening bracket “(“ and a closing bracket “)” and a dot “.”). The RNA folding prediction to generate the dataset is performed using RNAfold. Thus, the machine learning is not aiming to replace the RNA folding prediction method from sequence to structure, but rather to enhance the biophysical model being used for that, or any other model used instead for the prediction of structure from sequence. In the game playing community, this is generally known as the scoring function [3]. Thus, a combination of three modular components can be used to solve the eteRNA game challenges: a dataset, a language mode, and a Monte Carlo scheme. Each one of the three modular components can be extended in a way that will result in an improved RNA design. In our project we concentrate on the first two components, namely the dataset from Rfam and the language model, as a pre-processing step before the Monte Carlo scheme. This ensures that the input to the Monte Carlo scheme is much more powerful than any other initial condition to the Monte Carlo scheme. The Monte Carlo scheme can be an advanced Monte Carlo tree search taken from game playing [3], but it can also be a simple Monte Carlo scheme as in the original RNAinverse [1] or a Monte Carlo replica exchange strategy that is a super simulated annealing with different temperatures running all in parallel as in DesiRNA.
Improved RNA design in practically any RNA design tool being used should result with this approach. Difficult eteRNA game challenges that take many hours to solve by a computer can potentially be solved much faster. Moreover, because the language model training is performed with natural RNA sequences taken from Rfam, this approach is especially promising when solving real-life RNA design problems.
Acknowledgments
Acknowledgments
I would like to thank the Wolfram Research team that contributed to the project: Jofre Espigule-Pons, John McNally, Christopher Wolfram, Christian Pasquel, Maria Sargsyan, Matteo Salvarezza, Phileas Dazeley-Gaist, Mads Bahrami, and Stephen Wolfram. Work was performed in collaboration with Rami Zakh (Ben-Gurion University, Israel), Alexander Churkin (Shamoon College of Engineering, Israel), Hamza Touzani and Tristan Cazenave (LAMSADE, Paris Dauphine University - PSL, CNRS, Paris, France).
References
References
1
.I.L. Hofacker, W. Fontana, P.F. Stadler, L.S. Bonhoeffer, M. Tacker, P. Schuster (1994): Fast Folding and Comparison of RNA Secondary Structures, Monatshefte für Chemie, 125(2): 167-188. https://link.springer.com/article/10.1007/BF00818163
2
.D.H. Mathews, M.D. Disney, J.L. Childs, S.J. Schroeder, M. Zuker, D.H. Turner (2004): Incorporating Chemical Modification Constraints into a Dynamic Programming Algorithm for Prediction of RNA Secondary Structure, Proceedings of the National Academy of Sciences of the United States of America, 101(19): 7287-7292. https://www.pnas.org/doi/full/10.1073/pnas.0401799101
3
.T. Cazenave, H. Touzani (2024): Monte Carlo Inverse RNA Folding, RNA Design, Methods in Molecular Biology, 2847, In Press. https://link.springer.com/book/9781071640784
Cite This Notebook
Cite This Notebook