Classical Ramsey number DNA computing model (I): Add-bit-sequence DNA computing model

CORC > 北京大学 > 信息科学技术学院

	Classical Ramsey number DNA computing model (I): Add-bit-sequence DNA computing model
	Xu, Jin ; Fan, Yue-Ke
刊名	jisuanji xuebaochinese journal of computers
	2008
英文摘要	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 DNA computing model based on add-bit-sequence is proposed for the classical Ramsey number problems in this paper. The model consists of memory sub-system, operation sub-system and detection sub-system. The DNA computing model is a novel method for solving classical Ramsey number problems. The designed method and process of DNA sequence in the memory sub-system are provided, such as restriction, algorithm and probe. The operation sub-system is set up with PCR technique, and the sub-system for detect is described. As for the encoding problem of storage sub-system, the authors give three steps as follows; Give a number for encoding according to the possible Ramsey number's size, and estimate the length of each encoding string; Determine the restrictive conditions for DNA sequences in light of biological techniques, such as the types of hybridization; Ensure the length of each encoding string on the basis of the above two conditions. As for how to delete the incorrect solutions, take the r(5, 5) for example; Delete the DNA strands which denote the K5 from X; after finishing the first step, add bit to the rest DNA strands. Additionally, take the same steps as the first step to delete the incorrect solutions K5 or N5. In order to make the sub-system based on DNA computer work, the authors consider using the following biological techniques, such as restriction and PCR to delete the incorrect solutions.; EI; 0; 12; 2081-2089; 31
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/294138]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Xu, Jin,Fan, Yue-Ke. Classical Ramsey number DNA computing model (I): Add-bit-sequence DNA computing model[J]. jisuanji xuebaochinese journal of computers,2008.
APA	Xu, Jin,&Fan, Yue-Ke.(2008).Classical Ramsey number DNA computing model (I): Add-bit-sequence DNA computing model.jisuanji xuebaochinese journal of computers.
MLA	Xu, Jin,et al."Classical Ramsey number DNA computing model (I): Add-bit-sequence DNA computing model".jisuanji xuebaochinese journal of computers (2008).