SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• RNA sequencing reveals numerous novel non-coding RNAs (ncRNAs).
• Accurate simultaneous alignment and folding of ncRNAs is computationally intensive.
• Existing fast methods rely on sequence heuristics, failing below 60% sequence identity.

Purpose of the Study:

• Introduce a novel Sankoff-style algorithm, SPARSE, for RNA structure prediction and alignment.
• Achieve quadratic time complexity without sequence-based heuristics.
• Improve accuracy for low sequence identity RNA alignment.

Main Methods:

• Developed SPARSE (Sparsified Prediction and Alignment of RNAs based on their Structure Ensembles).
• Employed strong sparsification based on RNA structural properties for efficiency.
• Integrated lightweight energy computation for further speed-up.

Main Results:

• SPARSE achieves quadratic time complexity, a significant improvement over previous methods.
• SPARSE demonstrates similar alignment and better folding quality than LocARNA with a 3.7x speedup.
• SPARSE aligns low sequence identity RNAs more accurately than RAF at similar runtimes.

Conclusions:

• SPARSE offers a computationally efficient and accurate solution for RNA structure prediction and alignment.
• The algorithm overcomes limitations of sequence-based heuristics for divergent RNA sequences.
• SPARSE enables more reliable analysis of novel ncRNAs identified through RNA-Seq.