# An Intelligent Grammar-Based Platform for RNA H-type Pseudoknot Prediction

Evangelos Makris, Angelos Kolaitis, Christos Andrikos, Vrettos Moulos, Panayiotis Tsanakas, Christos Pavlatos

► To cite this version:

Evangelos Makris, Angelos Kolaitis, Christos Andrikos, Vrettos Moulos, Panayiotis Tsanakas, et al. An Intelligent Grammar-Based Platform for RNA H-type Pseudoknot Prediction. 18th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Jun 2022, Herissos, Greece. pp.174-186, 10.1007/978-3-031-08341-9_15. http-05335643

HAL Id: hal-05335643

https://inria.hal.science/hal-05335643v1

Submitted on 28 Oct 2025

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 Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# An Intelligent Grammar-Based Platform for RNA H-type Pseudoknot Prediction

Evangelos Makris<fnref n="1" />, Angelos Kolaitis<fnref n="1" />, Christos Andrikos<fnref n="1" />, Vrettos Moulos<fnref n="1" />(✉), Panayiotis Tsanakas<fnref n="1" />, and Christos Pavlatos<fnref n="2" />

**Abstract.** Predicting the secondary structure of RNA sequences has been proved quite a challenging research field for bioinformatics. Predicting structures that encapsulate the pseudoknot motif highlights why it is an NP-complete problem. In this setting, researchers focus on accurately predicting this motif and its variations by leveraging heuristic methodologies that converge while decreasing the prediction time. Any accurate heuristic does not add significant value when it involves an extended execution period, specifically considering lengthy sequences. In this work, we introduce a novel, time-efficient method that employs grammar attributes, parallel execution, and pruning techniques to create an efficient prediction tool that is helpful for biologists, bioengineers, and biomedical researchers. This version of the proposed framework features a pruning technique to reduce the search space of the grammar. It eliminates trees derived from corner-case conditions to reduce execution time by 33% regarding the grammar-based methodology and 43% regarding the brute-force approach without sacrificing the initial accuracy percentage.

**Keywords:** RNA secondary structure · Pseudoknot · Syntactic pattern recognition · Context-free grammars

## 1 Introduction

RNA is the intermediate stage during the transition from DNA to proteins, consisting a significant factor in a variety of biological processes. The effect of RNA in protein synthesis, gene expression regulation, site recognition and catalysis illustrates its importance and attracts researchers from a wide range of scientific fields. Considering its valuable effect in these processes, many studies focus on its structural analysis, and specifically in a 2-D representation, which is called secondary structure. The prediction of this secondary structure is also

<footnote n="1">¹ School of Electrical and Computer Engineering, National Technical University of Athens, 9 Iroon Polytechniou Street, 15780 Athens, Greece</footnote>

<footnote>`{vmakris,akolaitis,vrettos}@mail.ntua.gr, candrikos@cslab.ece.ntua.gr, panag@cs.ntua.gr`</footnote>

<footnote n="2">² Hellenic Air Force Academy, Dekelia Air Base, 13671 Acharnes, Athens, Greece
christos.pavlatos@hafa.haf.gr</footnote>
the core concept of this work. Even if the function of RNA is mainly depended on its 3-D or tertiary structure, the transformation of a primary structure of a molecule, which is a set of A(Adenine), U(Uracil), G(Guanine) and C(Cytosine) bases to a tertiary representation is a very difficult task. In that context, the intermediate secondary structure plays an important role in the prediction of an accurate and reliable tertiary structure prediction. Thus, the secondary structure of a molecule, which is a set of base pairing (A-U, C-G, G-U pairs) and the correct prediction of these pairs, is vital for the enlightenment of RNA operations.

