基于碱基匹配的DNA计算系统及其编码研究

VIP免费

3.0 陈辉 2024-11-19 5 4 942.54KB 74 页 15积分

侵权投诉

摘要

基于 DNA 分子的信息传递过程是一个包含编码与解码的互逆过程，体现出天

然的并行计算机制，运用数学方法对这种计算机制进行分析已经成为理论计算机

科学研究的一个新兴领域。DNA 计算研究的目的是希望通过对 DNA 分子计算机

制的分析，建立具有并行功能的生物计算系统。目前，DNA 计算研究包括理论系

统模型的构建和实验研究两大类，本文的选题属于前者，着重于对 DNA 计算模型

中的编码问题进行研究。编码设计是 DNA 计算模型实现的基础，良好的编码对

DNA 计算模型的实现具有重要意义，本文就是基于 DNA 分子的碱基互补配对原

则来分析 DNA 编码的数学结构，探讨如何设计避免碱基错误匹配的编码。

在本文中，我们探讨了运用形式语言和自动机理论建立 DNA 计算模型的有关

问题，对 DNA 分子的碱基序列进行了形式化分析，给出了 DNA 分子碱基互补配

对原则的数学表示，本文的核心内容是围绕 DNA 计算模型的编码问题展开的，包

括理论模型的建立和编码结构的分析。在理论模型的构建方面，主要是对已有的

粘贴系统模型进行了分析，并予以改进，在编码结构的研究方面，主要是基于粘

贴系统的模型框架对如何避免单链分子的碱基错配进行了分析。

本文的理论成果包括：一、提出了一个基于载体分子和单酶切操作的理论模

型，并分析了其所具有的图灵机表达能力；二、提出了一个扩展的粘贴系统模型；

三、运用编码理论建立了一些编码设计的基本原则。

关键词：DNA 计算形式语言自动机粘贴系统 DNA 编码

ABSTRACT

The information transfer process in DNA molecular is a bi-directional process

including encoding and decoding, which makes a natural parallel computing mechanism,

it is becoming a new research field in theoretical computer science while using

mathematical method to analyze this mechanism. The research aim of DNA computing

is to establish a new biological computing system. How to create theoretical models and

how to find efficient experiment methods are presently the two main research contents

of DNA computing. The research title selected in this thesis is especially about the

coding theory of DNA computing model. It is important for the realization of DNA

computing model that designing good code, so we give a systemic analysis about the

mathematic structure of DNA codes, and have a discussion about how to design DNA

code for computing which can avoid the incorrect matching between two single DNA

strands.

In this thesis, we first give some discussions about model creation problems of

DNA computing, in which we use formal language and automata theory to analyze the

properties of DNA sequences, and give a mathematical expression about Watson- Crick

complementarities; the core content of this thesis is about DNA code, including such

problems about coding model creation and its structure analysis. In aspect of the

question about model creation, we analyze the existing DNA computing model-- sticker

system model, and give some improvements, in another aspect of coding structure

analysis, based on the sticker system model, we analyze the coding problems in detail

about how to avoid the incorrect matching between two single DNA strands.

Some results we’ve got in this thesis are: firstly, putting forward a new theoretical

model which based on the mechanism of the ligation between target gene and vector

molecular, and prove its expression ability of Turing machine properties; secondly,

bringing forward an extended sticker system model; thirdly, creating some DNA code

designing principles based on coding theory.

Key Word: DNA computing, Formal language, Automata, Sticker

system, DNA code

III

摘要 ................................................................................................................................... I

ABSTRACT ....................................................................................................................II

目录 .............................................................................................................................. III

第一章绪论 .....................................................................................................................1

§1.1 研究背景介绍 .................................................................................................1

§1.2 本文的研究内容及意义 .................................................................................3

第二章 DNA 计算理论基础 ........................................................................................... 5

§2.1 形式语言与自动机理论介绍 .........................................................................5

§2.1.1 字符集和语言 ..............................................................................................5

§2.1.2 乔姆斯基(Chomsky)文法系统 ....................................................................6

§2.1.3 自动机和转换器 ..........................................................................................7

§2.2 DNA 计算的生物学基础 ..............................................................................10

§2.2.1 DNA 分子的结构 .......................................................................................10

§2.2.2 工具酶与载体 ............................................................................................11

§2.2.3 DNA 分子的操作 .......................................................................................12

