Chinese Journal of Computers (计算机学报) 2013/36:12 PP.2537-2544
Scientists have been trying to construct cell computers because of the diversity of information-processing mechanisms within a cell and the vast parallelism of cellular computing. Based on the information-processing mechanisms within a cell, scientists have successfully constructed many cellular computing devices such as Boolean logic gates and memory elements which simulated the functions of simple electronic devices. However, these cellular computing devices ignored the vast parallelism of cellular computing. This study has constructed a cellular computing model which can solve Satisfiability Problem in Escherichia coli using Biobricks. Biobricks are widely used in synthetic biology. The site-specific DNA recombinase Hin, which can mediate inversion of DNA segments that represent variables, was used to produce the solution. In this model, each cell can produce and examine a solution of Satisfiability Problem. As a result, billions of cells can explore billions of possible solutions. This model makes full use of the vast parallelism of cellular computing. It is demonstrated that cellular computing may pave the way to address NP-complete problem using the inherent advantages of cells.