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”