§2.2.4 DNA 计算的生化操作 ...............................................................................15

§2.3 本章小结 .......................................................................................................15

第三章 DNA 计算系统的理论模型 ............................................................................. 17

§3.1 NP 问题概述 ................................................................................................. 17

§3.2 Adleman-Lipton 实验介绍 ............................................................................ 18

§3.2.1 Adleman 实验 ............................................................................................. 18

§3.2.2 Lipton 实验 .................................................................................................20

§3.3 理论 DNA 计算模型 ....................................................................................21

§3.3.1 Adleman-Lipton 实验的形式化 ................................................................. 21

§3.3.2 DNA 分子碱基序列的抽象表达及其结构分析 .......................................23

§3.4 基于酶催化的 DNA 计算模型 ....................................................................25

§3.4.1 剪接系统模型 ............................................................................................25

§3.4.2 带剪接规则的插入-切割 DNA 计算系统(○IC) ..................................... 27

§3.4. 3 带剪接规则的插入-切割 DNA 计算系统的图灵机表达能力 ................28

§3.5 本章小结 .......................................................................................................31

第四章基于碱基匹配的 DNA 计算模型 .................................................................... 32

§4.1 碱基互补配对原则的数学表示 ...................................................................32

§4.2 基于互补配对原则的字符操作 ...................................................................33

§4.3 粘贴系统及其扩展 .......................................................................................36

§4.4 本章小结 .......................................................................................................44

第五章碱基匹配计算系统的编码理论 .......................................................................45

§5.1 DNA 碱基编码问题的产生 ..........................................................................45

§5.2 匹配计算的编码问题分析 ...........................................................................46

§5.3 基于 DNA 单链的编码构造 ........................................................................54

§5.4 基于分子生物操作的 DNA 语言的 f特性 .................................................58

§5.5 本章小结 .......................................................................................................59

第六章结论与展望 .......................................................................................................60

§6.1 本文的结论 ....................................................................................................60

§6.1.1 主要结论 .....................................................................................................60

§6.1.2 存在的问题 .................................................................................................60

§6.2 研究展望 ........................................................................................................61

附录 .................................................................................................................................63

参考文献 .........................................................................................................................65

第一章绪论

§1.1 研究背景介绍

现代电子计算机的基础理论形成于二十世纪三、四十年代，冯·诺伊曼建立了

关于存储程序结构的理论，它成为现代电子计算机的设计基础，冯·诺伊曼模型的

实质是一个串行数据处理模型，其核心设备是中央处理单元(CPU)。现代电子计算

机的物理设计以大规模集成电路为基础，自二十世纪七十年代以来，在信息的存

储容量与处理速度上均有了飞速发展，然而，随着集成电路规模的进一步扩大，

电路的线宽不断缩小，能够通过的电流微弱到只有几十个甚至几个电子，此时，

量子效应就会起作用，它使传统的计算机模型失去了效能。在这种状况下，寻求

新的结构设计理论成为计算机科学研究的一个重要方向。

另一个问题来自于计算理论领域，在现实条件下存在着大量的大规模计算问

题，对这些问题的研究是在一个有限的资源环境中进行的，比如提供给问题的计

算时间和空间是有限的，于是，在资源有限的环境下如何有效地构造计算成为诸

如计算复杂性理论，算法分析，优化理论等相关学科的核心研究内容。但目前上

述研究仍然基于电子计算机平台，这意味着在物理层面上，现有电子计算机的局

限性将对上述有关计算理论的研究产生影响。

由于上述原因，使得目前对于新型计算理论及相关设备的研究变得方兴未艾，

其中一个热点领域就是对生物演化系统表现出的计算特性进行研究。生物系统在

其漫长的进化过程中，不断地调整着自身对环境的适应性，从而保证了该物种的

延续。现代分子生物学的发展为我们在分子层面上揭示了这一生命奇观的本质特

征，一切有关于各物种生命信息的传递都是通过 DNA 分子来完成的，这种精密的

机制引起了数学家和计算机科学家们的兴趣，早在六十年代，Richard Feynman 便

提出了在分子层次上进行计算的设想[1]，而从计算的角度来看，基于 DNA 分子的

信息传递过程是一个包含信息的编码与解码的互逆过程，并且这种操作是在一个

巨大的并行环境中完成的，这吸引我们以数学的观点来分析 DNA 分子信息处理机

