最大匹配问题的三链DNA计算模型

第

32

卷 第

4

期

安徽理工大学学报

（

自然科学版

） Vol． 32 No． 4

2012

计

志祥

（ 1．

安徽理工大学理学院

，

安

徽 淮南

232001； 2．

安徽理工大学地球与环境学院

，

安徽 淮南

232001； 3．

安徽理工大学

化学工程学院

232001； 4．

摘 要

：

：

；

三链

DNA；

最大匹配

中

图分类号

文献标志码

： A

文章编号

1672 － 1098（ 2012） 04 － 0047 － 03

收

Triple － stranded DNA Computing Model of Maximum Matching Problem

YANG Jing

1，2

，YIN Zhi － xiang

1

，CHEN Ming － qiang

（ 1． School of Science，Anhui University of Science and Technology，Huainan Anhui 232001，China； 2． School of Earth ang Envi-

ronment，Anhui University of Science and Technology，Huainan Anhui 232001，China； 3． School of Chemical Engineering，Anhui

University of Science and Technology，Huainan Anhui 232001，China； 4． Department of Information and Electrical Engineering，

Huainan Vocational and Technical College，Huainan Anhui 232001，China）

posed． Triple － stranded DNA model has advantages of low rate of wrong solutions． The triple － stranded DNA

model was used to discuss the maximum matching problem，which expands method for solving the problem and

DNA

等作为最基本材料的

基于某些生化反应原理的一

种新型的分子生物计算方法

计算的优势是

利用

分子具有海量的存储能力及生化反应的

巨大并行性等特点进行计算

但

DNA

计算目前还

在实验室阶段

研究的

计算模型还很不成熟

型首先考虑的就是

DNA

分子结构

，

的分子结构也是目前研究的热点

单链的

双链的

环状的

半环状的

及三螺旋等结构的

DNA

分子结构

本文将用三链

1957

念

，

即在经典的

W － C

双螺旋中含有多聚嘌呤那条

链

，

通过

或反

Hoogsteen

氢键与大沟中

的第三条链结合

，

从而形成三螺旋结构即三链

可形成稳定的三链结构

，

首先寡

聚脱氧核苷酸在

S

的

存在下与

RecA

合

，

然后在目标双螺旋

这一

过程非常迅速并且不打开