基于碱基匹配的DNA计算系统及其编码研究
VIP免费
I
摘要
基于 DNA 分子的信息传递过程是一个包含编码与解码的互逆过程，体现出天
然的并行计算机制，运用数学方法对这种计算机制进行分析已经成为理论计算机
科学研究的一个新兴领域。DNA 计算研究的目的是希望通过对 DNA 分子计算机
制的分析，建立具有并行功能的生物计算系统。目前，DNA 计算研究包括理论系
统模型的构建和实验研究两大类，本文的选题属于前者，着重于对 DNA 计算模型
中的编码问题进行研究。编码设计是 DNA 计算模型实现的基础，良好的编码对
DNA 计算模型的实现具有重要意义，本文就是基于 DNA 分子的碱基互补配对原
则来分析 DNA 编码的数学结构，探讨如何设计避免碱基错误匹配的编码。
在本文中，我们探讨了运用形式语言和自动机理论建立 DNA 计算模型的有关
问题，对 DNA 分子的碱基序列进行了形式化分析，给出了 DNA 分子碱基互补配
对原则的数学表示，本文的核心内容是围绕 DNA 计算模型的编码问题展开的，包
括理论模型的建立和编码结构的分析。在理论模型的构建方面，主要是对已有的
粘贴系统模型进行了分析，并予以改进，在编码结构的研究方面，主要是基于粘
贴系统的模型框架对如何避免单链分子的碱基错配进行了分析。
本文的理论成果包括：一、提出了一个基于载体分子和单酶切操作的理论模
型，并分析了其所具有的图灵机表达能力；二、提出了一个扩展的粘贴系统模型；
三、运用编码理论建立了一些编码设计的基本原则。
关键词：DNA 计算 形式语言 自动机 粘贴系统 DNA 编码
II
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
IV
§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.1 研究背景介绍
现代电子计算机的基础理论形成于二十世纪三、四十年代，冯·诺伊曼建立了
关于存储程序结构的理论，它成为现代电子计算机的设计基础，冯·诺伊曼模型的
实质是一个串行数据处理模型，其核心设备是中央处理单元(CPU)。现代电子计算
机的物理设计以大规模集成电路为基础，自二十世纪七十年代以来，在信息的存
储容量与处理速度上均有了飞速发展，然而，随着集成电路规模的进一步扩大，
电路的线宽不断缩小，能够通过的电流微弱到只有几十个甚至几个电子，此时，
量子效应就会起作用，它使传统的计算机模型失去了效能。在这种状况下，寻求
新的结构设计理论成为计算机科学研究的一个重要方向。
另一个问题来自于计算理论领域，在现实条件下存在着大量的大规模计算问
题，对这些问题的研究是在一个有限的资源环境中进行的，比如提供给问题的计
算时间和空间是有限的，于是，在资源有限的环境下如何有效地构造计算成为诸
如计算复杂性理论，算法分析，优化理论等相关学科的核心研究内容。但目前上
述研究仍然基于电子计算机平台，这意味着在物理层面上，现有电子计算机的局
限性将对上述有关计算理论的研究产生影响。
由于上述原因，使得目前对于新型计算理论及相关设备的研究变得方兴未艾，
其中一个热点领域就是对生物演化系统表现出的计算特性进行研究。生物系统在
其漫长的进化过程中，不断地调整着自身对环境的适应性，从而保证了该物种的
延续。现代分子生物学的发展为我们在分子层面上揭示了这一生命奇观的本质特
征，一切有关于各物种生命信息的传递都是通过 DNA 分子来完成的，这种精密的
机制引起了数学家和计算机科学家们的兴趣，早在六十年代，Richard Feynman 便
提出了在分子层次上进行计算的设想[1]，而从计算的角度来看，基于 DNA 分子的
信息传递过程是一个包含信息的编码与解码的互逆过程，并且这种操作是在一个
巨大的并行环境中完成的，这吸引我们以数学的观点来分析 DNA 分子信息处理机
制中所蕴含的计算意义，对这种生物计算模式的探讨逐渐演变为一个新颖的研究
领域，称为 DNA 计算。
尽管有关 DNA 计算的理论性研究早在二十世纪八十年代至九十年代初就已出
现[2][3]，但公认的 DNA 计算理论的诞生标志是由美国南加州大学的 Adleman 博士
于1994 年完成的一个用以解决哈密尔顿路径问题的分子生物学实验[4]。通过这个
实验，Adleman 博士为古老的计算概念赋予了全新的理念，即计算问题可以通过生
化实验来完成，这无疑是具有开创性的，随后便出现了对运用 DNA 分子解决 NP
基于碱基匹配的 DNA 计算系统及其编码研究
2
问题的讨论[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]。
摘要：
展开>>
收起<<
I摘要基于DNA分子的信息传递过程是一个包含编码与解码的互逆过程，体现出天然的并行计算机制，运用数学方法对这种计算机制进行分析已经成为理论计算机科学研究的一个新兴领域。DNA计算研究的目的是希望通过对DNA分子计算机制的分析，建立具有并行功能的生物计算系统。目前，DNA计算研究包括理论系统模型的构建和实验研究两大类，本文的选题属于前者，着重于对DNA计算模型中的编码问题进行研究。编码设计是DNA计算模型实现的基础，良好的编码对DNA计算模型的实现具有重要意义，本文就是基于DNA分子的碱基互补配对原则来分析DNA编码的数学结构，探讨如何设计避免碱基错误匹配的编码。在本文中，我们探讨了运用形式语言...
相关推荐
作者：陈辉
分类：高等教育资料
价格：15积分
属性：74 页
大小：942.54KB
格式：PDF
时间：2024-11-19