The literature contains a substantial amount of publications dealing with the prediction of RNA secondary structure. Most of the methodologies are based on dynamic programming algorithms, such as Nussinov algorithm that predicts the maximum number of base pairings [44]. This algorithm is dominant but standalone, and it shows a lower prediction accuracy compared with other proposed methodologies in the literature. Secondly, thermodynamic models and specifically Zuker's minimum free energy algorithm is widely used. Zuker's thermodynamic model utilizes dynamic programming enriched by experimental parameters [42,43]. This approach leads to a stable structure with the minimum free energy and presents remarkable results in a variety of datasets. Other approaches incorporate stochastic methods, syntactic pattern recognition techniques, machine learning, other heuristic algorithms or a combination of the above. A detailed analysis of the related work is presented in Sect. 2.

For each secondary structure there is a set of possible motifs that can be formed such as stems, hairpins, bulges, interior loops, multibranch loops and pseudoknots. Nevertheless, the prediction of a pseudoknot motif is the most challenging, considering that only a few algorithms can predict it. The main reason is that dynamic programming and minimum free energy algorithms face difficulties to embrace the interconnection of pseudoknot motif and secondly, that the increase of the length of the molecule leads to an exponential execution time for those methods. Considering these difficulties and the utmost importance of this task, in this paper we present an improved version of Knotify, our intelligent grammar-based methodology of predicting H-type RNA pseudoknots, in terms of execution time using a pruning technique.

Initially, we analyze our dataset, searching for associated attributes in order to minimize the search space. Then, the RNA raw string is parsed via a Context-Free Grammar parser for all trees that include a pseudoknot to be produced in that optimized search space. Next, all trees are traversed to identify additional base pairs around the pseudoknot. Finally, the optimal tree is selected, maximizing the number of base pairs, while minimizing the free energy of the pseudoknot. For the first task, i.e. detecting possible pseudoknots, an alternative methodology is implemented as well using a brute force algorithm.

The proposed methodology does succeed in predicting the core stems of any RNA pseudoknot of test dataset by performing a 76.4% recall ratio. It achieves an F1-score equal to 0.774 and MCC equal 0.437. In [1], the methodology proposed by achieves a performance speed up of 3.45 and 7.75 compared to two well known platforms [6,10] using a dataset of 262 RNA sequences [39]. In this paper,
the proposed methodology facilitates a pruning technique in search space of methodology presented in [1], by eliminating trees in corner conditions, which, in turn, maintains the initial accuracy percentage and at the same time, reduces execution time by 33%. By applying the same pruning methodology at brute force algorithm, an execution time reduction by 43% is achieved.

## 2 Related Work

As mentioned before, a significant number of algorithms utilize dynamic programming techniques, in order to predict the secondary structure with the minimum free energy, such as RNAfold [2], manifold [43]. More specialized approaches for H-type pseudoknot prediction as in [45] has been proposed, focusing on conformational entropy, stability, and the free-energy. Though, considering that the problem is NP-complete [5] and thus, the computational time is increasing exponentially to the molecule's length, stochastic and heuristic methods are deployed to overcome this constraint [7–9]. In that context, Knotty [6] predicts the secondary structure of a variety of RNA motifs including pseudoknots, with CCJ algorithm with sparsification, introducing at the same time a new class of structures called Three-Groups-of-Band (TGB). ProbKnot [11] on the other hand, utilizes the concepts of base pair probabilities and partition function. It computes probabilities of non-pseudoknotted substructures and then creates the secondary structure with the maximum expected accuracy, performing good results in a low runtime. Focusing on accuracy level, IPknot [10] outperforms the above-mentioned approaches using integer programming, specific thresholds and base pair probabilities as optimization techniques.

SCFG-based frameworks have been also proposed in the literature such as Pfold [12, 13], a multi threaded version of that, the PPfold [14], RNA-Decoder [15] and a variety of other implementations (Contrafold [16], Evfold [17], Infernal [18], Oxford [19]), which leverage grammar's advantages. All these approaches embody a machine learning notion, considering that they search for common patterns and similarity measures, while they handle probabilities in their rules. That mathematical background combined with advanced computational methods and optimization algorithms lead to powerful prediction frameworks. Adding, also, information from biological concepts such as minimum free energy, as our framework proposes, we achieved a resilient and efficient grammar based prediction method.

