Chinese Journal of Computers   Full Text
Title	Boolean Logic Computation Based on Dan Tiles Self-Assembly
Authors	HUANG Yu-Fang1) CHENG Zhen1) ZHOU Kang2) XIAO Jian-Hua3) SHI Xiao-Long1)
Address	1)(Research Institute of Bio-molecular Computing, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074) 2)(Department of Mathematics and Physic, Wuhan Polytechnic University, Wuhan 430023) 3)(Research Center of Logistics, Nankai University, Tanjin 300071)
Year	2009
Issue	No.12(2347—2354)
Abstract &   Background	Abstract A large number of work has demonstrated that self-assembly of DNA tiles is a significant method among molecular computations. Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. The simple binary arithmetic and logical operations can be computed by the process of self assembly of DNA tiles, yielding the results of the problem. In this paper, the authors consider taking advantage of the self-assembly of DNA tiles for logical evaluation, and propose a procedure to compute a 4-variable 4-clause 3-conjunctive (3-CNF) Boolean computational problem. The procedure enables any Boolean operations whose inputs and outputs are defined by a truth table, and evaluates any different kinds of Boolean logical formula simultaneously. Keywords self-assembly; DNA tiles; molecular computation; logical evaluation; SAT problem Background The research group mainly devotes themselves to the field including the Graph Theory, Information Security, Model and Method of DNA Computer etc. They have published more than 150 papers on DNA computing and DNA computer. The paper proposes an arithmetic model to evaluate a four-variable four-clause Boolean computational problem based on the DNA tiles self-assembly. The smart “DNA tiles” invented by Winfree are the most promising approaches among DNA computing methods. Winfree’s brainstorm is to create nano-scopic building blocks out of DNA that not only can store data but are designed- Winfree likes to say “programmed”-to carry out mathematical operations by fitting together in specific ways. Normally, DNA exists as two intertwined strands of the chemical letters A, G, C and T-the familiar double helix. But Winfree’s DNA tiles are made by knotting together three or more of these strands, forming “tiles” about 15 nanometers (billionths of a meter) on their longest side. Taking advantage of DNA’s ability to selectively recognize other strands of DNA, Winfree has “coded” the edges of these tiles so that they come together in just the right way to form tiny built-to-order structures. Then, Mao and his colleagues have used DNA triple crossover molecules with diagonal reporter strands as tiles to perform four steps of a cumulative exclusive OR(XOR) operation in two independent assemblies in their laboratory. Brun has defined an arithmetic system of tile assembly, and tackled these issues to compute the sum and product of two numbers in binary. All these work have demonstrated that the DNA tiles can program in light of our careful designs to accomplish a variety of computations. This model proposed in this paper has demonstrated the huge potential for computing inherent in DNA tiles. It shows that the great potential of algorithmic self-assembly of DNA tiles can be used to solve the SAT problem. When the conventional computer based on silicon is facing more and more seriously hard computing problems, at least needing quite a long time to get the result, human beings have to turn to other computing methods for help. Algorithm basing on the self-assembling of DNA tiles may be one of the possible ways to break the limit of brute-force method in DNA computing. Many scientists have been paying their attentions on this field for solving NP problems using DNA tiles self-assembly.