Solution of Satisfiability Problem on a Gel-Based DNA computer
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 projectsofme Active In SP Posts: 1,124 Joined: Jun 2010 04-10-2010, 04:51 PM   Gel-based.ppt (Size: 444 KB / Downloads: 30)   Satisfiability_Problem.ppt (Size: 219 KB / Downloads: 35) 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

Important Note..!

If you are not satisfied with above reply ,..Please