DNA Sticker System in JavaScript

Parameters and Functions

Parameters

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

l: determines how many strands (2**l) are created by init() and also determines how many bits are initialized with a unique binary pattern in each strand.
k: determines the length of all stands created by init(). Of the k bits, k - l are 0 and the other l are unique at the time of init().
#tubes: how many tubes are available.
Fmt: a format string consisting of one or more repetitions of a width followed by a format specifier (d, b or r), as explained below.
listing mode (changed by toggling the "List" button)

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.

Functions

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

init(i) : initialize tube number i with (2**l) unique strands, each of length k. The first l bits contain a unique binary value for each strand, and the other k - l are 0. Note this is slightly different than algorithms in the literature specifying all three in the source: init(i,k,l). These are interactive here to make it easier to experiment with (see getL() and getK() below).
set(i,k) : set bit k of every strand contained in tube number i. Do nothing if the tube is empty.
clear (i,k) : clear bit k of every strand contained in tube number i. Do nothing if the tube is empty.
separate3(i1,i0,j,k) : Test bit k of every strand in tube number j. Put those whose bit is one into tube number i1; put those whose bit is zero into tube number i0. Unless i1 or i0 is the same as j, tube number j will be empty. This primitive is provided because it is used in [2]; many other references use the separate() function.
separate(i,j,k) : Test bit k of every strand in tube number j. Put those whose bit is one into tube number i; leave those whose bit is zero in tube number j. (Algorithmically, which bit setting stays in the tube is arbitrary, but there seems to be a preference due, to some physical/chemical probe-filtering issue, for leaving zeros in the source tube.)
combine(i,j) transfer all strands from tube number j into tube number i. Tube number j will be empty.
discard(i) : The contents of tube number i are destroyed. This is the only operation in this list that reduces the total number of strands present in the system.

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):

getK() : Returns k to allow generic algorithms that work for various length strands.
getL() : Returns l for the same reason.
getNumTubes() : Returns #Tubes. Probably not as useful as above since most algorithms need a certain number of tubes.
getTubePop(i) : Returns population count of number of strands in tube i. (Maybe could be approximated with actual DNA: Beer's Law or something like that?)
getNumStrands() : Returns the number of strands active in all tubes, i.e., the sum of getTubePop() for all valid tube numbers.
initCustom(i,v) : Custom initialization inserts a single strand, whose value k-bit value is v, into tube number i. Useful for debugging a limited input set.
removeOneStrand(i): Return the first strand found in tube number i, and also remove it from that tube. If there are no strands in the tube, return -1. This is the only operation aside from discard() that reduces strands in the system.
getTube(i) : Returns a string showing the contents of specified tube (according to Fmt)
display() : Shows getTube(i) for all tubes.
listOn() : Turns listing on to debug a portion of code. (Overides button on page)
listOff() : Turns listing off. (Overides button on page)
formatConvert(x,k,fmt) : Converts k-bit value x to formatted string according to supplied fmt argument (not the global one). Useful in conjunction with mywriteln for debugging.
timeStep(deltaTime) : Advances global time step by deltaTime , which needs to be enough time for all tubes to complete the code they are executing in parallel. (See tube parallelism below.) If never called, the time step feature is disabled, and may be ignored.
getTimeStep() : Returns the number of time steps used so far. (See tube parallelism below.)
getTimeSeq() : Returns the number of sequential steps required if tube parallelism is ignored.
getTimeViolation() : Returns the number of timing violations. (See tube parallelism below.)
mywrite(form,string) : Emulates Delphi output to the textbox (stay on same line).
mywriteln(form,string) : Emulates Delphi output to the textbox (makes new line).
mycopy(string,i,j) : Emulates Delphi substring in JavaScript.
mypos(string) , etc.: Emulates Delphi string operations in JavaScript.

The "my" routines are taken from my JavaScript assembler.

Formatting

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

d: Decimal output with no leading zero.
b: Binary output with leading zeros on the left (normal convention).
r: Reversed binary output with leading zeros on the right (several stickers publications follow this convention, which seems confusing to me, at least in the computer-arithmetic context).

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.

Example

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:

timeStep(1);
init(0);
timeStep(1);
separate(1,0,0);
timeStep(1);
separate(3,1,1);
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.

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.

Mark G. Arnold