A MEMS Based DNA Computer for Solving SAT Problems

This paper presents a novel MEMS-based DNA computer for solving SAT problems. A modified back-side exposure process and a low-cost fluorescent microscope system for image acquisition are used for the computing experiment such that no time-consuming alignment procedures and delicate sample applying equipment are required for the proposed microarray-based DNA computing. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions and multiple UV exposures during computing processes such that the proposed method shall be useful in dealing with large scale problems. An algorithm based on a modified sticker model accompanied with a state-of-the-art MEMS-based microarray experiment is demonstrated to solve SAT problem which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms need an initial data pool to cover all correct and incorrect answers and further execute a series of separation procedures to destroy the unwanted ones, we built solutions in parts to satisfy one clause in one step, and eventually solve the entire Boolean formula through steps. Accordingly this algorithm greatly reduces the formation of unnecessary candidate solutions and shall be very practical as problem size grows