图3-着色问题的O链数DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3ⁿ)减少至O(2ⁿ),改进了3-着色问题同类文献的研究结果.

An O Volume Molecular Solutions for the 3-Colorable Problem on DNA-Based Supercomputing ( 1.School of Computer and communications,Hunan University,Changsha,Hunan 410082,China; 2.Institute of Biomolecular Computer,Huazhong University of Science and Technology,Wuhan,Hubei 430074,China)

The DNA volume which increases in a pure exponentially with the scale of the problem has become the bottleneck problem.So how to decrease the volume in DNA computers is of a great significance in the research of DNA computing.For the objective to decrease the DNA volume of the 3-colorable problem,an improved DNA computing model basing on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model is introduced.Furthermore,a new DNA algorithm where new algorithms of Vertex Shader,Sparse Parallel Searcher and Dense Parallel Searcher are developed to solve the 3-colorable problem.The proposed algorithm can solve the 3-colorable problem by using the O(2ⁿ) shorter DNA strands on the condition of not varying the time complexity,as compared by far the best molecular algorithm for it in which O(3ⁿ) DNA strands is used.