Predicting secondary structures of RNA folding

This is 100% not the type of post I envisioned starting this blog off with. I kind of just “lucky dipped” my draft backlog of projects and posts. Anyway, here we are. In this post, which I’ll class under computer science, programming, specifically dynamic programming, and bioinformatics, I will introduce the Nussinov-Jacobson algorithm for predicting secondary fold structures of RNA sequences. It is a dynamic programming algorithm and was one of the first developed for the prediction of RNA structures as RNA combinatorics can be quite involved and expensive.

Dynamic Programming

To briefly recap, before looking at the Nussinov algorithm, dynamic programming consists of programming in such a way where one uses past knowledge to make further solving easier, and as a result, reducing complexity. More concisely, we say that dynamic programming, (DP), is a technique used to avoid computing the same thing multiple times for an exponential number of times by breaking a task down into subproblems. It’s a great technique for powerful algorithm design, path-finding problems, and reducing time complexity. My professor once called it “careful bruteforce”. As a side-note, I personally hate the name, and know many others who also do. Sadly, we’re stuck with it.

An example of DP can be shown when computing the Fibonacci sequence. If I asked you to compute fibonacci to the 1 millionth integer… that’s a struggle. What if I gave you the two previous integers? Now it’s just a matter of a single, large, addition.

Continue reading “Predicting secondary structures of RNA folding”