[attachment=4986][attachment=4985]

---

This article is presented by:
Ji Yoon Park
Dept. of Biochem
Hanyang University


Abstract

1. Succeeded in solving an instance of a 6-variable 11-
clause 3-SAT problem on a gel-based DNA computer

2. Separation were performed using probes covalently
bound to polyacrylamide gel

3. During the entire computation, DNA was retained
within a single gel and moved via electrophoresis

4. To be readily automatable and should be suitable for
problems of a significantly larger size


I. Introduction


 = (x1∨￢ x2∨￢ x3)∧(x2∨￢ x3∨￢ x4)∧(x3∨￢ x4∨x5) ∧
(x4∨￢ x5∨￢ x6)∧(x5∨￢x6∨￢x1)∧(x6∨￢x1∨￢x2) ∧
(x1∨x2∨x3)∧(x1∨x2∨￢x3)∧ (￢x1∨x2 ∨x3)∧
(￢x1∨x2∨￢x3) ∧(x1∨￢x2∨x3)


 has a unique solution: x1 = x2 = … x6 = true

◈ To represent all possible variable assignments for the chosen 6-variable SAT problem, a Lipton encoding was used
- For each of the 6 variables x1, x2, · · · , x6
- two distinct 15 base value sequences were designed
: true (T) XkT , false(F) XkF
- Each of the 26 truth assignments was represented by a library sequence of 90 bases consisting of the concatenation of one value sequence for each variable.
- DNA molecules with library sequences are termed library strand
- Combinatorial pool containing library strands is termed a library
- The probes used for separating the library strands have sequences complementary to the value sequences
- Errors in the separation of the library strands are errors in the computation
- Sequences must be designed to ensure that library strands have little secondary structure which might inhibit intended probe-library hybridization