DNA Sticker System in JavaScript

DNA Sticker System in JavaScript

Parameters and Functions


The operation of the JavaScript Sticker system depends on following parameters:

k should be greater than or equal to l. These parameters are checked, as appropriate, on each of the sticker functions. If they are not correct, an error message will be printed and the illegal operation does not occur, but in keeping with the laissez-faire philosphy of JavaScript, later code is allowed to proceed.


These are the functions that perform the actual operations of the sticker model, which, in theory, could be implemented with DNA:

The above arguments could be constants, but they could also be JavaScript variables to allow a more generic kind of algorithm (that works on different sized problems), similar to ones in [1-6]. In addition, there are some helper debugging functions (that probably cannot or would not need to be implemented with DNA): The "my" routines are taken from my JavaScript assembler.


There are three specifiers allowed as part of the Fmt parameter, each is preceeded by a width:

The simplest case would be to choose a width equal to k with a single format specifier. Say k is 5 as it is in the example: 5b would show the result in ordinary binary; 5d would show the equivalent decimal.

Complex algorithms, like ones in computer-arithmetic, work with many separate variables, that in the sticker system must be concatenated together in a single strand. Allowing multiple formats allows these to be printed out separately. For example, the Fmt initialized by the "Example" button is 3d2b. This format causes the left-most three bits to be shown in decimal, and the right-most two bits (the "inputs" initialized by init() with l=2) to be shown in binary, with a "_" character between them. The example output for tube 0 shows either 0 or 3 as the decimal numbers computed by each strand followed by "_" and the corresponding binary numbers 00, 01, 10 and 11 provided originally by init():

0:{0_00,3_01,3_10,0_11} 1:{} 2:{} 3:{} 4:{} 5:{}

Note: 0 XOR 1 as well as 1 XOR 0 give 1, which is duplicated to form binary 11 and then printed in decimal as 3.


The JavaScript page provides a small example, which computes the exclusive OR of bits 0 and 1 and duplicates this result in bits 2 and 3. To see this, click on "Example" and then "RUN". The reason the result is put into two bits is to illustrate the use of a JavaScript loop together with the getL() function. The value of getL() will be the next bit position beyond the input bits. The value of that bit position (2 with the default value of l) and the following bit position are set by the loop:

for (i=getL();i<=getL()+1;i++)//javascript loop example
set(1,i); //sets bits l,l+1 (ie2,3)

If you increase the value of l to 3, this code will still work (it might be helpful to choose 2d1b2b as the format to isolate the unused input bit.) The final result tube will contain more strands, but the exclusive OR will be correct in each strand.

Test Code

It might be convenient to write test code that verifies all the strands in a tube have been computed correctly. The removeOneStrand(0) functions allows you to do this by emptying a tube one strand at a time. (Note: The JavaScript for this function does a linear search of all tubes, and is rather slow. It works OK for small l.) For example, if the following code were put just after the display() in the example, it would print true several times, indicating the exclusive OR had been computed correctly in each strand.

var v=removeOneStrand(0);
while (v!=-1)
{ mywriteln(form,((v&1)^((v>>1)&1))==((v>>3)&1)); v=removeOneStrand(0);}

Tube Parallelism

Just like electronic microprocessors have parallel datapath elements (like registers and busses) that can process independent pieces of information in parallel, an automated biochemical processor envisioned by the sticker model might be designed to have parallel tubes that can process independent sets of strands in parallel. In other words, at a given moment in time, separate tubes can have different commands (like set and separate) occuring at the same instant. The requirement is that those commands operate on independent tubes, which is sometimes hard to achieve when designing an algorithm. This idea is discussed in [6], but apparently was not implemented. (We will make the simplifying assumption all parallel operations take the same wall-clock time to complete.)

In order to assist with the design of tube-parallel algorithms, the functions timeStep(deltaTime), getTimeStep() and getTimeViolation() are provided. By default, the JavaScript ignores the tube-parallelism issue, and the example does not consider it. In order to activate this feature, you need to call timeStep(deltaTime) one or more times. (There are analogous features in real-time operating systems and hardware descriptions languages that are similar to timeStep(deltaTime)) Each invocation of timeStep(deltaTime) allocates the specified deltaTime to each tube for completing the operations it is performing in parallel to other tubes. If such a tube continues to be reused more than the number of time steps allocated (i.e. before timeStep(deltaTime) is called again), a timing violation occurs. (Such a violation does not impact the mathematical correctness of the strand results, but it means the algorithm could not execute on a tube-parallel machine.) getTimeViolation() returns the number of timing violations, which ideally should be 0 for a successful tube-parallel algorithm, in which case, getTimeStep() is the speed of the algorithm on a tube-parallel machine. As a small example, the first few commands of the XOR example could be made tube parallel as:

separate(2,0,1); ...

Timing viloations would occur if you omit the second or third timeStep(1) . If you continue to insert timeStep(1) , the algorithm finishes in seven steps (as reported by getTimeStep() ), as opposed to ten (as reported by getTimeSeq() ). Of course, you could achieve no violations by putting timeStep(1) in front of every command, which in effect makes the algorithm tube-sequential, rather than tube-parallel.

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.


[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.