DNA计算是一种多学科相互交叉的技术,它的发展有赖于分子生物学和计算机科学的综合发展。这种计算模式凭借着DNA序列的强大存储密度和高度并行性,在求解一些复杂的组合优化问题及NP困难问题时显示出了极大的优势。近年来,对DNA计算的研究得到了很大的发展,一些基于DNA计算的模型被提了出来,如:剪接系统模型、分子瓦自组装模型、粘贴模型等。由于DNA自组装计算模型的操作简单易行,在整个过程中不需要人为对它的干预,因此对它的研究引起了越来越多专家学者的重视。DNA tile自组装计算模型就是通过DNA分子间相互匹配的粘性末端而组装成可完成特定计算结构的过程,它综合了DNA计算技术、Ting理论及DNA纳米技术。本论文主要工作如下:首先,介绍了DNA计算和DNA自组装的基本背景知识,以及有关它们的研究及发展现状。由于DNA分子的超大规模并行性、超低的能耗和超高的存储密度,才使得DNA计算成为研究上的一个热点,它的进一步发展将有利于改进现有一些研究方法的局限性。其次,以DNA计算中的自组装模型为手段,NP问题为研究对象,采用DNA自组装模型对三个典型的组合优化问题进行了讨论和研究。针对每一个问题都建立了相应的计算Tile,并且得到了计算结果,最后对计算复杂度进行了分析。对于0-1背包问题,改进了先前的自组装模型,引入了一个由DNA Tile构成的比较系统,用它来判断约束条件是否得到满足。通过结果可知时间复杂度得到了提高,理论上达到了在多项式时间内解决这一问题的目的。装箱问题也是一个典型的组合优化问题,在本文中只研究了一维的情况。对于该问题引入了折半分组的概念,在组装过程的采用了一个减法系统。该模型为研究更为复杂的装箱问题提供了一种思维方式。度约束最小生成树问题是一个经典的图论问题,其目标是找出给定图的满足度约束的最小生成树。为了解决该问题,引入了一个非确定搜索的概念,并且通过巧妙的设定运算规则和一些Tiles,实现了对该问题的求解。最后把该思路推广到求解旅行商问题上,为TSP问题的研究提供了一种新的思路。最后,对全文进行了总结与展望。DNA计算作为一个新兴的学科,对它的研究和应用还处于初期的探索阶段,在理论和实现技术上都还有一些不足之处,还需要进一步的深入研究和探讨。