Random generation of RNA secondary structures according to native distributions

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Random biological sequences are crucial for distinguishing biological information from background noise in genome analysis.
• Generating random sequences and complex structures like RNA molecules and proteins is an area of significant research interest.

Purpose of the Study:

• To present a general framework for non-uniform random generation of combinatorial objects using stochastic context-free grammars.
• To develop an algorithm for generating RNA secondary structures with realistic distributions based on real-life data.

Main Methods:

• Extends the recursive method for uniform random generation using admissible specifications of combinatorial classes.
• Introduces weighted combinatorial classes for non-uniform generation via unranking.
• Utilizes a detailed context-free grammar to model RNA secondary structures, including known motifs.

Main Results:

• Achieves a worst-case time complexity of O(m*n*log(n)) for generating m random RNA secondary structures of size n, an improvement over typical O(m*n^2) algorithms.
• The method employs integer arithmetic, enhancing speed and avoiding floating-point precision issues.
• Preprocessing step requires O(n^2) time for computing weighted class sizes.

Conclusions:

• Experimental results demonstrate that the random generation method produces realistic RNA secondary structures, particularly regarding motif appearance.
• The algorithm is accessible as a web service and available for download, supporting various RNA types.