摘    要

一方面，伴随电子技术不断的发展，电子计算机已经没法去满足人们的需要，另一方面，随着生物技术的发展，DNA计算应运而生。DNA计算是一种全心的计算形式，是一种基于生化反应原理的、以DNA与相应的某些生物酶等作为基本材料的一种新型的分子生物计算方法，它的涌现引起了许多国家学者的普遍关注。非常多研究者已经利用它的耗能低、高度并行性和资源丰富等一系列优点顺利地解决了一些NP完全问题，如汉密尔顿回路问题、最大团问题等。中国知网学术不端文献检测系统

DNA计算就是以分子杂交为核心，杂交的精度和效率直接影响着最终杂交的结果。由此如何去提高杂交反应的准确性也就成了近几年来的研究热点。非常多的学者已经开始去研究DNA编码问题，DNA编码的质量好坏就直接的影响到杂交反应的结果，有效的编码可以大大的降低杂交反应的错配率。我们所说的DNA编码问题也就是在现实的生化反应过程中，我们所编码的每一个信息元 (或位) 的DNA分子都能够被唯一的识别（即完全杂交反应），从而能够最大限度的去减少错误杂交的出现，从而进一步的提高DNA计算的准确性。因此本文主要研究DNA编码问题。中国知网学术不端文献检测系统

知网论文查重

到现在为止DNA编码的研究主要是集中在以下两个方面，一是DNA集合设计，二是DNA质量优化，本文主要DNA集合设计。DNA集合设计也就是说一定长度的DNA编码序列，在满足相应的约束条件下，再通过算法搜索找到符合条件的全部DNA序列集合的最大值。中国知网学术不端文献检测系统

因此，本研究将要采用DNA序列设计中的组合约束条件，也就是热力学约束（GC含量约束）和距离约束（包括H距离和汉明距离约束）的组合约束，设计一套较好的DNA编码集合，并对其进行仿真实验。中国知网学术不端文献检测系统

1 绪论

1.1 DNA计算背景

1946年，第一台电子计算机埃尼阿克在宾夕法尼亚大学诞生。从那开始，电子计算机就开始了飞速发展。同第一台电子计算机相比，电子计算机的价格性能比和体积性能比已经提高的成千上万倍。但是量子理论它揭示了计算机芯片制造的物理极限已经逐渐接近。随着技术和社会的发展，电子计算机已经无法满足解决NP－完全问题，这就使的人们必须去需要寻找一种能克服上述缺点的新型计算机。中国知网学术不端文献检测系统

1953年美英国化学家克里克和国科学家沃森发现了DNA双螺旋结构。1954年美国物理学家加罗夫提出了核苷酸三联体的遗传密码。1958克里克提出了遗传信息传递是从DNA到RNA再到蛋白质的中心法则。1991年阿德尔曼博士开创性的在试管中用DNA分子解决了7个顶点的汉密尔顿图问题。中国知网学术不端文献检测系统

1.2 DNA计算过程和特点

1.2.1 DNA计算过程

在计算机中，我们使用有机分子的独特信息处理能力去取代数字开关部件，这就是DNA计算的思想。具体来说，DNA计算就是利用 DNA的碱基互补配对原则和双螺旋结构对信息去进行编码，然后把接下来要运算的对象映射成DNA分子链，然后再经过相应的生物酶的作用，生成数据池，按照相应的准则把我们需要解决的问题的数据运算并行地映射成DNA分子链的可控的生化反应过程，最后再通过分子生物技术，比如超声波降解、聚合链反应PCR、DNA链的分离和结合、分子纯化、复制、凝胶电泳、磁珠分离等，最终获得我们所需要的结果。中国知网学术不端文献检测系统

从本质来讲，DNA计算和电子计算机是十分相像的，都是从已知的符号串开始，在按照相应的规则，然后对这些符号进行变换，最后我们可以得到满足条件的符号串。但是又有所不同的是，电子计算机是用1和0去表示信息的，但DNA计算是用A、G、C、T来表示，然后再利用一些相应的生化反应来实现，最后取得我们想要的解。中国知网学术不端文献检测系统

