You may or may not know that this semester for the Choose Ohio First Bioinformatics scholarship I'm working with Andrew on RNA secondary structure prediction. If not, you do now ;) We've looked over some papers, and found a highly referenced work on the topic, a dynamic programming approach. I'm hoping to come back and make a post about the papers we read and specifically about the algorithm we're currently using. We were able to shortcut some steps because there is a provided reference implementation of the algorithm. We're still working on understanding it, but it should prove as a good starting point and potentially as something we might be able to extend. In addition to that, we've decided we would like to have a visualization of the folded RNA. Not just a static visualization, however, but one you can change to see how the overall energy changes

So, where do we start on something like that? Well, there is a pretty popular piece of software named jmol, which has visualisation. However, it has many more features than we need and because of that might be hard to extend. What we want is relatively simple, so right now we're both trying our hand at implementing it. Andrew is trying in java, and I'm doing it in C.

We don't get something that says "the 33rd guanine goes in these coordinates", so we must come up with something ourselves. I thought about it for a little bit, but couldn't come up with anything satisfactory. So, instead I opted to start off with a Feynman diagram form. For this visualization, the chain is laid out in a circle, and bonds between pairs are arcs between them. This is really neat, because it is very easy to see where there are various structures like hairpins and loops. The last few hours was spent hacking away on it, and I've come up with something I think looks pretty neat (and lets you modify the structure, the main purpose!).

This is a slightly modified result of the optimal RNA secondary structure prediction algorithm, to show off more interesting structures. Before, there were some external bases and one loop, not interesting :) This is an actual screen-shot of the program, and the bonding modifications were made inside the program. The next thing I need to have is text rendering, to say what is selected, what is hovered over, and whether or not those can be paired. In addition, there will be a continuous energy rating somewhere. An idea I had is, once you select or hover over a base, background threads can start exploring modified structures based on altering that pair, and then give you "hints" if it finds a structure that is more optimal than what is there presently.

The main reason I wrote this post, though, is the weighted, arbitrary degree Bézier curve drawer I implemented for this. Basically, the arcs showing bonding between bases went through a few iterations. I knew what I wanted them to look like, but that was too complicated to start with. So, it started out as simple straight lines. The next thing I did was to figure out the "distance" around the circle the bases are (allowing jumping over the hole on the right). Then, I created a circle concentric to the backbone whose radius is inversely proportional to the distance between the bonded bases. Then, the point on that circle at the angle that was half way between the two bases was chosen as an intermediary point between the first and second base. Two straight line segments were drawn, connecting these three points. Finally, a weighted Bézier curve drawing function was implemented to interpolate the points with a weight of 1 for the endpoints and 2 for the midpoint. The Wikipedia article portion about the rational form was succinct, but easy to understand. To calculate the (n choose i)'s I simply started at 1 and calculated the next number to the right in Pascal's triangle by the obvious method (multiply by degree minus i, divide by i).