DNA计算一种新的计算模式 (2008 年度畅销榜NO.11828 )

目前在大规模并行计算模式方面主要有两种新模式：量子计算模式和生物计算模式.本书即是对生物计算模式(DNA计算模式)的详尽介绍，内容涉及粘贴系统、Watson—Crick自动机、插入—删除系统、剪接系统、有穷H系统的通用性、剪接循环串、分布式H系统等.本书内容组织合理，介绍由浅人深，并给出了所需的语言学和生物学方面的基础知识.
本书可作为生物信息学等专业的教材，也是一本该领域研究人员的极好的参考书.

引言DNA计算简介
第一部分背景与动机
第1章DNA的结构与处理
1.1DNA的结构
1.2DNA分子的操作
1.3读出序列
1.4文献注记
第2章分子计算初步
2.1Adleman实验
2.2我们能否解决可满足性问题及破译DES密码
2.3计算模式——一些再思考
2.4DNA计算：希望与挑战
第二部分数学理论
第3章形式语言理论介绍
3.1基本记号，文法，自动机，文法系统
3.2递归可枚举语言的刻画
3.3通用图灵机和0型文法
3.4文献注记
第4章粘贴系统
4.1粘贴运算
4.2粘贴系统及其分类
4.3粘贴系统的生成能力
4.4正则语言和线性语言的表示
4.5递归可枚举语言的刻画
4.6正则粘贴系统
4.7文献注记
第5章Watson-Crick自动机
5.1Watson-Crick有穷自动机
5.2WK簇之间的关系
5.3递归可枚举语言的刻画
5.4Watson-Crick有穷转换器
5.5Watson-Crick有穷自动机的其他变形
5.6带有Watson-Crick内存的Watson-Crick自动机
5.7关于Watson-Crick自动机的通用性理论
5.8文献注记
第6章插入删除系统
6.1DNA结构中的插入—删除
6.2递归可枚举语言的刻画
6.3单字符插入—删除系统
6.4只使用插入运算
6.5文献注记
第7章剪接系统
7.1从DNA重组到剪接运算
7.2作为语言运算的非迭代剪接
7.3作为语言运算的迭代剪接
7.4扩充H系统；生成能力
7.5简单H系统
7.6文献注记
第8章有穷H系统的通用性
8.1用2—剪接代替1—剪接
8.2允许和禁止上下文
8.3目标语言
8.4程序化系统和进化系统
8.5双剪接H系统
8.6多重集合
8.7通用性结果
8.8文献注记
第9章剪接循环串
9.1循环串的剪接运算变量
9.2一个变形变量及其能力
9.3文献注记
第10章分布式H系统
10.1剪接文法系统
10.2通信分布式H系统
10.3双层分布式H系统
10.4分时分布式H系统
10.5计算完备性H系统的总结
10.6文献注记
第11章再述剪接
11.1受限剪接：非重复情况
11.2复制系统
11.3文献注记
参考文献

