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$) [.] CRNs augmented with a constant number of stacks are Turing-universal . 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 , 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 , the stack machine construction in 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

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

• BGF: Biochemical ground form
• Kappa

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