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. The prediction of secondary RNA structures is an interesting and important problem in bioinformatics. This post 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.
Before looking at the Nussinov algorithm, it may be worthwhile recapping some dynamic programming (DP). DP consists of programming in such a way where one uses past knowledge of the problem, to make further solving easier, and as a result, reducing complexity. More concisely, we say that 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 sub-problems. 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 hate the name.
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”