1984年，硕士导师王自果教授把我引进运筹学的大门.从此我与优化计算，特别是图与组合优化方面的优化计算结下了不解之缘.自那时起，每当在杂志上看到有关图与组合优化方面的学术论文，我都会带着浓厚的兴趣去拜读.从1990年开始，我逐渐掌握了用人工神经网络求解图与优化问题的方法，后来又学会了用遗传算法和模拟退火等算法来求解图与组合优化问题.通过这些积累，使我在解决优化问题上有了一定的方法、技巧与经验，但同时我也认识到，不管是一些常规的图论算法还是人工神经网络方法、遗传算法、模拟退火算法等，它们在电子计算机这个子台上，面对一般性困难的NP—完全问题，实际上都是“无能为力”的!这些算法只能是一点点地改进，一点点地推进.虽然有大量的报道宣称(包括本人在内)，用某方法对某NP—完全问题在一些特殊条件下，或者在规模较小的条件下解决得很好，但实际上，对于一般情况下大规模的NP—完全问题，已有的方法在电子计算机平台上都是很难解决的! 1996年年末的某一天，阅读“Science”时，无意中发现Adleman发表的题为“MolecularComputationOfSolutionstOCombinatorialProblems”的文章.看了题目和摘要之后，兴趣大发：还有人用DNA分子来求解“我们图论中的有向Hamilton路问题”!我想好好读读此文，但读不懂!原因是我不懂DNA分子的性质，更不了解什么是连接酶.能读懂的只是他的算法步骤，而他的算法好像是一种最笨的枚举法，因此我也就没有在意此文. 1997年，我的一位博士生发现了Ouyang等人发表在“Science”上的题为《最大团问题的DNA解(DNASolutionOftheMaximalCliqueProblem)》的文章.阅读之后，觉得与Adleman的文章类似，但还是看不懂.于是，我带着这篇文章，请教了陕西师范大学生物系的一位张老师，他读了此文之后觉得有道理.我决定试着学习“用DNA分子求解图论中的NP—完全问题”这一方法，从此，开始学习有关分子生物学的知识.待有了一点点门道之后，决定好好在这一领域耕耘，并动员我的几位博士生放弃在神经网络和遗传算法等领域的研究，来从事DNA计算方面的学习与研究.到目前，我已经为祖国培养出了从事DNA计算研究的博士后2名，博士7名. 1999年，看到Pgun等人撰写的关于DNA计算方面的学术专著，立即开始了阅读学习，并萌发了尽快译成中文介绍给我国学者的想法.本来本书早就应该与读者见面，但是由于种种原因延误至今才出版. 本书是国际上第一部关于DNA计算方面的学术专著.此专著主要总结了1998年以前几个主要DNA计算模型的数学理论基础方面的研究成果. 全书共11章.第1章给出了DNA分子的基本结构与性质.第2章主要介绍了Adleman和Lipton两人在DNA计算方面的开拓性工作.第3章给出了后面章节所用的形式语言的有关基本理论.从第4章开始，作者介绍了DNA计算中的几个模型的数学理论，其中第4章讨论粘贴系统(stickersystem)，它是在由Rowels等人提出的粘贴模型(stickermodel)的基础上抽象出来的一种纯数学模型.第5章研究Watson-Crick自动机，它是有关这种粘贴系统的自动机的理论体系.第6章给出了插入—删除系统.第7章介绍了所谓的剪接系统，此系统是目前学者们所关注的一个研究领域.第8章讨论了有穷H系统的通用性，以期对未来的通用DNA计算机理论进行探索.第9章给出了剪接循环系统.第10章给出了基于文法系统分布式结构的分布式H系统.第u章针对剪接系统从变量的角度对模型进行了进一步的扩展. Paun等人所撰写的这本学术专著对DNA计算的研究与发展起到了很大的促进作用.特别是在短短的3—4年的时间内，从数学的角度对提出的上述DNA计算模型进行了很好的研究，得出了一些出色成果.虽然DNA计算研究领域发展迅速，但这本专著出版至今，仍然从理论上对DNA计算的研究具有良好的指导作用.遗憾的是，本书未能涉及DNA计算的核心内容——DNA计算的生化机理以及DNA计算的检测方法与技术等方面. 本书的完成与华中科技大学校领导以及系所领导的支持和关心是分不开的。他们是：杨叔子院士，周济院士，李培根院士，丁烈云教授，陈学广教授，陈国清教授，张七一教授，周细刚教授，齐欢教授，孙德宝教授以及系党总支周建波书记. 感谢朝夕相处的费奇教授、冯珊教授、廖晓晰教授、岳超元教授、王红卫教授、赵勇教授等. 我还要感谢本书的作者Paun教授，他对翻译工作给予了大力支持，给出原版中出现的一些错误，而且使我们双方的研究队伍作了进一步的合作研究. 参加本书翻译的还有刘文斌博士、董亚非博士、刘西奎博士以及张连珍硕士等. 由于译者水平所限，在翻译过程中难免出现疏漏、不妥乃至错误等，望各位专家与广大读者不吝赐教. 许 进 2004年3月26日于华工园