Editing CRNs with limited geometry

= Problem context before workshop =

Chemical reaction networks are known to be Turing-universal with probability $1-\epsilon$ (for any $\epsilon>0$) [<ref name="SCWB2008">Soloveichik, D., Cook, M., Winfree, E., & Bruck, J. (2008). Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4), 615-633.</ref>.] CRNs augmented with a constant number of ''stacks'' are Turing-universal <ref name="QSW2011">Qian, L., Soloveichik, D., & Winfree, E. (2011).  Efficient Turing-universal computation with DNA polymers. In DNA computing and molecular programming (pp. 123-140). Springer Berlin Heidelberg.</ref>.   This was demonstrated using a DNA strand displacement system construction that exploited the fact that DNA can easily form ''polymers''.  The stacks in that construction behave as one would expect: a molecule can be added to the top of the stack, can be removed from the top of the stack, and molecules not on the top are not accessible to other reactions. A stack of type $i$ initiates from a special subunit molecule called $\bot_i$. Simplifying details from <ref name="QSW2011" />, this leads to CRN reactions of the form:

$$
\begin{align}
  [\bot_i \ldots X] + Y &\rightarrow [\bot_i \ldots XY]\\
  [\bot_i \ldots XY] + POP_i &\rightarrow [\bot_i \ldots X] + Y
\end{align}
$$

==== Initial context assumption ====

As with many results that demonstrate CRNs capable of complex computation <ref name="SCWB2008" /><ref name="TC2012">Thachuk, C., & Condon, A. (2012). Space and energy efficient computation with DNA strand displacement systems. In DNA Computing and Molecular Programming (pp. 135-149). Springer Berlin Heidelberg.</ref>, the stack machine construction in <ref name="QSW2011" /> assumes that certain molecular species are present in exact initial quantities, in particular there is exactly one copy of each stack.

=== Problem overview & questions ===

What is the power of CRNs augmented with stacks, without the [[initial context]] assumption?  (i.e., the concentrations of stack subunit species, $\bot_i$, are given as part of the input.)  The inspiration of this question can be found in the ability for DNA strand displacement systems to form polymers (complexes consisting of multiple DNA strands bound via hybridization of complementary domains).  While polymers can simulate stacks, they are more general and open up new possibilities for programming CRNs.

Interesting thought experiments in this model may include:

* Beginning from a population of input $X$, can stacks be used to output $\log(|X|)$ copies of an output species $Y$?
* Could consensus of two input species $X$ and $Y$ be computed exactly, and efficiently, with the use of a constant number of stack types?

* What additional computational power, if any, arises when the model is broadened to included:
** double ended stacks / queues
** stacks/queues/polymers that can be efficiently ''concatenated'' with another, at their ends
** polymers that can be efficiently "merged" with another, at multiple locations along the polymer

=== CRNs with complexation/decomplexation ===

In a 2010 paper "Turing universality of the Biochemical Ground Form" Cardelli and Zavattaro define an extension of (an equivalent language to) CRNs with operations of complexation and decomplexation, and show that the extended language (BGF) is Turing universal by emulating a register machine (where registers are stacks). But in BGF stacks are not built-in, and BGF can represent pretty much any complex dynamic polymer with a finite program.

Questions:

* Can this be useful as a formal language (analogously to CRN) to investigate expressibility questions involving polymerization?
* Is there a general DSD implementation of BGF (using DNA's ability to form complexes), the same way there is a DSD implementation of CRN?

= Workshop progress =

=== High level goals ===

* Strand displacement systems can naturally form polymers
* Extend syntax of CRNs to consider polymer molecules
* What can they compute?
* What shapes/patterns (algorithmic) can they form?

=== Extended CRN syntax ===

==== Prior work ====
* DSD <ref name="dsd">Lakin, M. R., Youssef, S., Cardelli, L., & Phillips, A. (2012). Abstractions for DNA circuit design. Journal of The Royal Society Interface, 9(68), 470-486.</ref>

** DSD already handles some polymer classes, focused on DNA strand displacement

* BGF: Biochemical ground form <ref name="bgf">Cardelli, L., & Zavattaro, G. (2008). On the computational power of biochemistry. In Algebraic Biology (pp. 65-80). Springer Berlin Heidelberg.</ref>
* Kappa <ref name="kappa">Danos, V., Feret, J., Fontana, W., Harmer, R., & Krivine, J. (2008). Rule-based modelling, symmetries, refinements. In Formal Methods in Systems Biology (pp. 103-122). Springer Berlin Heidelberg.</ref>

==== Future work ====

'''Desired''': syntax for arbitrary polymers; higher level description of different polymer classes
     .... motivation from CRNs 

Question: what is a an arbitrary polymer structure?

=== Classes of polymers ===

* Linear
** Stacks, queues (and double ended variants)
** Tapes (i.e. like a TM, random access to any monomer in the polymer)

* Circular tapes (anything more than tape?  clockwise TM?)

* Tree shapes

* Arbitrary graphs

=== Computational power of polymer classes ===

'''Question''': what computational power does each class of polymers exhibit, when described as augmented CRNs?

Motivating example: CRNs in a well mixed solution cannot stably compute beyond semi-linear functions.  Can augmented CRNs?

'''Ex''': Tree polymer construction from Luca.  (CHECK.  Construct tree of height $\Theta(\log n)$ in expected time $O(\log n)$.  One spline of tree forms active molecules.  This would effectively compute f(x)=\Theta(\log x ) if correct.  Well mixed CRNs cannot.)


'''Prior work'''
Chen and Dabby, and Malchik and Winslow<ref name="dsd">Caleb Malchik, Andrew Winslow. (2014). Tight Bounds for Active Self-Assembly Using an Insertion Primitive. [arxiv | http://arxiv.org/abs/1401.0359] </ref> work on a polymer model. The latter paper shows that with $k$ DNA hairpin monomer types, we can deterministically construct polymers of length $ 2^{\Theta{(k^{3/2})} } $, quickly; and that the expressive power of these systems is exactly the context free languages.

=== Constructing shapes / patterns with polymer classes ===

'''Question''': Which structures can you build? 

* On a tape, for example, can you build context free grammars, regular expressions,... ?
* Do other classes give more 'context' / power?

=== Tree self-assembly ===

'''Question''': Self-assemble a single tree from uniform components. Then light-up the left spine. How cheaply/fast can we do it? 

* Here is an algorithm and simulation: [[:File:Tree assembly in pi-calculus.pdf]]

= References =

<references/>