DNA Sticker System in JavaScript

DNA Sticker System in JavaScript

Computing with DNA

Roweis et al. [1] proposed a very simple and elegant, yet universal, model for massively-parallel manipulation of k-bit wide strings (called strands) that are contained in a finite set of containers (called tubes). Here we will assume there are 2**l (power of two) strands. Each strand consists of k >= l bits, where typically the first l bits in each strand start as a unique binary number, and the remaining k - l bits start as zero. The sticker model allows the programmer to modify these bits using a single traditional processor (simulated on this page with eval'ed JavaScript code you may write) to issue a sequence of the following commands to the 2**l strands:

The significant aspect [1-3] of this model is that all of these (except perhaps the clear[2]) could be implemented using robotic biochemical processing with parallelism limited perhaps only by the Avogadro constant. The backbone of each strand is implemented with a long single-stranded DNA molecule, and the distinction between each '0' and '1' in a particular strand is whether a "sticker" (a short complementary DNA molecule designed for a particular bit position) is present at the only place on the long backbone strand where it is designed to stick. As I understand it (and I am new to this so my description may not be perfect), this appears to be feasible [1-2] because the designer chooses k unique patterns of m DNA bases (from the 4**m > k combinations possible with A,C,T,G) that will not stick to each other nor to any other position on the backbone strand (made from m*k bases) except at the desired position (which consists of the Watson-Crick complement of that position's sticker). The simulation here works only at a higher (bit) level of abstraction and does not consider the m bases of the DNA needed for each bit.

Using JavaScript for Sticker Programs

The algorithms for the DNA sticker system originally focused on NP-complete graph problems [1-3]. Recently, there has been interest in developing computer-arithmetic algorithms [4-5] compatible with the sticker system, which raised my curiosity about how the sticker system works. In searching the web, I discovered only two simulation packages that had been developed ([6] and a mention of "StickerSim" in [2]), and neither of these seems to be available currently for download or use. So...in an attempt to learn the sticker system and make a web-based sticker tool generally available, I put this JavaScript together. An interpretive system, like JavaScript, is ideal for quick development of this tool since most of the features of JavaScript are available in your sticker program because of my use of JavaScript's eval() function. ([6] says it required a compiler and runtime system, which is much more involved than this.) All I had to do was implement the above operations (and most difficultly, provide semi-decent output formatting). Of course, as an interpreted system that runs on your web browser, even modest-sized problems will run slowly.

The JavaScript page to run simple sticker code can be accessed here. (The JavaScript page to run extended sticker code, as proposed in my DNA19 paper, can be accessed here. This is upwards compatible to my simple sticker simulator; using Fmt as "" shows the char representation that allows lower-case stickers and upper-case staples to be distinguished.) Some browsers may require you to enable JavaScript before it will run. There are four parameters (k, l, #tubes, and Fmt) you need to provide in addition to valid source code. For a quick example with appropriate parameters and code (which computes the exclusive OR of bits 0 and 1 and duplicates this result in bits 2 and 3), click on "Example" and then "RUN". There are two modes of operation you may toggle with the "List" button (by default the contents of each tube are shown (as formatted by Fmt) after each sticker operation; when listing is off, you may explicitly call display()). Documentation of the parameters and JavaScript sticker functions can be accessed here.

Warning: Like all simple JavaScript applications, this page provides no permanent storage for your program or results. You need to cut and paste into an editor to save them on your machine.

References

[1] Roweis S., et al., "A Sticker-Based Model for DNA Computation," Journal of Computational Biology, vol. 5, pp. 615-629, 1996.

[2] Z. Ignatova, I. Martinez-Perez, and K. Zimmermann, DNA Computing Models, New York Springer, Section 5.3, 2008.

[3] Jin Xu, Yafei Dong and Xiaopeng Wei, "Sticker DNA Computer Model-Part I: Theory," Chinese Science Bulletin vol. 49, no. 8, pp. 772-780, 2004.

[4] Yang X. Q. and Liu Z, "DNA Algorithm of Parallel Multiplication Based on Sticker Model," Computer Engineering and Application, vol. 43, no. 16, pp. 87-89, 2007.

[5] P. Guo and H. Zhang, "DNA Implementation of Arithmetic Operations," Fifth International Conference on Natural Computation, pp. 153-159, 2009.

[6] S. Carroll, "A Complete Programming Environment for DNA Computation," First Workshop on Non-Silicon Computation (NSC-1), Cambridge, MA, pp. 46-53, Feb. 2002.