The rise of machine learning has also affected this field of bioinformatics. Many machine learning algorithms have been partially adopted to predict the RNA secondary structure. Some of them focus on the base-pair prediction using deep learning and tertiary constraints [3], while others [22], predicts the secondary structure of RNA sequences, including pseudoknots by leveraging bidirectional-LSTM networks and Improved Base Pair Maximization principle (IBPMP) to choose the appropriate base pairs. Similarly, 2dRNA [20] applies a coupled two-staged deep neural network and a U-net architecture. Its bidirectional LSTM stage performs as an encoder in higher dimensions and in turn, a fully connected
network acts as an decoder, which outputs the dot-bracket structure. Recently, ATTfold [21], an also deep learning framework was proposed, in the direction of predicting the secondary structure of RNA with pseudoknots. This approach encapsulates an attention mechanism, which operates as an encoder to a base pairing score matrix and a convolutional neural network as decoder. The whole system is trained with respect to hard biological rules, in order predict results that comply to basic folding principles.

# 3 Theoretical Background

In this section, basic theoretical issues regarding RNA, pseudoknot structure and parser implementations are analyzed, in order to introduce the reader to necessary basic concepts.

## 3.1 RNA

RNA secondary structure is the basis of various biological processes. By the use of four distinct nitrogenous bases: A (adenine), C (cytosine), G (guanine), and U (uracil), RNA manages to carry genetic information. In contrast to DNA, RNA forms a single-stranded molecule, while its bases bind in pairs known as the standard set of RNA base-pairs: A-U and G-C, which are the Watson-Crick base-pairs [26] and the less regularly showing off G-U wobble-base pairs. Depending on the way and the sequence base-pairs are created, various RNA-folding motifs are formed. The well known RNA-folding motifs are those of loops, kissing loops, bulges, hairpins and pseudoknots. In this paper, the proposed methodology is focused on H-type pseudoknots.

<figure><img src="image_3.png" /><figcaption>Fig. 1. H, L, K and M type of pseudoknots.</figcaption></figure>

**The Pseudoknot Pattern.** One of the most-typical RNA-folding motif is that of the pseudoknot pattern. Pseudoknot motif was initially spotted in the *Turnip Yellow Mosaic virus* [24]. A pseudoknot motif consists of two helical segments that are bound by at least two single-stranded sections or loops. There may be various folding variations forming a pseudoknot motif. However, there are
four main types [23] of pseudoknots known as the H-type, the K-type, the L-type, and the M-type that are shown in Fig. 1. In an H-type pseudoknot [25] the single-stranded RNA sequence folds into an “S” mode in order to construct two tangent loops, each one of arbitrary length.

## 3.2 Syntactic Pattern Recognition

In this paper, the proposed methodology facilitates a pruning technique in grammar's search space of presented methodology in [1]. In [1], the underlying model of the proposed methodology in order to predict H-types pseudoknots in RNA structures is that of Context Free Grammars using syntactic pattern recognition. The basic idea of syntactic pattern recognition is the definition of a language [27] which is a set of syntax rules, that may construct a parse tree having the examined string at the terminal nodes. The set of syntax rules along with a set of vocabulary consists of a grammar that may recognize if a string of symbols is belonging to the defined language or not. Noam Chomsky [28] divided the grammars into four specific classes, that are known as the Chomsky hierarchy. The proposed methodology is based on Context-free grammars (CFG), that are really helpful tools in natural language processing and programming languages [29].

