Review
Nano Letters
Li, Wei; Yang, Yang; Yan, Hao; Liu, Yan.
"Three-Input Majority Logic Gate and Multiple Input Logic Circuit
Based on DNA Strand Displacement"
Three-input majority logic gates are useful tools in computation;
they work on the principle that if at least 2/3 of the inputs are true,
then the result is true. The result is false if only 1/3 of the inputs
is true. At first glance, this seems like a convenient system for tuning
the on-state of a system for non-binary inputs; theoretically, any odd-number
of inputs can be turned into a majority logic gate.
The true versatility of this system lies
in the fact that it is easy to convert 3-input logic gates into the more
standard OR or AND gates, simply by setting of the inputs as true or
false. If one input is set as true , then either one of the other two (or
both) could be true in order to get a true result. If one input is set
as false, then both the other two must be true to get a true result.
OR and AND gates, and calculations:
In simple terms, OR gates represent
additions. In order for the equation to be true (have a value of at least 1),
the sum of the inputs has to be at least one. Thus, if you have 2 inputs, an OR
gate states that input A OR input B can be zero because 1+0 and 0+1 both end up
having true outputs.
AND gates, on the other hand, represent
multiplications. Since any number multiplied by 0 = 0, in order for the net
output to be TRUE, all of the inputs must be TRUE (in other words, none of the
inputs can be false (0).
The Paper
Wei Li,Yang Yang, Hao Yan, and Yan Liu at
Arizona State University have been able to make these logic gates based on DNA
hybridization properties. The concept of DNA-based logic gates has been around
for many years, and the field is fertile with new developments.
Li et al use a circular piece of single
stranded DNA with 3 different hybridization sequences, corresponding to the 3
inputs of the logic gate. These sequences are flanked by repeating
"joint" sequences that are complementary to a detector sequence.
Finally, this single stranded circular DNA is hybridized to complementary
sequences each bearing a toehold - that is, a segment of DNA that will allow
the strands to be displaced upon binding to input strands that have regions
complementary to the toeholds. The principle of displacement here is 1) the
greater stability of the longer piece of DNA with more base pairing as opposed
to shorter base paired strands (thermodynamic) and 2) the initial binding
efficiency of the input strands is higher with a toehold than without (kinetic).
When two of the inputs are complementary
to the toehold strands, it opens up a joint region that exists between the two
toehold strands. A detector sequence consisting of a double stranded DNA
sequence containing a fluorophore quencher pair (see Molecular Beacon) is then
able to bind the quencher sequence, allowing the fluorophore to fluoresce and
form a turn-on signal. However, when only one input is present, the joint
region is not fully exposed, and fluorophore quenching is maintained.
The researchers expand upon this model to
build more complex logic cascades based on the principle of turning three-input
majority gates into AND and OR gates. A variety of calculations can be
accomplished using just two steps in sequence. To accomplish the presets, one
of the three calculation sequences is present or absent in the reaction mixture
when the input sequence(s) are introduced. The output of the first DNA
calculation takes the form of a double stranded piece of DNA, with one strand
binding to the exposed joint region of the first calculator, and the second
strand binding acting as an input for the second DNA calculator.
In practice, the design of these DNA
calculators is trickier. One design flaw is that the flanking regions to the
recognition parts of the calculator and inputs are the same, causing
non-specific inputs to sometimes bind the calculator strands. This, however,
should not be a problem in the detection, as the fully complementary sequences
are pre-hybridized with the single stranded calculator to form the calculator
DNA.
The calculators work as predicted for the
single gate problem. When the calculator is challenged with 0 or 1 input, no
fluorescence increase is detected, with 2 or 3 inputs, fluorescence is
detected. With a higher ratio of detector strand to calculator DNA, the authors
are able to distinguish well between a 2 and 3 input challenge. This agrees
with the relative molar ratios of exposed joint domains.
For the multi-gate problems some signal
leakage is seen - as fluorescence occurs even for cases where the output should
be false, but in general the system works quite well. The main weakness in
using DNA as a computational tool is time. It takes at least half an hour for a
signal to process, and sometimes hours for it to be processed unambiguously.
The kinetics of the signal formation are also offset by the signal leakage -
the faster a true positive result is able to distinguish itself from a false positive,
the better. The authors attribute slow kinetics to the fact that strand displacement
is likely to occur concomitantly between calculators, causing steric crowding
to limit the rates of the reaction. Signal leakage, on the other hand, is due
to cross talk between the two logical gates. Signal leakage can be optimized
by careful design of the sequences used for the calculators, and by
tuning the concentrations. Rates, on the other hand, are more tricky- a certain
amount of crowding is inevitable, and as calculations get more involved, the
lengths of the DNA used to compute them will get longer in order to decrease
crosstalk. Longer DNA will inevitably lead to slower kinetics. Thus, signal
leakage and speed are at odds with one another, but both need to be optimized
in order to make a feasible DNA computer.
How one might optimize for speed.
In nature, the kinetics of a reaction are
governed by temperature and catalysts. In short, the higher the reaction
temperature, the faster the kinetics. The problem with this strategy is that it
also favors non-specific interactions. In the case of these calculators, higher
temperatures will lead to easier strand displacement and possible false
positives. (For other examples, higher temperatures will increase specificity
in that only the correct sequence will bind).
Another strategy may be to use catalysts.
DNA catalysts take the form of proteins - enzymes in particular, which nature
exploits in order to make the process of gene replication and expression occur
in seconds rather than hours. A helicase that is specific for certain DNA
structures - toehold-strand-breaks for example - may expedite the sensing
processes.
