摘要
DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.
The scalability problem in DNA computer has been one of the important research areas in DNA computing. According to the requirement of the DNA parallel computing for exact cover problem, a DNA model for good scalability is proposed, which is based on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model by simultaneously taking the method of fluorescence labeling and the technique of gel electrophoresis into the model. Based on this model, a DNA-based algorithm for the exact cover problem, by making use of the strategem of divide-and-conquer, is also proposed which consists of three sub-algorithms： Init （）, IllegalRemove（）, and ParallelSeacher（）. Compared with by far the best molecular algorithm for the exact cover problem with n variables and m sets in which O（2^n） DNA strands are used, this algorithm can solve the same problem only using O（1. 414^n） DNA strands 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 120, and thus the is an improved result over the past researches.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第10期1782-1788,共7页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60603053,90715029)
浙江省自然科学基金项目(106654)
高等学校博士后科学基金项目(20060400845)~~
关键词
DNA计算机
NP完全问题
精确覆盖问题
分治法
DNA超级计算
DNA computer
NP-complete problem
exact cover problem
divide super-computing proposed algorithm and conquer
DNA