**Context Free Grammars.** A CFG [38] may be defined by the use of four sets (quadruple). Consequently, $CFG = \langle NT, T, R, S \rangle$. Where $S$ ($S \in NT$) is the root of the grammar, which is defined as the start symbol. The terminal symbols of the grammar compose set $T$, while the non-terminal symbols compose set $NT$. Set $R$ consists of the syntactic rules. The syntax rules follow the formalism $K \to \gamma$, where $K \in NT$ and $\gamma \in (T \cup NT)^*$, denoting that non-terminal symbol $K$, can produce string of symbols $\gamma$.

CFG grammars have extensively been used, due to their high expressive capability, hence a considerable number of parsing algorithms have been presented in the literature. Two efficient CFG parsing algorithms are those presented by Cocke, Younger, and Kasami (CYK) [30] and by Earley [31]. Based on these two approaches numerous modified [32–34] and parallel versions [35,36] are proposed in the literature.

In this paper as well as in [1], the proposed system makes use of the most efficient Earley's parser implementation, capable of parsing ambiguous grammars, that of Yet Another Early Parser (YAEP) parser [37].

## 4 Proposed Methodology

In this paper, the proposed methodology facilitates a pruning technique in grammar's search space of the methodology presented in [1]. The proposed methodology as well as the methodology presented in [1] succeed in recognizing RNA H-type pseudoknots following three tasks: (i) construction of all parse trees that
incorporate a pseudoknot by the use of a CFG parser; (ii) traversal of all pro-
duced trees in order to identify additional base pairs around the pseudoknot;
and (iii) selection of the optimal tree by the use of the minimum free energy and
the maximum number of base pairs of the pseudoknot criteria. The goal of the
proposed methodology is to produce a base pairing in an extended dot-bracket
notation given an input string representing an RNA.

The CFG $G_{RNA}$ proposed in [1] is capable of detecting pseudoknots in strings where the first and last symbols of the sequence belong to the core stems group. However, this implies the parsing of subparts of the strings using a sliding-windows technique.

The sliding-windows technique divides the initial input string into substrings,
starting from the one that starts with the first symbol and features the minimum
potential length. Iteratively, the length of the examined substring is augmented
by one symbol to finally include the entire initial RNA sequence. Then, using the
same iterative fashion, starting symbol position is increased by one to exclude
the previous set starting symbol.

Syntactic pattern recognition was chosen, having as future goal to augment
the CFG with attributes, forming in this way an attribute (AG), aiming to aug-
ment system with probabilities and succeed in dynamically prune parse trees.
However, the first task may be implemented using a brute-force algorithm which
will enhance the performance of the presented system. The brute force algorithm
traverses the RNA sequence in order to identify all possible base pairs and then
examines all base pairs in order to locate couples of base pairs, that may poten-
tially be parts of the core stems of a pseudoknot. The proposed methodology aims
to facilitate a pruning technique in both grammar's and brute-force's method-
ology search space of methodology presented in [1]. This space elimination will
affect only the first task of the implementation. The pruning technique is based
on defining two thresholds regarding the minimum and maximum length an
pseudoknot may have regarding the size of the whole RNA sequence. These two
thresholds will be notated as *minimum_percentage* and *maximum_percentage*.
Based on these two thresholds the number of substrings examined during the
sliding-windows technique may dramatically be decreased.

It is implied from the analysis and Figs. 2 and 3 that there is room for
improvement regarding the required time for the identification and description
of the pseudoknot. Leveraging two heuristic thresholds (aka. features) suffice to
improve the time by 33% at grammar based methodology and 43% at brute-
force based methodology without trading accuracy. This finding was unveiled
by observing the benchmark training set's statistical indicators, i.e. probability
density, dispersion of a random variable, and mean value. This initial analysis
highlights that hidden feature correlation could further improve the algorithm's
performance. A dataset [39] of 262 RNA sequences was used in order to esti-
mate the values of *minimum_percentage* and *maximum_percentage* thresholds.
In Fig. 2 the percentage of pseudoknot length in RNA sequence (pseudoknot
length/RNA sequence length) for all 262 RNA sequences is presented. As shown
in this Figure, for all 262 RNA sequences the length of pseudoknot is limited
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Percentage of pseudoknot length in whole RNA sequence</figcaption></figure>

