Applications ideas and a resolution

Yall may have noticed the cornucopeia of posty goodness appearing here yesterday. Each of these posts was about an idea for an application built using the Orion API. The client side API is now available on sourceforge (see sidebar under For Developers), as is a set of documentation, guidelines, help, enhancement requests, manual job submission, etc. also linked to in the sidebar under For Developers: Orion web services. Together these two resources are enough to start incorporating state-of-the-art optimization and constraint satisfaction solvers into your applications. Currently we are not connecting the web services to the AQC-based systems, although when we do the programming interface will be identical.

Each of the posts yesterday are about potential applications / applets that range from silly to important commercial applications. The amount of information about how to enable the application also has a wide range, from detailed step by step instructions to vague pointers to papers.

I would love to have folks code real applications around some or all of these ideas (and others too, there are lots!), and that is the real motivation for these posts. We are currently setting up an applications gallery where developers can post applications they have built using Orion web services, share code, and discuss what’s working well and what isn’t. One of the things I am really interested in are mash-ups of Orion and other web services interfaces, such as Facebook and Google offer.

I am going to try to stick to the following resolution: I am going to try to post one applications idea per day for the next year, for a total of 365 applications ideas, starting today. I think there are enough out there to be able to hit this goal… we’ll see!

3 thoughts on “Applications ideas and a resolution

  1. Geordie,

    Beyond protein folding, it would be tremendously useful to have a means of more efficiently solving the NP-complete problem of predicting all classes of pseudoknots in RNA secondary structure (or better yet, calculating secondary structure partition functions involving these pseudoknots).

    “Pseudoknots in RNA secondary structures”
    http://portal.acm.org/citation.cfm?id=332306.332551&coll=&dl=&type=series&idx=SERIES140&part=series&WantType=Proceedings&title=RECOMB
    (There are other papers I’ve seen that also prove NP-completeness)

    Endogenous/viral pseudoknots have been proven to ‘encode’ frameshifts for eukaryotic ribosomes (See ” A mechanical explanation of RNA pseudoknot function in programmed ribosomal frameshifting” in Nature for some beautiful cryoelectron images and a description of how this works). HIV, for example, uses a pseudoknot to redundantly encode proteins in multiple reading frames.

    Pseudoknots also have a critical role in facilitating many protein binding/signaling events, and allowing the proper folding of ribozymes (like HDV, the extended hammerhead), ribonucleoproteins (like telomerase and the ribosome), etc. .

    I have no doubt that there are many many more endogenous and viral pseudoknots yet to be discovered. And beyond the (very) few that have been found, there are probably many more undiscovered regulatory ribozymes lurking in the LTRs of mRNAs. Unfortunately, and although I could be wrong, it sounds like any algorithm to do this on an adiabatic quantum computer (or solve certain sub-problems in conjunction with a classical computation), would be extremely computationally expensive.

  2. Hi KaoriBlue, this sounds like a good place to start looking for a reduction to SAT or quadratic unconstrained binary optimization. Do you know if this has been done, and/or how this problem is solved today? I will look through the papers you’ve referenced. Would you be interested in working together on putting a reduction & application together? We know a lot of reduction tricks but for something like this a lot of biological knowledge is required to know what users ultimately want, what’s important and what isn’t, etc.

  3. Geordie –

    I hope it’s not too late to comment on the applications available. One very useful application would be to use the Tabu search functionality to create globally optimal decision trees.

    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8601

    Decision trees are highly useful in data mining and any predictive system. Their drawback is their reliance on a greedy algorithm that reduces accuracy. A quantum system that was able to generate a globally optimal decision tree would be a very useful tool.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s