We propose a strategy using tiny beads for DNA computing. DNA computing is a means of solving intractable computation problems
such as NP-complete problems. In our strategy, each bead carries multiple copies of a DNA sequence, and each sequence represents
a candidate solution for a given problem. Calculation in our strategy is executed by competitive hybridization of two types
of fluorescent sequences on the beads. One type of fluorescent sequences represents a constraint that has not been satisfied,
and the other type a constraint that has been satisfied. After competitive hybridization, beads with only the latter type
of fluorescent sequences hold “true” solutions. To extract the beads from the test tube, we use fluorescent-activated cell
sorter.
We describe the approach to DNA computing on beads through SAT problems. The SAT problem is an NP-complete problem in Boolean
logic. Using Megaclone, which allows DNA strands to be attached to beads, we show that DNA computing on beads can solve up
to 24 variables.