between 32% and 85% of the length of the whole RNA sequence. One may
come to the same conclusion observing the deviation of percentage of pseudo-
knot length in RNA sequence for the same dataset in Fig. 3, where obviously
there is no RNA sequence that has *minimum_percentage* smaller than 32% and
*maximum_percentage* grater that 85%.

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Deviation of percentage of pseudoknot length in RNA sequence.</figcaption></figure>

We argue that the modifications that have been observed can be mitigated
directly through widely adopted AI methodologies. In particular, a) extracting
new features and b) dynamically updating boundaries can be approximated with unsupervised distributed deep learning techniques. This observation can lead to structural changes in how we deal with pseudoknot algorithms for RNA. The DDL-friendly revision of the algorithm(s) will provide new artefacts on how we can deal the context-free grammar (CFG). At the same time, it will allow us to include extra functions and controls that previously were considered deterrents due to complexity limitations. The plethora of sub-cases forced us to re-implement/re-shape the brute-force (type) algorithm/s to deteriorate the search space that keeps growing exponentially to the length of the RNA sequence. To conclude, we envision the presented version (Knotify) to be the core platform where we would add processes, dictionaries and rules. These processes will snap onto the algorithm's platform by following whatever AI technique the researcher thinks is optimal. We argue that by extending and leveraging the features and functionalities that Knotify algorithm is offering, we will surpass the brute-force algorithm and apply it to extra/special cases with minimum changes.

## 5 Performance Evaluation

The same dataset [39] of 262 RNA sequences was used to evaluate our methodology's performance against other methodologies. It is composed of well-known RNA sequences; thus, it should be considered a perfect fit to compare our methodology against other highly respected implementations proposed in the literature, i.e., Hotknots, Iterative HFold (IHFold), IPknot, and Knotty [6, 10, 40, 41].

<table><caption>**Table 1.** Execution time (secs) required per platform in entire dataset.</caption><thead><tr><td>Platform</td><td>Average time</td><td>Total time</td></tr></thead><tbody><tr><td>IHFold</td><td>0.030</td><td>8.096</td></tr><tr><td>Hotknots</td><td>0.169</td><td>44.432</td></tr><tr><td>IPknot</td><td>0.447</td><td>117.246</td></tr><tr><td>Knotty</td><td>1.004</td><td>263.303</td></tr><tr><td>Knotify_yaep</td><td>0.327</td><td>85.756</td></tr><tr><td>Knotify_beuteforce</td><td>0.129</td><td>33.894</td></tr><tr><td>Knotify_yaep_pruned</td><td>0.218</td><td>57.202</td></tr><tr><td>Knotify_beuteforce_pruned</td><td>0.073</td><td>19.377</td></tr></tbody></table>

