单位：[1]Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871 China[2]College of Computer Science, South-Central University for Nationalities, Wuhan 430074 China[3]Tongji Hospital of Tongji Medical College, Huazhong University of Science and Technology, Wuhan 430074 China华中科技大学同济医学院附属同济医院[4]Institute of Biomolecular Computers, Huazhong University of Science and Technology, Wuhan 430074 China[5]College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510 China.
The solution space exponential explosion caused by the enumeration of the candidate solutions maybe is the biggest obstacle in DNA computing. In the paper, a new unenumerative DNA computing model for graph vertex coloring problem is presented based on two techniques: 1) ordering the vertex sequence for a given graph in such a way that any two consecutive labeled vertices i and i + 1 should be adjacent in the graph as much as possible; 2) reducing the number of encodings representing colors according to the construture of the given graph. A graph with 12 vertices without triangles is solved and its initial solution space includes only 283 DNA strands, which is 0.0532 of 3(12) (the worst complexity).
基金：
National Natural Science Foundation of ChinaNational Natural Science Foundation of China (NSFC) [60974112, 60910002, 60971085, 30900060, 30970969, 60874036]
第一作者单位：[1]Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871 China
共同第一作者：
通讯作者：
推荐引用方式(GB/T 7714)：
xu jin,qiang xiaoli,yang yan,et al.An Unenumerative DNA Computing Model for Vertex Coloring Problem[J].IEEE TRANSACTIONS ON NANOBIOSCIENCE.2011,10(2):94-98.doi:10.1109/TNB.2011.2160996.
APA：
xu,jin,qiang,xiaoli,yang,yan,wang,baoju,yang,dongliang...&wang,shudong.(2011).An Unenumerative DNA Computing Model for Vertex Coloring Problem.IEEE TRANSACTIONS ON NANOBIOSCIENCE,10,(2)
MLA：
xu,jin,et al."An Unenumerative DNA Computing Model for Vertex Coloring Problem".IEEE TRANSACTIONS ON NANOBIOSCIENCE 10..2(2011):94-98
