ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs

Area of Science:

• Bioinformatics
• Computational Biology
• Structural Biology

Background:

• Comparing structural RNAs is computationally intensive.
• Existing methods like ExpaRNA require known RNA structures, which are often unavailable or computationally unreliable to predict.
• There is a need for efficient RNA comparison methods that do not rely on pre-determined structures.

Purpose of the Study:

• To develop a novel algorithm, ExpaRNA-P, for identifying sequence-structure motifs in RNA.
• To enable simultaneous RNA matching and folding, overcoming limitations of existing methods.
• To create a faster and more flexible RNA alignment approach, ExpLoc-P.

Main Methods:

• ExpaRNA-P computes sequence-structure motifs within Boltzmann-distributed structure ensembles of RNAs.
• Employs a novel structure ensemble-based sparsification technique to achieve quadratic time and space complexity.
• A generalized chaining algorithm identifies compatible motif subsets, feeding into the ExpLoc-P alignment tool.

Main Results:

• ExpaRNA-P achieves quadratic time and space complexity, significantly improving efficiency over previous methods.
• ExpLoc-P, utilizing ExpaRNA-P, demonstrates comparable accuracy to state-of-the-art tools like LocARNA but is 4x faster.
• ExpLoc-P shows over 30-fold speed-up for longer RNA sequences (approx. 400nt) and offers adaptable variants for specific applications.

Conclusions:

• ExpaRNA-P's ensemble-based sparsification enables efficient and high-quality RNA sequence-structure alignment.
• The derived ExpLoc-P tool provides a substantial speed advantage for RNA comparison.
• The ExpaRNA-P and ExpLoc-P methods offer versatile solutions for diverse RNA analysis scenarios.