Invertases are a family of enzymes, each member of which recognizes a pair of oppositely oriented sites, and inverts the DNA segment between them. Such control on the orientation of a DNA segment flanked by appropriate invertase recognition sites has fundamental applications in synthetic bioengineering. For example, the orientation of a segment may be used as a memory element storing a single bit of information, or it may be used to enable or disable transcription of a coding sequence in a synthetic construct.
Previous work in this area includes the memory device by Ham et al., and more recently by Bonnet et al., and the "genetic counter" by Friedland et al. Ham's memory device is unique in that it interleaves recognition sites to obtain a larger state space, with the largest device consisting of five states, including the start state. Ham et al. build the five-state device and present a general design for n sites based on intercalating sites.
In this work, we present algorithms for building two computing structures which we call the Permutron and the Automaton. The permutron is a DNA sequence of arbitrary DNA segments 1, 2, ..., n and distinct invertase recognition sites such that any permutation of the n segments may be obtained by treating the design with a sequence of invertases. The automaton is a DNA sequence such that given a finite set of chemical words, the sequence will produce fluorescence if and only if treated by chemicals of the type and order specified in the set. The permutron extends the Ham construct and the automaton generalizes Friedland's "counter."
Trumpet is a Clotho application that implements some permutron design algorithms. The automaton design algorithms are currently under implementation.
We thank Josh Gilmore (JBEI) for his kind help and Suma Jaini, Andrew Krueger, and J. Christopher Anderson for valuable discussions.