制中所蕴含的计算意义，对这种生物计算模式的探讨逐渐演变为一个新颖的研究

领域，称为 DNA 计算。

尽管有关 DNA 计算的理论性研究早在二十世纪八十年代至九十年代初就已出

现[2][3]，但公认的 DNA 计算理论的诞生标志是由美国南加州大学的 Adleman 博士

于1994 年完成的一个用以解决哈密尔顿路径问题的分子生物学实验[4]。通过这个

实验，Adleman 博士为古老的计算概念赋予了全新的理念，即计算问题可以通过生

化实验来完成，这无疑是具有开创性的，随后便出现了对运用 DNA 分子解决 NP

基于碱基匹配的 DNA 计算系统及其编码研究

问题的讨论[5]。1995 年，普林斯顿大学的 Lipton 等又设计了一个针对可满足性问

题（SAT）的计算实验[6]，这些早期的工作提出了 DNA 分子计算的基本思想，可

以归纳为下述三个步骤[7]：

1.用DNA 分子链的四个碱基，在特定的互补配对规则作用下，构造不同组合

来生成问题的编码

2.通过设计一组可控的分子生物学实验完成问题的求解计算

3.对所获结果进行检测和解码，以找出代表问题解的 DNA 序列

遵循这一基本思想，目前 DNA 计算的研究内容不断丰富，概括来说，DNA

计算理论的研究主要划分为两类：理论 DNA 计算研究和 DNA 计算的实验研究。

理论 DNA 计算研究是期望建立起严格的理论基础，在现有的计算理论中，图灵可

计算性成为现代计算机的理论基础，因此对于 DNA 计算的理论研究很自然的也纳

入到这个理论框架下来。另外，现代电子计算机是以二进制序列来表达信息的，

研究符号序列的信息表达能力运用了形式语言和自动机理论，DNA 序列是以四个

碱基按照互补配对规则来建立的，因此研究 DNA 序列的计算能力也同样运用了形

式语言和自动机的理论。目前的理论模型已从单纯的对 DNA 分子计算能力的研究

发展到细胞计算的层面上来，其代表模型就是 P系统以及基于纤毛虫遗传机理的

基因装配计算系统。DNA 计算的实验研究在于构建具有实现可能性的 DNA 计算

系统，在 Adleman-Lipton 实验成功之后，由威斯康星大学的一个小组进行了基于

表面化学技术解决四变量 SAT 问题的实验[8]-[9]，它的意义在于将 DNA 链固定在硅

或者玻璃等表面上，而不是漂浮在溶液中，这使对 DNA 链的操作得以简化，从而

减少 DNA 链的丢失，提高了 DNA 计算的可靠性，使 DNA 计算朝自动化和实用

化方向进一步发展。另一项重要的实验成果是由 Winfree 等进行的一系列 DNA 分

子自装配实验，通过构建不同形状的 DNA 分子片，并将它们按照一定的规则进行

组合，从而完成了特定的组合计算，并且不同形状的 DNA 分子片的组合计算能力

被证明能够类比于乔姆斯基的文法体系，其意义在于将基于线性 DNA 分子的计算

拓展到了二维平面的 DNA 分子计算，使其成为纳米技术研究的一个重要领域。

从DNA 分子进行信息遗传的本质特征来看，它不同于现代电子计算机的串行

数据处理模式，而体现出并行数据处理模式，因此，DNA 计算研究的最终目标是

建立起具有并行数据处理能力的生物计算机。DNA 计算理论的研究发展到今天，

已经在上述几个方面不断获得新的进展，其中，关于 DNA 计算研究的综述性文献

可参阅[10]-[16]，关于 P系统以及细胞计算理论的文献可参阅[17]-[22]，关于 DNA

分子自装配计算的文献可参阅[23]-[26]。

第一章绪论

§1.2 本文的研究内容及意义

本文着重于对 DNA 计算系统的编码问题进行研究。编码问题是 DNA 计算模

型实现的首要步骤，DNA 计算的实现基础是 DNA 分子的碱基互补操作，从形式

语言和自动机理论的角度来看，这种碱基互补配对规则构成了一种新的表达字符

序列信息的方式，在这种规则支配下，带有编码性质的 DNA 分子链通过实现杂交

与解链反应，形成表达问题结果的分子链，从而完成 DNA 计算。因此，杂交与解

