DNA计算是一种基于生化反应机理的新型信息处理模式，与基于图灵机思想的电子计算机原理截然不同。从DNA计算解决问题规模的能力来看，其发展相当迅速；1994年，Adleman给出了仅能处理7个顶点有向图中的计算问题实验，到2007年我国研制出搜索能力可达到10²⁸次的图顶点着色DNA计算机，仅用了15年的时间。特别是近年来，DNA分子自组装理论、实验及操控技术的快速发展，为DNA计算机的实现技术提供了一种新的理论和手段。正是凭借其海量存储和超大规模并行运算能力，从理论上可克服电子计算机存储量与运算速度上的不足，有望成为NP-完全问题的潜在解决方案之一。DNA分子自组装是指在一定的温度，浓度，酸碱度以及特定酶的作用下，一些带有输入信息的DNA分子（比如说，DNA Tile）根据Watson-Crick互补配对原则，自组装生成新的带有输出信息的DNA分子的过程。近十年中，DNA分子自组装技术在分子计算、生物物理、纳米技术等各个方面都得到了广泛的应用。尤其对DNA计算的发展具有重要的指导意义。自组装DNA计算模型是通过DNA分子间的相互作用形成特定的构型来完成计算过程。它组合了DNA计算、Ting理论和DNA纳米技术，成为目前备受关注的模型之一。在计算过程中，它避免了其它DNA计算模型所需要的众多实验操作次数，减少了操作带来的时间消耗和误差倾向。本文在深入研究自组装DNA计算机理的基础上，对其在NP-完全问题和信息安全领域中的应用展开讨论，并给出一种编码设计方案。本文创新点如下：首先，分析了传统计算中减法和除法的运算机理，按照除法的运算过程，将除法运算分为比较子系统，复制子系统和减法子系统。借助于已有的Tile类型，将待运算的信息通过编码与Tile的粘性末端相关联，用DNA Tile自组装技术对三个子系统一一给予了实现。最后合并这三个子系统，建立了基于自组装DNA计算的减法和除法运算模型。其次，将自组装DNA计算模型应用于求解组合优化问题，包括0-1规划问题和图着色问题。0-1规划问题作为运筹学中一个重要问题，到目前为止还没有好的算法。本文通过对0-1规划问题中的约束处理机制进行分析，将约束处理分为两个基本操作：“与”操作和“比较”操作。并给出了“与”操作和“比较”操作的自组装DNA计算实现方案。通过组合这两种操作，根据DNA自组装技术，对于任意可行解，能自动判断它是否满足所有给定的约束条件。借助于DNA计算的并行性，提出了基于自组装DNA计算模型的0-1规划问题中约束处理方案。理论分析表明，采用自组装DNA计算模型，可以在多项式时间内解决这一问题。图顶点着色问题与现实生活中的时间表问题、排序问题和任务分配问题等密切相关。这里根据DNA分子自组装的特性，引入非确定性算法，可非确定性的给定图着色方案。利用自组装DNA计算的并行性优势，并行的验证所有可能着色方案，以高概率地给出问题的解，在多项式时间内解决图顶点着色问题。然后，采用DNA Tile编码信息，借助于Tile之间的粘性末端进行自组装，给出了一些两个整数的乘法运算和两个多项式乘法运算的实现方案。在此基础上，通过引入非确定性的指派Tile，提出了一种用自组装DNA计算破译NTRU和RSA公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA Tile，算法可以并行地以高概率地破译这两种密码系统。该方法最大的优点是充分利用了DNA Tile具有的海量存储能力，生化反应的巨大并行性以及组装的自发有序性。最后，针对自组装DNA计算的编码问题给出了一个序列设计方案。编码质量、编码数量、序列长度与DNA计算的可靠性、有效性、可扩充性密切相关。优化DNA编码设计最本质的规律，蕴藏在DNA杂交过程相互绑定时的热动力学之中。采用热力学编码约束，建立了编码序列设计的目标优化数学模型。借助于IWO算法，提出了一种用于编码序列设计的优化算法，阐述了算法的实现过程。通过将本文算法产生的序列和Deaton等提供的DNA序列进行比较和分析，证实了本文算法可产生热力学性质更稳定的DNA序列，验证了本文算法的有效性，拓展了IWO算法在离散空间中的应用。