| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Classical Ramsey Number DNA Computing Model (¢ñ): Add-Bit-Sequence Model |
| Authors | XU Jin1),2) FAN Yue-Ke2) |
| Address | 1)(Institute of Software, School of Electronics Engineering and Computer Science, Key Laboratory of High Confidence Software Technologies of Ministry of Education, Peking University, Beijing 100871) 2)(Institute of Biomolecular Computer, Huazhong University of Science and Technology, Wuhan 430074) |
| Year | 2008 |
| Issue | No.12(2073¡ª2080) |
| Abstract & Background | Abstract Classical Ramsey number problem is a NP complete problem. It takes exponential time to solve classical Ramsey number problem with traditional electronics computer. It is necessary to study new computation methods because traditional electronics computer faces with greatly difficulty in solving NP complete problem. DNA computing possesses high parallelism in data and higher storage capacity than normal systems. Hence, in theory, it is feasible to solve NP complete problems with DNA computing. A novel method is proposed and used to solve the classical Ramsey number problem in this paper. Firstly, a method for DNA sequence code based on graphic sequence is presented. In order to reflect all possible information of p-order graphs, it is focused on the encoding of p-order complete graph. The number of the edges in the graph is p*(p-1)/2!. The delta-encoding method is selected. The sequences of encodings are the edges 1,2,¡, p*(p-1)/2!. Here, the edges 1,2,¡,p*(p-1)/2! represent adjacent lower triangular matrix array in order from left to right, top to bottomin the graph G. The character of this encoding is to sort them into p-1 classes, and the edges in the i class are composed of {v1,vu+1}, {v2,vi+1,¡, {vi,vi+1}, i=1,2,¡,p-1. According to the encoding, the length p*(p-1)/2! of 0-1 sequence can be mapped to all labeled sub-graphs with p vertexes. It means that arbitrary 0-1 sequence with length p*(p-1)/2! corresponds to the graph with the order p; On the other hand, any order p for the labeled graph corresponds to 0-1 sequence with length p*(p-1)/2!. Secondly, some problems are discussed, such as the set problem of labeling sub-graph and un-labeling sub-graph, especial the method of sequence denoted. Finally, in order to delete the incorrect solutions in the first, the idea, method and process of deleting incorrect solutions are presented, and an instance is presented to illuminate the proposed method. The basic idea is to construct a graph by bit by step. In order to delete incorrect solutions as soon as possible the graph constructed dose not include the Km and Nn. The method, which deletes the set of sub-graphs including Km and Nn from the set of all Km-order sub-graph labeled, deletes the corresponding bit, which is corresponding to the edges set of all m-order Complete sub-graph, from the corresponding sequence Lq; including the set of sequences corresponding bit. The key step for the bit sequence based-on DNA computation can delete the incorrect solution whenever it is brought up. Consequently, it can weaken the speed of which the number of sub-graph increases, and also provides a feasible method for finding the Ramsey number with much higher order. In addition, it is demonstrated the possibility of using the advantage inherent in DNA computation, including vast information storage capacities and much highly computing ability. The more detail researches about how to solve the Ramsey number using DNA computer with be given in the second paper. Keywords Ramsey number£» DNA computing£» add-bit-sequence computing model |