10-04-2017, 07:57 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