title: Solving satisfiability problems using a novel microarray-based DNA computer.
abstract: 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.
authors.affiliation: Department of Mechanical and Electro-Mechanical Engineering, National Sun Yat-sen University, Kaohsiung 804, Taiwan. chehsin@mail.nsysu.edu.tw
authors.forename: Che-Hsin
authors.initials: CH
authors.lastname: Lin
authors.forename: Hsiao-Ping
authors.initials: HP
authors.lastname: Cheng
authors.forename: Chang-Biau
authors.initials: CB
authors.lastname: Yang
authors.forename: Chia-Ning
authors.initials: CN
authors.lastname: Yang
mesh_terms: 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
chemical_list: D009711:Nucleotides; D004247:DNA