A faster algorithm for simultaneous alignment and folding of RNA.

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Biology

Background:

• Pairwise RNA structural alignment is crucial for understanding RNA function and evolution.
• Current algorithms, like Sankoff's, are computationally expensive (O(N^6) time, O(N^4) space), limiting their practical application.
• Existing heuristics often compromise accuracy or impose restrictive assumptions on RNA substructures.

Purpose of the Study:

• To develop a computationally efficient, non-heuristic method for pairwise RNA structural alignment.
• To improve upon the time and space complexity of Sankoff's dynamic programming algorithm without sacrificing optimality.
• To provide a practical solution for aligning longer RNA sequences.

Main Methods:

• Development of a novel dynamic programming approach for RNA secondary structure alignment.
• Theoretical analysis of the algorithm's expected time complexity under a standard polymer folding model.
• Empirical validation through simulations on RNA sequences of varying lengths.

Main Results:

• The new algorithm achieves an expected time complexity of O(N^4)sigma(N), representing a significant improvement over Sankoff's O(N^6).
• Simulations demonstrated speedups of 3-12 fold for RNA sequences ranging from 25 to 250 nucleotides.
• The method maintains the optimality of the alignment process, avoiding heuristic compromises.

Conclusions:

• The developed algorithm offers a practical and efficient alternative for pairwise RNA structural alignment.
• This advancement enables more extensive comparative analyses of RNA structures and functions.
• The availability of code and data facilitates further research and application in RNA bioinformatics.