As mentioned above, the limitation imposed to the sliding-window technique by the use of the *minimum_percentage* and *maximum_percentage* thresholds does not affect the accuracy. The proposed methodology succeed in predicting the core stems of any RNA pseudoknot of test dataset by performing a 76.4% recall ratio and it achieves an F1-score equal to 0.774 and MCC equal 0.437 which is
<table><caption>**Table 2.** Precision, Recall, F1-score, and MCC per platform in entire dataset.</caption><thead><tr><th>Platform</th><th>tp</th><th>tn</th><th>fp</th><th>fn</th><th>Precision</th><th>Recall</th><th>F1-score</th><th>MCC</th></tr></thead><tbody><tr><td>IHFold</td><td>3056</td><td>3556</td><td>1968</td><td>2196</td><td>0.608</td><td>0.582</td><td>0.595</td><td>0.226</td></tr><tr><td>Hotknots</td><td>4180</td><td>3632</td><td>1744</td><td>1220</td><td>0.706</td><td>0.774</td><td>0.738</td><td>0.452</td></tr><tr><td>IPknot</td><td>3872</td><td>3767</td><td>1522</td><td>1615</td><td>0.718</td><td>0.706</td><td>0.712</td><td>0.418</td></tr><tr><td>Knotty</td><td>5026</td><td>3352</td><td>1870</td><td>528</td><td>0.729</td><td>0.905</td><td>0.807</td><td>0.569</td></tr><tr><td>Knotify_yaep</td><td>4212</td><td>4102</td><td>1162</td><td>1300</td><td>0.784</td><td>0.764</td><td>0.774</td><td>0.543</td></tr><tr><td>Knotify_b bruteforce</td><td>4214</td><td>4101</td><td>1160</td><td>1301</td><td>0.784</td><td>0.764</td><td>0.774</td><td>0.543</td></tr><tr><td>Knotify_yaep_pruned</td><td>4212</td><td>4102</td><td>1162</td><td>1300</td><td>0.784</td><td>0.764</td><td>0.774</td><td>0.543</td></tr><tr><td>Knotify_b bruteforce_pruned</td><td>4214</td><td>4101</td><td>1160</td><td>1301</td><td>0.784</td><td>0.764</td><td>0.774</td><td>0.543</td></tr></tbody></table>

the initial accuracy of the methodology presented in [1], as shown in Table 2 as well. Consequently, the metric that was used in order to compare the proposed methodology with other platforms is that of execution time. In Table 1, the execution time required per platform to predict an existing pseudoknot in RNA sequences is provided. The third column of this table depicts the total execution time required by each platform to analyze all 262 RNA sequences, while the second column depicts the average execution time per RNA sequence. In this table the proposed methodologies are shown as Knotify_yaep_pruned and Knotify_b bruteforce_pruned while methodologies presented in [1] are shown as Knotify_yaep and Knotify_b bruteforce. Our methodology outperformed Knotty, which had worse results regarding the core stems prediction and the precision but better results regarding the F1-score and MCC. Knotify_b bruteforce required 33.894 secs; Knotify_yaep required 85.756 secs; Knotify_b bruteforce_pruned required 19.377 secs; Knotify_yaep_pruned required 57.202 secs; and Knotty required 263.303 secs. The proposed methodology knotify_yaep_pruned, achieved a speed up of 33% compared to the Knotify_yaep platform, while the methodology Knotify_b bruteforce_pruned, achieved a speed up of 43% compared to the Knotify_b bruteforce platform. Finally, IHFold recorded the lowest execution time; nonetheless, it had the poorest accuracy-evaluation profile as it is shown in [1]. The execution time required per platform is also shown in Fig. 4.
<figure><img src="image_6.png" /><figcaption>Fig. 4. Average execution time (sec) required per platform.</figcaption></figure>

6 Conclusion

The prediction of RNA secondary structure is a useful tool for field experts to enhance their analysis toolkit and proceed to accurate results and innovative decision making in biology and medicine era. In that context, and considering the need of immediate requirements elicitation and decision making, as it arose from the thread of COVID-19 virus, the minimization of execution time, leveraging computation methods and search space optimization techniques, is of highly importance. To fulfill the above-mentioned crucial and imperative needs, we introduce a time-efficient, grammar-based algorithm and a brute-force one, which prune outlier parsing windows, based on data analysis. These optimized frameworks, eliminate trees in corner conditions, without any reduction in accuracy ratio. Specifically, compared to the initial implementation, we achieve an improvement in execution time by 33% in regards to the grammar-based methodology and by 43% in regards to the brute-force approach.

**Acknowledgement.** The research leading to the results presented in this article has received funding from the European Union's funded Project PolicyCLOUD under grant agreement No. 870675.
References

