#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# RNA, dynamic programming, and Feynman diagrams

This seems like the sort of paper that would benefit from some high level perspective, not that I know anything about any of the subjects involved: https://www.sciencedirect.com/science/article/pii/S0022283698924366

• Options
1.
edited June 2018

Hi Reuben, the lab I'm in works on this stuff, and the Dirks et. al paper cited in the paper you linked to came out of our lab. Also this paper reports an $$O(N^5)$$ algorithm for pseudoknots. In practice, some people would like to do this for long sequences, say >5000 bases, and then it starts to become impossible to do these calculations. One thing I have been interested in is quantum algorithms, and pseudoknots are actually one of the problems I thought about because while it is bounded in polynomial time, it's still a bigger polynomial. We know from Grover's quantum algorithm we can reduce search times by a quadratic factor, so pulling this down somewhere near $$O(N^{2.2} )$$ would bring some biologically interesting sequences within range, if the problem can be recast in that way. In general, I am interested in quantum algorithms across biology, and this might be an interesting problem. I would, of course, be interested in what types of insights might be gained by looking at these types of problems through the lens of category theory. At Oxford where you're at you are probably aware that there is a lot of work being done on categories in quantum theory, and John has written a lot about this as well, which is one of the main motivations for me in taking this course (along with direct applications in biology). I'm hoping to better understand quantum algorithms and quantum computation, and I hope category theory can help.

Comment Source:Hi Reuben, the lab I'm in works on this stuff, and the Dirks et. al paper cited in the paper you linked to came out of our lab. Also [this paper](http://www.piercelab.caltech.edu/assets/papers/jcc04.pdf) reports an \$$O(N^5) \$$ algorithm for pseudoknots. In practice, some people would like to do this for long sequences, say >5000 bases, and then it starts to become impossible to do these calculations. One thing I have been interested in is quantum algorithms, and pseudoknots are actually one of the problems I thought about because while it is bounded in polynomial time, it's still a bigger polynomial. We know from Grover's quantum algorithm we can reduce search times by a quadratic factor, so pulling this down somewhere near \$$O(N^{2.2} )\$$ would bring some biologically interesting sequences within range, if the problem can be recast in that way. In general, I am interested in quantum algorithms across biology, and this might be an interesting problem. I would, of course, be interested in what types of insights might be gained by looking at these types of problems through the lens of category theory. At Oxford where you're at you are probably aware that there is a lot of work being done on categories in quantum theory, and John has written a lot about this as well, which is one of the main motivations for me in taking this course (along with direct applications in biology). I'm hoping to better understand quantum algorithms and quantum computation, and I hope category theory can help.
• Options
2.

Comment Source:Awesome, thanks for this reply!