18th AIAI 2022, 17 - 20 June 2022, Greece

An intelligent grammar-based platform for RNA H-type pseudoknot prediction

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


  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.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.