1. Andrikos, C., Makris, E., Kolaitis, A., Rassias, G., Pavlatos, C., Tsanakas, P.: Kno-
tify: an efficient parallel platform for RNA pseudoknot prediction using syntactic
pattern recognition. Methods Protoc. **5**, 14 (2022)

2. Lorenz, R., et al.: ViennaRNA package 2.0. Algorithms Mol. Biol. AMB **6**, 26 (2011). https://doi.org/10.1186/1748-7188-6-26

3. Singh, J., Hanson, J., Paliwal, K., Zhou, Y.: RNA secondary structure prediction using an ensemble of two-dimensional deep neural networks and transfer learning. Nat. Commun. **10**, 1–13 (2019)

4. Zuker, M.: Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. **31**, 3406–15 (2003). https://doi.org/10.1093/nar/gkg595

5. Akutsu, T.: Dynamic programming algorithms for RNA secondary structure pre-
diction with pseudoknots. Discret. Appl. Math. **104**, 45–62 (2000)

6. Jabbari, H., Wark, I., Montemagno, C., Will, S.: Knotty: efficient and accurate prediction of complex RNA pseudoknot structures. Bioinformatics **34**, 3849–3856 (2018)

7. Van Batenburg, F., Gultyaev, A.P., Pleij, C.W.: An APL-programmed genetic algorithm for the prediction of RNA secondary structure. J. Theor. Biol. **174**, 269–280 (1995)

8. Isambert, H., Siggia, E.D.: Modeling RNA folding paths with pseudoknots: application to hepatitis delta virus ribozyme. Proc. Natl. Acad. Sci. USA **97**, 6515–6520 (2000)

9. Meyer, I.M., Miklos, I.: SimulFold: simultaneously inferring RNA structures includ-
ing pseudoknots, alignments, and trees using a Bayesian MCMC framework. PLoS
Comput. Biol. **3**, 149 (2007)

10. Sato, K., Kato, Y., Hamada, M., Akutsu, T., Asai, K.: IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming. Bioinformatics **27**, 85–93 (2011)

11. Bellaousov, S., Mathews, D.H.: ProbKnot: fast prediction of RNA secondary struc-
ture including pseudoknots. RNA **16**, 1870–80 (2010)

12. Knudsen, B., Hein, J.: RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics **15**, 446–454 (1999)

13. Knudsen, B., Hein, J.: Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. **31**, 3423–3428 (2003). https://doi.org/10.1093/nar/gkg614

14. Sukosd, Z., Knudsen, B., Vaerum, M., Kjems, J., Andersen, E.S.: Multithreaded comparative RNA secondary structure prediction using stochastic context-free grammars. BMC Bioinform. **12**, 103 (2011)

15. Pedersen, J.S., Meyer, I.M., Forsberg, R., Simmonds, P., Hein, J.: A comparative method for finding and folding RNA secondary structures within protein-coding regions. Nucleic Acids Res. **32**, 4925–4936 (2004)

16. Do, C.B., Woods, D.A., Batzoglou, S.: CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics **22**, e90–e98 (2006)

17. Pedersen, J.S., et al.: Identification and classification of conserved RNA secondary structures in the human genome. PLoS Comput. Biol. **2**, e33 (2006)

18. Nawrocki, E.P., Kolbe, D.L., Eddy, S.R.: Infernal 1.0: inference of RNA alignments. Bioinformatics **25**, 1335–1337 (2009)

19. Anderson, J.W.: Oxford: kinetic folding of RNA using stochastic context-free gram-
mars and evolutionary information. Bioinformatics **29**, 704–710 (2013)
20. Mao, K., Wang, J., Xiao, Y.: Prediction of RNA secondary structure with pseudoknots using coupled deep neural networks. Biophys. Rep. 6(4), 146-154 (2020). https://doi.org/10.1007/s41048-020-00114-x

21. Wang, Y., et al.: ATTfold: RNA secondary structure prediction with pseudoknots based on attention mechanism. Front. Genet. 11, 1564 (2020)