DNA计算模式并不是固定的，因为问题的复杂多样性 使得使用的分子生物技术具有 多样性，所以应该根据相应的问题进行具体的设计。但是DNA计算有个一般化的过程：首先对需要处理的信息进行编码，将要解决的问题映射成对应的DNA片段，然后再把这些片段去合成为DNA链；然后再根据碱基互补配对原则让前面所生成的DNA链进行杂交，得到含有最终答案的解空间；最后再通过相应的分离提取手段作用在DNA链上，通过相应的检测去读取所获得的DNA链（即所需的答案）。

1.2.2 DNA计算特点

（1）具有高度并行性，运行速度快。因为DNA分子的杂交反应是并行进行的，所以参加生化反应的DNA分子就都相当于纳米级的处理器，所以DNA计算也是高度并行的，这样就会使其运算速度大大加快。中国知网学术不端文献检测系统

（2）海量存储能力。使DNA计算能够具有非常巨大的信息存储能力的主要原因是DNA分子的双螺旋结构。根据相关的统计，1万亿位的二进制数据可以仅仅储存在1立方米的DNA溶液中。中国知网学术不端文献检测系统

（3）消耗的能量很低。在完成相同的计算时，电子计算机所消耗能量是DNA计算所消耗的能量的十亿倍。

（4）DNA分子资源丰富。

1.3 DNA计算的现状分析

1.3.1 DNA计算现状简介

（1）国际研究进展

自1994年阿德尔曼第一次提出了DNA计算的概念，并且运用生物技术成功的解决了七顶点的汉密尔顿路径问题以来，DNA计算引起了国际上的广泛关注。1995年，利普顿受阿德尔曼思想影响，构造一个接触网络图G，然后运用了阿德尔曼的方法成功地求解了SAT问题，这就证明了通过DNA计算能够解决NP完全问题。1996年，弗兰克提出了DNA计算中的加法运算。1997年，欧阳等人也利用DNA计算解决了图的最大团问题。从这三位研究者以后，很多人都给出了图与组合优化问题的DNA计算结果。

（2） 国内研究进展

从DNA计算诞生到现在为止，国内的很多学者也对DNA计算进行了研究，其中最为著名的就是上海交通大学的贺林院士带领的研究小组、华中科技大学以及北京大学许进教授带领的工作小组对DNA计算进行了深入的研究，并取得了非常不错的成果。

在2000年，世界上第二个Bio-X生命科学研究中心在上海成立，完成了国内第一个DNA计算机雏形。2003年，赵健等设计了一种可以编程的有限自动机，并且它的试验过程是在固体表面所进行的。在2006年，钱璐璐等人实现了两个非负二进制整数之间的加法。2008年，许进等使用DNA计算模型成功的解决了拉姆齐数的位序列问题。

1.4 DNA计算难点

（1）指数爆炸问题

尽管DNA计算具有高度并行性，但是在解决层出不穷的复杂实际问题时，DNA计算模型也面对着指数爆炸问题。现实中遇到的汉密尔顿路径问题可远远不止几个点，很可能是上万个点，即便是将编码每个顶点的寡核苷酸长度减少为1，一条路径也是需要102-3bp，这样的解空间将是一个十分庞大的数。中国知网学术不端文献检测系统

（2）生物技术限制

第一，在DNA计算中所用到的各种各样的生物技术，例如DNA分子合成、凝胶电泳、聚合酶链反应等都难以做到非常准确，都存在或多或少的误差；第二，实验中各种生物酶的反应也不是100%充足的，大约是80%-95%,并且会不断的累积；第三，DNA序列的长度是有限的，到目前为止最大的长度是10000bp。

（3）DNA编码问题

在DNA计算过程中，最为重要的是DNA分子的杂交反应，而杂交反应的结果是由DNA编码的质量所决定的，所以为了减少单链的DNA片段形成发卡结构，我们应该选择一个好的编码方法，从而去有效地控制错误杂交，从而进一步的提高反应的效率和精度。中国知网学术不端文献检测系统