¡¡Chinese Journal of Computers   Full Text
  TitleThe Parallel Type of DNA Computing Model for Solving Ramsey Number Problem
  AuthorsXU Jin1),2) FAN Yue-Ke1)
  Address1)(Institute of Biomolecular Computer£¬ Huazhong University of Science and Technology, Wuhan 430074)
2)(Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871)
  Year2009
  IssueNo.12(2320¡ª2324)
  Abstract &
  Background 		Abstract The difficulty of solving the Ramsey number is that the solution space is too large to solve by traditional computer in effective time and storage space. Moreover, for the traditional DNA computing model, lots of oligonuleotides should be designed and generated much longer DNA sequences which are not convenient for bio-operation. This paper proposes a DNA computing model for Ramsey number based on the enormous parallelism and high-density storage capacity of DNA molecules. The advantage of this model is that many false solutions could be deleted as early as possible. Finally, the authors take R(3,10) as an example and give the concrete steps for solving the problem.
Keywords parallel type; DNA computing; Ramsey number Background
Classical Ramsey number problem belongs to NP complete problem, which will spend exponential time in solving by 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 posssesses hign parallelism in data and higher storage capacity than normal systems. Hence, in theory, it is feasible to solve NP complete problem with DNA computing. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability.
In this paper, a parallel type DNA computing model is proposed and used to solve the classicla Ramsey number problem based on the enormous parallelism and high-density storage capacity of DNA molecules. The basic idea is to construct a graph by bit by site. Here, the authors take as an example and give the concrete steps for solving the problem. The advantage of this model is that many false solution could be deleted as soon as possible.