22. Wang, L., et al.: DMfold: a novel method to predict RNA secondary structure with pseudoknots based on deep learning and improved base pair maximization principle. Front. Genet. 10, 143 (2019)

23. Kucharík, M., Hofacker, I.L., Stadler, P.F., Qin, J.: Pseudoknots in RNA folding landscapes. Bioinformatics 32, 187-194 (2016)

24. Rietveld, K., Van Poelgeest, R., Pleij, C.W., Van Boom, J., Bosch, L.: The tRNA-Uke structure at the 3' terminus of turnip yellow mosaic virus RNA. Differences and similarities with canonical tRNA. Nucleic Acids Res. 10, 1929-1946 (1982)

25. Staple, D.W., Butcher, S.E.: Pseudoknots: RNA structures with diverse functions. PLoS Biol. 3, e213 (2005)

26. Watson, J., Crick, F.: Molecular structure of nucleic acids. Am. J. Psychiat. 160, 623-624 (2003). https://doi.org/10.1176/appi.ajp.160.4.623

27. Hopcroft, J.E., Ullman, J.D.: Formal Languages and Their Relation to Automata. Addison-Wesley Longman Publishing Co., Inc., Boston (1969)

28. Chomsky, N.: Three models for the description of language. IRE Trans. Inf. Theory 2, 113-124 (1956). https://doi.org/10.1109/TIT.1956.1056813

29. Sipser, M.: Introduction to the Theory of Computation, vol. 2. Thomson Course Technology, Boston (2006)

30. Younger, D.H.: Recognition and parsing of context-free languages in $n^3$. Inf. Control. 10, 189-208 (1967)

31. Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13, 94-102 (1970). https://doi.org/10.1145/362007.362035

32. Graham, S.L., Harrison, M.A., Ruzzo, W.L.: An improved context-free recognizer. ACM Trans. Program. Lang. Syst. 2, 415-462 (1980)

33. Ruzzo, W.L.: General Context-Free Language Recognition. PhD Thesis, University of California, Berkeley, CA, USA (1978)

34. Geng, T., Xu, F., Mei, H., Meng, W., Chen, Z., Lai, C.: A practical GLR parser generator for software reverse engineering. JNW 9(3), 769-776 (2014)

35. Pavlatos, C., Dimopoulos, A.C., Koulouris, A., Andronikos, T., Panagopoulos, I., Papakonstantinou, G.: Efficient reconfigurable embedded parsers. Comput. Lang. Syst. Struct. 35, 196-215 (2009). https://doi.org/10.1016/j.cl.2007.08.001

36. Chiang, Y., Fu, K.: Parallel parsing algorithms and VLSI implementations for syntactic pattern recognition. IEEE Trans. Pattern Anal. Mach. Intell. 6, 302-314 (1984)

37. https://github.com/vnmakarov/yaep, Accessed 25 Mar 2020

38. Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison Wesley, London (2006)

39. https://bit.ly/dataset_pseudobase_knotify, Accessed 3 Jan 2022

40. Ren, J., Rastegari, B., Condon, A., Hoos, H.H.: HotKnots: heuristic prediction of RNA secondary structures including pseudoknots. RNA 11, 1494-1504 (2005)

41. Jabbari, H., Condon, A.: A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures. MC Bioinform. 15, 147 (2014)

42. Zuker, M.: Calculating nucleic acid secondary structure. Curr. Opin. Struct. Biol. 10, 303-310 (2000)

43. Zuker, M.: Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. 31, 3406-3415 (2003)
44. Nussinov, R., Jacobson, A.B.: Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc. Natl. Acad. Sci. USA **77**, 6309–6313 (1980)

45. Cao, S., Chen, S.: Predicting structures and stabilities for H-type pseudoknots with interhelix loops. RNA (New York, N.Y.) **15**, 696–706 (2009). https://pubmed.ncbi.nlm.nih.gov/19237463