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

李肯立; 周 旭; 许 进; 湖南大学计算机与通信学院; 湖南长沙; 华中科技大学分子生物计算机研究所; 湖北武汉

您当前的位置：

首页 >

文章列表页 >

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

论文 | 更新时间：2025-07-16

- 图3-着色问题的O链数DNA计算机算法
- 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)
- 电子学报 2008年36卷第11期页码：2096-2101
- 作者机构：
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.60603053,60503002,60533010);浙江省自然科学基金 (No.Y106654);中国博士后科学基金 (No.20060400845)
- DOI：
  中图分类号： TP384
- 纸质出版：2008
- 稿件说明：
移动端阅览
李肯立, 周旭, 许进, 等. 图3-着色问题的O链数DNA计算机算法[J]. 电子学报, 2008,36(11):2096-2101.

LI Ken-li, ZHOU Xu, XU Jin. 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)[J]. Acta Electronica Sinica, 2008, 36(11): 2096-2101.
李肯立, 周旭, 许进, 等. 图3-着色问题的O链数DNA计算机算法[J]. 电子学报, 2008,36(11):2096-2101. DOI：

LI Ken-li, ZHOU Xu, XU Jin. 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)[J]. Acta Electronica Sinica, 2008, 36(11): 2096-2101. DOI：

摘要

随着DNA计算的不断发展

如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数

本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展

通过设计顶点着色器、稀疏图/稠密图搜索器

提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下

将求解

个顶点的图3-着色问题所需DNA分子链数从

O(3

)减少至O(2

)

改进了3-着色问题同类文献的研究结果.

Abstract

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.

关键词

Keywords

references

浏览量

1268

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种基于分治的三维匹配问题DNA计算算法

基于Tile自组装模型的最大匹配问题算法研究