自Adleman博士首次提出DNA计算理论并成功解决哈密顿路径问题以来,许多科学家都致力于用DNA计算来解决图论问题并建立模型。他们的最终目的是研制出以DNA计算为基础的、具有高存储信息量的、超级运行速度的新型计算机。随着遗传学的发展,人们发现了DNA分子可自行组装,而且DNA链除单链双链结构外还可以形成发夹结构。在此基础上,DNA自组装技术和分子信标诞生了。目前,如何组装DNA分子收到很多研究者们的关注,原因在于它直接影响着DNA计算的发展。分子信标也因自身的独特结构成为研究热点,在研究者们的不断努力下发现了分子信标具有很多特殊的性质。这些性质被广泛的应用到计算科学、医学、工程学等科学研究领域。在前人的基础上,本文主要从分子信标与DNA自组装技术出发,对组合优化问题及逻辑门问题进行了研究和讨论。文章开始对DNA计算的背景、现状和发展进行了简单的介绍。然后叙述了DNA计算的一些基础知识,并详细介绍了分子信标和DNA自组装技术。分子信标作为一种特殊的DNA探针源于其具有特殊的发夹结构,这种结构赋予它超强特异识别靶序列的能力。在一定条件下,DNA分子可以由小分子结构依靠分子间的非共价键自组装成大分子结构的过程称为DNA自组装。一般,我们可以通过控制温度或加入DNA溶解酶即可控制DNA自组装过程,操作简单方便。目前研究者们开始关注分子自组装的二维结构,进而发展三维空间结构。在构造DNA自组装的二维结构的元件,我们常用的是DNA单链、双链等。但是这种组装元件对编码要求比较高,分子信标的特殊结构恰好可以弥补这一不足。在此思想基础下,本文建立了基于DNA自组装的全错位排列问题模型和基于分子信标的异或门DNA自组装计算模型。最后归纳总结全文,对未来的研究状况进行设想。