链反应的效率和精度直接影响到 DNA 计算的结果，在这一方面的研究中一种方法

是从实验技术的角度对 DNA 分子杂交和解链进行控制，另一种方法就是设计具有

良好结构的编码，以避免 DNA 分子间的错误杂交[27]-[29]。本文则是在 DNA 分子碱

基匹配操作的基础上探讨 DNA 编码的数学结构，所要解决的问题是：

1.在DNA 分子的碱基互补配对规则下，如何构建 DNA 编码。

2.基于对 DNA 编码结构的分析来探讨如何避免出现错误杂交的编码。

本文按照如下方式进行组织：

第二章对 DNA 计算研究所需要的背景知识进行了介绍，包括形式语言和自动

机理论以及分子生物学基础。目前 DNA 计算研究的基本方法是将基于碱基互补配

对规则的操作抽象为字符集上的字串操作，其理论框架是建立在形式语言和自动

机理论基础之上的，因此这一章首先介绍了必要的形式语言和自动机理论。另外，

在相关的分子生物学部分，主要介绍了基于碱基互补配对规则对 DNA 分子进行各

种操作的一些知识。

第三章对理论 DNA 计算的有关模型进行了讨论。DNA 计算理论的兴起首先

来源于对 NP 问题的研究，因此在这一章中，首先引述了有关 NP 理论的一些基本

内容，随后介绍了著名的 Adleman 实验和 Lipton 实验。本章的核心内容是关于理

论DNA 计算模型的介绍，这里详细讨论了基于单酶切操作的 DNA 计算模型，它

是在既有剪接系统模型的基础上，模拟载体分子和目的基因在单酶切操作下的拼

接组合过程构造出的一个理论模型，其后论证了该模型所具有的图灵机表达能力。

第四章讨论了基于碱基匹配操作的 DNA 计算模型。碱基互补配对原则是 DNA

分子信息遗传所遵循的基本规则，本章讨论了基于碱基互补配对原则的理论模型，

并且运用形式语言和自动机理论对其进行了理论分析，本章的分析是通过引入一

个变换函数将既有的双向粘贴操作形式化为单向粘贴操作，并且将基于单链分子

的粘贴系统模型扩展为带粘末端的 DNA 片段的粘贴操作模型，对其具有的语言表

达能力进行了分析。本章讨论的模型也是下一章关于 DNA 计算编码研究的理论基

础。

第五章讨论了碱基匹配计算模型中的编码设计问题。在基于碱基匹配的 DNA

基于碱基匹配的 DNA 计算系统及其编码研究

计算模型中，我们运用寡聚核苷酸来构造问题的编码，让其按照碱基互补配对原

则进行匹配，从而得到表达问题解的 DNA 分子链。但在实际的寡酸构造中，存在

于同一集合内的各寡酸分子之间可能存在碱基错配的情形，导致错误杂交，致使

编码失效。本章就是围绕碱基匹配模型中的编码问题进行了较为深入的研究。首

先分析了碱基错配的各种情形，然后对碱基匹配操作和剪接操作模型框架下的

DNA 编码构造进行了分析。

第六章对本文的研究进行了总结，同时对当前 DNA 计算研究的几个热点领域

进行了介绍。

在附录部分，我们给出了目前运用 DNA 计算理论对 NP 问题进行研究的一个

统计表，以供查阅。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

I摘要基于DNA分子的信息传递过程是一个包含编码与解码的互逆过程，体现出天然的并行计算机制，运用数学方法对这种计算机制进行分析已经成为理论计算机科学研究的一个新兴领域。DNA计算研究的目的是希望通过对DNA分子计算机制的分析，建立具有并行功能的生物计算系统。目前，DNA计算研究包括理论系统模型的构建和实验研究两大类，本文的选题属于前者，着重于对DNA计算模型中的编码问题进行研究。编码设计是DNA计算模型实现的基础，良好的编码对DNA计算模型的实现具有重要意义，本文就是基于DNA分子的碱基互补配对原则来分析DNA编码的数学结构，探讨如何设计避免碱基错误匹配的编码。在本文中，我们探讨了运用形式语言...

展开>> 收起<<

基于碱基匹配的DNA计算系统及其编码研究.pdf

共74页,预览8页

还剩页未读，继续阅读

基于碱基匹配的DNA计算系统及其编码研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: