A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

ZHOU Xu; LI Ken-li; YUE Guang-xue; YANG Zhi-bang

您当前的位置：

首页 >

文章列表页 >

A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

更新时间：2025-07-16

- A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy
- Acta Electronica Sinica Vol. 38, Issue 8, Pages: 1831-1836(2010)
- 作者机构：
  
  1. 嘉兴学院数学与信息工程学院,浙江,嘉兴,314001
  2. 湖南大学计算机间与通信学院,湖南,长沙,410082
  3. 嘉兴学院数学与信息工程学院浙江嘉兴,314001
  4. 湖南大学计算机间与通信学院湖南长沙,410082
- 作者简介：
- 基金信息：
- DOI：
  CLC： T18
- Published：2010
- 稿件说明：
移动端阅览
ZHOU Xu, LI Ken-li, YUE Guang-xue, et al. A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy[J]. Acta Electronica Sinica, 2010, 38(8): 1831-1836.
DOI：

ZHOU Xu, LI Ken-li, YUE Guang-xue, et al. A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy[J]. Acta Electronica Sinica, 2010, 38(8): 1831-1836. DOI：

摘要

本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间

提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略

提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从

)减少至

)≈

(1.414

)

同时生物操作数由

(

)减少至

(15

+30

)

测试试管数由所需的

(

)减少至

(1)

最大链长由

(15

+45

)减少至

(15

/2+45q).因此

本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(2

≈10

)提高到134(67×2=134).同时

与传统的穷举搜索算法相比

该算法具有高效的空间利用率及容错技术的优点.

Abstract

At present

it is how to decrease the DNA volume that plays an important role in the development of DNA computing.In this paper

for the objective to reduce the DNA volume of 3-Dimensional Matching Problem which is a famous NP-complete problem

an improved DNA computing model based on the operations in Adleman-Lipton's model and the solution space of the sticker-based model is put forward.Then

the divide and comquer is introduced into the DNA computing and a new DNA computing's algorithm is proposed.In a computer simu

lation

the DNA strands of maximum number required was

(1.414

)

the time complexity was

(15×

+30×

)

the test tube complesity was

(1) and the longest DNA strand was

(15

/2+45

).Hence

the scale of 3-Dimensional Matching Problem may be enlarged from 67 to 134.This new algorithm is highly space-efficient and error-tolerant compared to the conventional brute-force searching

and can be scaled-up to solve large and hard 3-Dimensional Matching Problem.By the approach

we can also show DNA computing's vast potentials for resolving NP problems.

关键词

Keywords

references

Views

1240

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

Improving the Single Template Method in DNA Computing

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)

Progress in the Research of DNA Computing

Analysis for Directed Hamilton Path Problems Based on Splicing Systems

Related Author

PAN Guo

OUYANG Ai-jia

LI Ken-li

ZHOU Yan-tao

ZHOU Xu

ZHANG Lin-xi

WANG Xiang-hong

LIU Wen-bin

Related Institution

College of Electrical and Information Engineering Hunan University Changsha Hunan China

College of Information Science and Engineering Hunan University Changsha Hunan China

College of Mathematics and Information Engineering Jiaxing University Jiaxing Zhejiang China

College of Electrical and Information Engineering, Hunan University

College of Information Science and Engineering, Hunan University

⁰