DNA Sticker System in JavaScript

DNA Extended Sticker System in JavaScript

Parameters and Functions

Parameters

The operation of the JavaScript Extended Sticker system depends on following parameters (mostly upwards compatible with the Simple Sticker Simulator):

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 Also, the extended simulator allows a format specifier of "" to display the internal S3 string used as the internal representation of stickers and staples in the Extended Sticker Simulator.
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, and of the new extended sticker operations (see my DNA 19 paper), 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. As a kludge, this is also used to implement setweak.
clear (i,k) : clear bit k of every strand contained in tube number i. Do nothing if the tube is empty. As a kludge, this is also used to implement clearweak.
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.
staple1(t0,i,j,t1) staple the strands from tube number t0 whose bit i is zero onto strands from tube number t1 whose bit j is zero at random. Two versions of staple are needed by JavaScript; in actual DNA a single staple operation covers both cases. This one is used when i is on the right and j is on the left of the substrands in question (as in the example i=_BA, j=BA_).
staple2(t0,i,j,t1) staple the strands from tube number t0 whose bit i is zero onto strands from tube number t1 whose bit j is zero at random. Two versions of staple are needed by JavaScript; in actual DNA a single staple operation covers both cases. This one is used when i is on the left and j is on the right of the substrands in question (as in the example i=BA_, j=_BA).
split(i,j) transfer half of the strands from tube number j into tube number i at random.
splitDeterministic(i,j) transfer every other of the strands from tube number j into tube number i.
discard(i) : The contents of tube number i are destroyed.

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.
initCustomS5(i,v,s5) : Custom initialization inserts a single strand, whose value k-bit value is v, into tube number i. on a virtual strand whose 5'..3' string is S5. Only the bits (represented as chars) that are within the set provided in s5 are actually set by copying the appropriate char into s3. Useful for creating substrands of the extended sticker system (rather than the full strands of the simple sticker system). Note: the stickers are represented by lower-case chars limiting the number of bits to 26; Staples are represented by two corresponding upper-case chars.
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.
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.The extended sticker system also allows "" to show the S3 string that represents the sticker and staple bits.

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.

Xor Example

The original 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. This also is available here as "Xor examp"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.

Log-Time Summation Example

My DNA 19 paper gives an algorithm to compute the summation of a set of substrands. This also is available here as "Sum examp". For simplicity of implementation, several of the functions, like fulladd(), fixstrays() and iteration() are in the loaded webpage. Only the dynamic binding of critical variables and the calls to these functions are loaded when you hit the "Sum examp". Use view source on your browser to see the full source code.

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