RNA Secondary Structures with Limited Base Pair Span: Exact Backtracking and an Application.

Area of Science:

• Computational biology
• Bioinformatics
• Molecular biology

Background:

• RNA secondary structure prediction accuracy is limited by base pair span.
• Existing dynamic programming algorithms offer span-restricted folding but often approximate global optimality.
• The ViennaRNA package lacked a tool for optimal, span-restricted minimum energy RNA structure prediction.

Purpose of the Study:

• To develop an efficient algorithm for reconstructing globally optimal RNA secondary structures with span restrictions.
• To integrate this algorithm into the ViennaRNA package.
• To enable the identification of hyper-stable structural elements within genomic sequences.

Main Methods:

• Developed an efficient backtracking algorithm to reconstruct globally optimal structures from locally optimal fragments.
• Integrated the algorithm into the ViennaRNA package, modifying RNALfold's forward and backtracking recursions.
• Constrained recursions to structural components with significantly negative z-scores to identify stable elements.

Main Results:

• Successfully implemented an algorithm for optimal, span-restricted RNA structure prediction.
• Demonstrated the ability to identify hyper-stable structural elements using constrained recursions.
• Observed a higher abundance of these features in the *C. elegans* genome compared to shuffled background models.

Conclusions:

• The new algorithm overcomes limitations in predicting globally optimal, span-restricted RNA secondary structures.
• This advancement facilitates the discovery of biologically relevant, hyper-stable RNA motifs.
• The findings suggest that specific sequence compositions contribute to the stability of RNA structures in genomes.