| 精确覆盖问题的O(1.414~n)链数DNA计算机算法 |
| |
| 引用本文： | 李肯立,刘杰,杨磊,刘文斌.精确覆盖问题的O(1.414~n)链数DNA计算机算法[J].计算机研究与发展,2008,45(10). |
| |
| 作者姓名： | 李肯立 刘杰 杨磊 刘文斌 |
| |
| 作者单位： | 1. 湖南大学计算机与通信学院,长沙,410082
2. 温州大学计算机科学与工程学院,浙江温州,325027 |
| |
| 基金项目： | 国家自然科学基金项目，浙江省自然科学基金项目，高等学校博士后科学基金项目 |
| |
| 摘 要： | DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.
|
| 关 键 词： | DNA计算机 NP完全问题 精确覆盖问题 分治法 DNA超级计算 |
An O(1.414~n)Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing |
| |
| Li Kenli,Liu Jie,Yang Lei,Liu Wenbin.An O(1.414~n)Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing[J].Journal of Computer Research and Development,2008,45(10). |
| |
| Authors: | Li Kenli Liu Jie Yang Lei Liu Wenbin |
| |
| Affiliation: | Li Kenli1,Liu Jie1,Yang Lei1,, Liu Wenbin21(College of Computer , Communication,Hunan University,Changsha 410082)2(College of Computer Science , Engineering,Wenzhou University,Wenzhou,Zhejiang 325027) |
| |
| Abstract: | 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... |
| |
| Keywords: | DNA computer NP-complete problem exact cover problem divide and conquer DNA super-computing |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
