Posts tagged dynamic graph layout

I have recently handed in a report as a part of my masters/candidate in Computer Science at University of Copenhagen – “Visualizing blobs and computation in a biomolecular computation model“. It sounds very fancy and I would like to introduce the subject and my report here in hopefully a less dry way than in the report it self. (This post will be in a “anecdotal” style and will not contain citations for all the facts. The report above should be up to academic par on citations)

Biomolecular computers and computation

Biomolecular computers or “biocomputers” is an area that have been research the last 20 years. At first much hype and hope was attached that this would provide some kind of break through to overcome the limitations of normal silica-based chip computers as we know and use today – your average PC and every microchip controlled device around. This is the same hope that surrounds quantum computers – a new approach for doing currently very long computations, for example integer factorization of large prime products within feasible time. The jury is still out on the possibility of biomolecular computing to deliver on that hope/potential. Other research have also shown “niche” interest in the area of “DNA Doctor” usage of biocomputers where a “biocomputer” is implemented to interact directly with the cells in for example humans.

A biomolecular computer can be seen as a computer that  ”.…use systems of biologically derived molecules, such as DNA and proteins, to perform computational calculations involving storing, retrieving, and processing data.“(From wikipedia). Why is this interesting?

First of all: Why not? Tinkering, and playing around with things is interesting IMHO: By drawing the parallel between a biocomputer and a (human) brain you can say that it is a way to learn about ways nature works.

Second of all, a biocomputer will have different properties compared to conventional computers. Some of the first explored ideas was to use DNA interactions to solve very computational hard problems (NP-complete, traveling salesman like problems, Adleman 1994). This is interesting because it is possible to have millions and millions of molecules in lab-tube and thereby allowing for massively parallel computations – compared to a conventional computer which might have 4 (or at least not millions of) cores for parallel computations.

The Blob programming model

When I contacted my supervisor about writing a project this winter I was introduced to “the blob programming model”. At that time it was mostly an article in progress. Just now it has been accepted for the CS2Bio workshop as “Programming in Biomolecular computation” in Amsterdam, June 10, 2010.

The authors, Neil Jones in particular, read lots of the articles around biomolecular computation, turing universality of the models, and formal algebras for describing molecular interactions (Like Kappa calculus and Biochemical Ground Form) but his background as a computer scientist found something missing: Where are the programs?

Lots of interesting computational properties was proven but as a programmer there is no way to write a program as we know it.

Based on that “hole” a machine language was developed and described in the article which might theoretically could be used on a biocomputer. The models was dubbed “The blob programming model” and the article can be found at http://blobvis.appspot.com/blob

My Project – Visualizations of Blob programs

Based on this article I defined a project for doing a literature review of biocomputing literature as well as visualization theory applicable to visualization of blob programs. Normal progrogramming visualizations exists and have been used for many years, but in this case there was a special angle attached to the visualizations. The blob model has a potential physical analog as it might be possible to create a “biomolecular computer” that can execute the instructions and as the instructions is formed to be somewhat like an abstract molecule or similar a visualization of the blob instruction set could/should reveal interesting properties of blob programs with regards to their physical presence.

A program in the BlobVis tool

At http://blobvis.appspot.com my report is available for download as well as the BlobVis visualization tool I developed. From there you can play around with a few simple “Blob Programs”, for example a “list append’” program and see a video of a program executing in BlobVis. As I focused on physical properties the tool uses a physical based algorithm for layouting the blob programs(Via prefuse) which allows you to drag around programs and data in a way that looks like it is immersed in water or similar. That gives an interesting effect and is fun to watch.