DNA计算的模型与用于解决NP难问题的算法设计

摘要

该文综述了生物计算中的热点-DNA计算,给出了DNA计算的一些实际算法和模型.在第一章中,简述了DNA的结构和DNA计算所需的生物技术;第二章中,说明了以DNA为计算介质的计算具有完备性的基础;第三章总结了目前已有DNA计算模型,给出了它们的图灵等价性的主要结论,最后设计了一个不用限制性酶,模拟图灵机运行的一个DNA模型,这个模型可以有效的模拟非确定图灵机;在最后一章,给出了建立在去除操作基础上解决NP完全和NP优化问题的算法,这类算法的时间复杂度一般是线性的.

目录

文摘

英文文摘

前言

第一章DNA的结构与操作

1.1 DNA的结构

1.1.1 DNA的组成

1.1.2 Watson-Crick互补

1.2 DNA计算中常用到的酶

1.3常用的DNA操作

小结

第二章DNA实现计算的基础

2.1图灵机与RE语言

2.2 DNA本身具有“完备性”

2.2.1 gsm

2.2.2TS语言与其通用性

2.2.3 Watson-Crick互补与TS语言

2.3 Watson-Crick有限自动机模型

2.3.1 Watson-Crick有限自动机

2.3.2 Watson-Crick有限自动机的语言

2.3.3 Watson-Crick有限自动机的分类

2.4生物计算的诞生

小结

第三章DNA计算模型

3.1 DNA-EM模型

3.1.1 EM机

3.1.2双链法的DNA-EM模型

3.1.3 DNA-EM模型的能力

3.2插删系统

3.3剪接系统

3.3.1剪接操作

3.3.2简单的剪接

3.3.3叠代的剪接系统

3.3.4扩展的H系统-EH

3.3.5多重集的剪接系统

3.4利用限制性酶的图灵机的实现

3.4.1图灵带

3.4.2图灵机的运行

3.5不使用切割操作模拟图灵机

3.5.1图灵机各要素的编码

3.5.2转移规则的实现

3.5.3时间复杂度分析

小结

第四章用DNA计算解决NP问题

4.1可满足性问题

4.1.1问题定义

4.1.2初始溶液的制备

4.1.3求解的计算过程

4.1.4一般形式

4.2去除操作为核心的解决NP优化问题的算法

4.2.1生成排列

4.2.2最小顶点覆盖问题

4.2.3 MAX-3SAT

4.2.4最大团

4.3解决NP完全问题-3DM

小结

第五章DNA计算的未来与思考

参考文献：

后记

声明