The Computational Model Of Living Organisms In The Np-complete Problem

A bran-new research field biological computation came forth since Adleman implemented the molecular biological experiment to solve the problem of Hamilton Path in the nineties of the last century. With the advantages of huge parallelism, massive storage capability and lower energy cost, biological computation is drawing more and more attention of researchers. This paper gives a preliminary analysis and discussion about the biological realization of biological computation and its algorithmic models under the experimental methods and techniques of molecular biology. And we mainly discuss and do the study of the Hamilton Path Problem and the SAT problem based on the in vivo model of biological computation. The specific contents are as follows:There are three hard points in the current research of biological computation:1. Coding, which is the first problem the biological computation should solve. It needs to translate the problems which we want to solve into biological molecules. The current coding method cannot meet the practical requirement of biological computation.2. Biological realization, how to design the experiment and operation so that the molecule representing the result of the problem can be generated instead of the wrong result or fake result.3. Detection of result, which is one of the hard points of biological computation. This paper give a detailed analysis and discussion about the current detection techniques.Biological computation model in vivo is based on the different kinds of molecules in vivo which team up in a special way to process information, which is a new model of biological computation. Every part of the biological computation model in vivo has some computing ability and they are all embed in the living organisms, so we can use it to study the ability of how the organisms process information and how to acquire and conquer this kind of ability. This paper mainly dissertate the biological computation model in vivo based on the carrier of plasmid and firstly discuss the in vivo algorithmic model of the Hamilton Path Problem and the SAT problem.The Hamilton Path Problem is an NP-complete problem, and it has an extensive application in the field of engineering optimization, field management and so on. This paper firstly translate the problem into a mixed DNA single and double chain coding, then use the carrier of plasmid to search the related paths, lastly get the optimal solution via electric field separating equipment, and give an example to explain the specific steps of the algorithm. The SAT problem is the seed of the legions of NP-complete problems, and it has an extensive application in the field of artificial intelligence, hardware testing and so on. This chapter gives the molecular algorithm of the SAT problem based on the biological computation model in vivo. Firstly we give a code to each variable, and all the codes are set in a double chain of DNA molecule, which could reduce the workload of coding operation, namely the synthesis of DNA molecules. In the computing process we use enzymes to operate the plasmid recombinant under the constraint condition. After all the operations to every clause are completed, the left DNA strands in the tube which represents the variables are the results space which we need to output. Lastly we detect the result of the certain problem, and give an example to explain the realization of the algorithm. In the last paragraph of this chapter, we also give an extension of the algorithm, namely solving the error permutation problem in mathematics. The basic idea is to convert the error permutation problem to SAT problem, then give a molecular algorithm based on the in vivo biological computation model.At the last part of this paper, we analyze and discuss the advantages and disadvantages of the biological computation model in vivo, although there are some advantages in the biological computation model in vivo, there are still some difficulties in the current biochemical experimental operation and technology, which are as follows:①It is too hard to control the living organisms.②The demand of the types of the restrictive incision enzymes are manifold with the augmentation of the size of problems.③The errors of the incision enzymes may cause the loss of data and the emergence of the fake answer or wrong answer. In conclusion there are prodigious difficulties in the current control and operation of the living organism. How to avoid and resolve these difficulties will be the direction of our future work, which needs our more hard work.