Solving satisfiability problems using a novel microarray-based DNA computer.
An algorithm based on a modified sticker model accompanied with an advanced MEMS-based microarray technology is demonstrated to solve SAT problem, which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms needing an initial data pool to cover correct and incorrect answers and further executing 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. No time-consuming sample preparation procedures and delicate sample applying equipment were required for the computing process. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions during computing processes such that the proposed method shall be useful in dealing with large-scale problems.
Lin
Che-Hsin
CH
Department of Mechanical and Electro-Mechanical Engineering, National Sun Yat-sen University, Kaohsiung 804, Taiwan. chehsin@mail.nsysu.edu.tw
Cheng
Hsiao-Ping
HP
Yang
Chang-Biau
CB
Yang
Chia-Ning
CN
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D039301:Computers, Molecular; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry*; D008433:Mathematics; D008957:Models, Genetic; D008962:Models, Theoretical; D008967:Molecular Biology / Q000379:methods*; D009690:Nucleic Acid Conformation; D009711:Nucleotides; D020411:Oligonucleotide Array Sequence Analysis
D009711:Nucleotides; D004247:DNA