This project finds the theoretical amount of bonds given an RNA sequence.

The image demonstrates the visualization of bonds in the RNA using our DP algorithm.

This algorithm is a dynamic programming approach for predicting RNA sequences' secondary structure. It aims to maximize the number of non-crossing base pairs based on the assumption that the more the base pairs, the more stable the RNA molecule is.

The algorithm uses a 2D matrix to store the number of base pairs for every possible substring of the RNA sequence. The matrix is filled in a bottom-up manner, where each cell (i, j) represents the maximum number of base pairs that can be formed in the substring from index i to j.

The algorithm considers three possibilities to fill each cell:

1. The number of base pairs if the current base pairs with the base at the end of the substring.
2. The number of base pairs if the current base does not pair with any base.
3. The maximum number of base pairs can be formed by bifurcating the substring at any possible position.

The cell is filled with the maximum of these three possibilities. The final solution is present in the cell (0, n-1), where n is the length of the RNA sequence.

The algorithm also includes a traceback procedure to recover the optimal structure.

We ran the algorithm on 5 sequences, and these are the results in comparison with ground truth:

Here, we considered the minimum loop length to be 4, i.e. if adding a bond creates a loop of nucleotides, there must be at least 4 nucleotides between the start and end of the bond.

Here are the main files in the project:

• main.cpp
• rna_folding.cpp

The documentation can be found here.

This project was done with the contributions of

For the course CS F364 (Design & Analysis of Algorithms)