DOI: 10.3724/SP.J.1016.2013.02537

Chinese Journal of Computers (计算机学报) 2013/36:12 PP.2537-2544

A Biobrick Inversion Cellular Computing Model for Satisfiability Problem

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.

Key words:Biobrick,DNA recombinase Hin,gene regulation,satisfiability problem,cellular computing

ReleaseDate:2014-07-21 17:04:09