《自组装dna计算模型的研究及应用》由会员分享，可在线阅读，更多相关《自组装dna计算模型的研究及应用（133页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 博士学位论文 自组装DNA计算模型的研究及应用 姓名：张勋才 申请学位级别：博士 专业：系统分析与集成 指导教师：许进 20090522 华 中 科 技 大 学 博 士 学 位 论 文华 中 科 技 大 学 博 士 学 位 论 文 I 摘摘 要要 DNA 计算是一种基于生化反应机理的新型信息处理模式，与基于图灵机思想的 电子计算机原理截然不同。 从 DNA 计算解决问题规模的能力来看， 其发展相当迅速； 1994 年，Adleman 给出了仅能处理 7 个顶点有向图中的计算问题实验，到 2007 年我 国研制出搜索能力可达到 1028次的图顶点着色 DNA 计算机，仅用了 15
2、年的时间。 特别是近年来，DNA 分子自组装理论、实验及操控技术的快速发展，为 DNA 计算 机的实现技术提供了一种新的理论和手段。正是凭借其海量存储和超大规模并行运 算能力， 从理论上可克服电子计算机存储量与运算速度上的不足， 有望成为 NP-完全 问题的潜在解决方案之一。 DNA 分子自组装是指在一定的温度，浓度，酸碱度以及特定酶的作用下，一些 带有输入信息的 DNA 分子（比如说，DNA Tile）根据 Watson-Crick 互补配对原则， 自组装生成新的带有输出信息的 DNA 分子的过程。近十年中，DNA 分子自组装技 术在分子计算、生物物理、纳米技术等各个方面都得到了广泛的应用。
3、尤其对 DNA 计算的发展具有重要的指导意义。自组装 DNA 计算模型是通过 DNA 分子间的相互 作用形成特定的构型来完成计算过程。它组合了 DNA 计算、Ting 理论和 DNA 纳米 技术，成为目前备受关注的模型之一。在计算过程中，它避免了其它 DNA 计算模型 所需要的众多实验操作次数，减少了操作带来的时间消耗和误差倾向。本文在深入 研究自组装 DNA 计算机理的基础上，对其在 NP-完全问题和信息安全领域中的应用 展开讨论，并给出一种编码设计方案。本文创新点如下： 首先，分析了传统计算中减法和除法的运算机理，按照除法的运算过程，将除 法运算分为比较子系统，复制子系统和减法子系统。借助
4、于已有的Tile类型，将待运 算的信息通过编码与Tile的粘性末端相关联， 用DNA Tile自组装技术对三个子系统一 一给予了实现。最后合并这三个子系统，建立了基于自组装DNA计算的减法和除法 运算模型。 其次，将自组装 DNA 计算模型应用于求解组合优化问题，包括 0-1 规划问题和 图着色问题。 0-1 规划问题作为运筹学中一个重要问题， 到目前为止还没有好的算法。 华 中 科 技 大 学 博 士 学 位 论 文华 中 科 技 大 学 博 士 学 位 论 文 II 本文通过对 0-1 规划问题中的约束处理机制进行分析，将约束处理分为两个基本操 作：“与”操作和“比较”操作。并给出了“与”
5、操作和“比较”操作的自组装 DNA 计算实 现方案。通过组合这两种操作，根据 DNA 自组装技术，对于任意可行解，能自动判 断它是否满足所有给定的约束条件。借助于 DNA 计算的并行性，提出了基于自组装 DNA 计算模型的 0-1 规划问题中约束处理方案。理论分析表明，采用自组装 DNA 计算模型，可以在多项式时间内解决这一问题。 图顶点着色问题与现实生活中的时间表问题、排序问题和任务分配问题等密切 相关。这里根据DNA分子自组装的特性，引入非确定性算法，可非确定性的给定图 着色方案。利用自组装DNA计算的并行性优势，并行的验证所有可能着色方案，以 高概率地给出问题的解，在多项式时间内解决图顶
6、点着色问题。 然后，采用 DNA Tile 编码信息，借助于 Tile 之间的粘性末端进行自组装，给出 了一些两个整数的乘法运算和两个多项式乘法运算的实现方案。在此基础上，通过 引入非确定性的指派 Tile，提出了一种用自组装 DNA 计算破译 NTRU 和 RSA 公钥 密码系统的非确定性算法。通过创建数以亿计的参与计算的 DNA Tile，算法可以并 行地以高概率地破译这两种密码系统。该方法最大的优点是充分利用了 DNA Tile 具 有的海量存储能力，生化反应的巨大并行性以及组装的自发有序性。 最后，针对自组装 DNA 计算的编码问题给出了一个序列设计方案。编码质量、 编码数量、序列长度
7、与 DNA 计算的可靠性、有效性、可扩充性密切相关。优化 DNA 编码设计最本质的规律，蕴藏在 DNA 杂交过程相互绑定时的热动力学之中。采用热 力学编码约束，建立了编码序列设计的目标优化数学模型。借助于 IWO 算法，提出 了一种用于编码序列设计的优化算法，阐述了算法的实现过程。通过将本文算法产 生的序列和 Deaton 等提供的 DNA 序列进行比较和分析，证实了本文算法可产生热 力学性质更稳定的 DNA 序列，验证了本文算法的有效性，拓展了 IWO 算法在离散 空间中的应用。 关键词：DNA 计算，Tile 自组装，算术运算，0-1 整数规划，图着色，编码设计， NTRU 破译，整数分解
8、 华 中 科 技 大 学 博 士 学 位 论 文华 中 科 技 大 学 博 士 学 位 论 文 III Abstract DNA computing is a new information processing pattern. It is different from electronic computer principle, as that electronic computer principle based on Turing idea, while DNA computing based on biochemical reaction. Viewing from the abil
9、ity of DNA computing to solve problems, it grows quickly. It only cost 15 years form an experiment given by Alderman in 1994, which can only deal with 7 vertexes HPPs computing to developing DNA computer to solve graph coloring problem, whose searching times are 1028 in 1997. Especially in recently
10、years, a new theory and measure is provided for DNA computers achievement, as the fast development of both the theory of DNA molecule Self-assembly and experimental technology. Given its vast parallelism and high-density storage, from theory, some shortages such as storage and operation speed in ele
11、ctronic computer can be overcome. DNA computing approaches show great potential to solve complex combinatorial optimization problems such as the NP-complete problems. DNA molecule self-assembly is a process, in which some molecules (such as DNA Tile) carry with input information, according to Watson
12、-Crick complementary principle to produce new DNA molecules, which have output information. The process develops under special temperature, concentration and enzyme. In this decade, the potential of DNA self-assembly has been widely developed in the fields of molecular computing, biophysics, nanotec
13、hnology and so on. It has important significance especially for the development of DNA computing. DNA computing by self-assembly model completes the computing process by using DNA molecules autonomously associate with each other to form superstructures. The idea of computing aroses from the combinat
14、ion of DNA computing, the theory of tilings, and DNA nanotechnology. So it has become one of the remarkable models. During the computing, it avoids too much experiment operations, time consuming and error, while other DNA computing models can not. This paper mainly focuses on DNA computing by self-a
15、ssembly. Discussing DNA computing by self-assemblys application both in NP-complete problem and information safety field, and an encoding design scheme is proposed. The detailed contents are as follows. Subtraction and division are fairly basic operators for any computing model. This part shows how
16、the tile assembly process can be used for subtraction and division. In order to achieve this aim, four systems, including the comparator system, the duplicator system, 华 中 科 技 大 学 博 士 学 位 论 文华 中 科 技 大 学 博 士 学 位 论 文 IV the subtraction system, and the division system, are proposed to compute the difference and quotient of two input numbers using the tile assembly model. This work indicates that these systems can be carried out in polynomial time with optimal O(1) distinct tile types in paralle
