04-10-2010, 04:51 PM
[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