一种最大匹配问题DNA计算算法

A Volume Molecular Solution for the Maximum Matching Problem on DNA-Based Computing

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.

DNA computing makes use of biomolecules as information storage materials and biological laboratory experiments as information processing operators. At present, DNA computing has been employed to many different decisions or combinatorial optimization problems and it has led to an important breakthrough in computing. The power of parallel, high density computation by molecules in solution also allows DNA computer to solve hard computational problems such as NP-complete problems. The maximum matching problem is a famous NP-eomplete problem. For the objective to decrease the solution volume of the DNA computing algorithm for the maximum matching problem, the pruning strategy is introduced into the DNA supercomputing and a DNA computing algorithm is proposed. The new algorithm consists of a graph composer, a resolvent generator, a parallel matching generator and a maximum matching searcher. Compared with the existing molecular algorithms for maximum matching problem, the DNA strands of maximum number required is reduced from 0（2~） to O（1. 618＂） on the condition of not varying the time complexity. Therefore, the cardinal number of the exact cover problem that can be theoretically resolved in a test tube may be enlarged from 60 to 86, thus the proposed algorithm is an improved result over the past researches. This algorithm is space-efficient and error-tolerant compared with conventional brute-force searching, and thus it can be scaled-up to solve large and hard maximum clique problems.