目 录
摘要 ................................................................................................................................... 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