Research In DNA Assembly Model For Maximum Clique Problem

DNA computing is a novel computing model which is based on some biochemical reactions with the basic materials of molecules and related enzymes. DNA computing overcomes two serious drawbacks of the electronic computers:small storage capacity and slow operational speed. In addition, it shows four outstanding features compared with the traditional turing machine, which are high parallelism, huge storage capability, low energy consumption and rich resources respectively. With the further research of DNA computing, the drawbacks of traditional DNA computing mode, which are high hybrid error rate and highly complex biochemical operations, are emerged gradually. How to improve the accuracy of DNA computing becomes an increasing critical issue on the field of DNA computing. The reasons leading to this bottleneck are various, while the two most important factors are the selection of DNA computing mode and the design of encoding scheme.Most DNA computing algorithms of solving the maximum clique problem are on the basis of paste and editing model. Although these algorithms can determine the maximum clique in a polynomial time, the biochemical operation has a considerable high complexity. Moreover, an increasing number of operational steps lead to a greater error, so the accuracy of results can not be guaranteed. On the basis of the Tiles self-assembly model, this paper defines a mapping between the basic imformation of the maximum clique problem and the cohesive end of Tiles molecules firstly. Then a detailed design scheme consisting of designs and coding schemes of tiles in the initial pattern, decision pattern and detection pattern, whose number of tiles is (?)(n2), is presented. The correctness of the proposed schemes in this paper is proved in theory on the basis of the mathematical description.Furthermore, using DAE molecule, which is a kind of dual acrossing DNA molecules and with stable structure, as computing carrier, the paper presents an improvement on the mathematical description of self-assembly theoretical model of Tiles. Combined with the basic biological operation method, a DNA computing algorithm of solving the maximum clique problem is proposed. The DAE molecules in the process can be classified into three kinds:Initial molecule, regular molecule, and detective molecule. A designing scheme is given in detail for each kind of molecule. The species of DAE molecule is (?)(n+|E|) and the complexity of biochemical operation is (?)(1) in the proposed algorithm, where n and|E|denote the number of vertexes and edges of the graph respectively. Compared with other DNA algorithms of solving the maximum clique problem, the proposed algorithm not only significantly improves the accuracy of biochemical solution, but also reduces the complexity of biochemical experiment. In addition, it has a good operability.