DNA计算一直以来都是很热门的一门学科,它利用分子生物技术解决计算机科学或数学中的问题,是计算机科学与生物化学之间的桥梁。在DNA的计算中,信息通过DNA分子间的相互作用进行传递,并且它的过程是通过一系列生化反应来完成的,由于生化反应中固有的大量并行性和DNA分子的高信息密度,使得DNA计算慢慢成为一个有吸引力的并且值得研究的领域。本文主要研究的是DNA计算在NP-完全问题中的应用。首先在绪论中介绍了 DNA计算的背景知识,基本的思想和意义。然后详细阐述了 DNA折纸术在可满足性问题中的应用,并列出了可满足性问题的研究现状。可满足性问题是理论计算机与人工智能等领域共同关注的NP-完全问题之一,在NP-完全问题中占有很重要的地位。与以往提出的一些DNA自组装方法相比,DNA折纸术可以看成是一种新的DNA自组装方法。利用基于DNA折纸术求解可满足性问题的计算模型,解决了一个含3个变量、3条子句的实例,以说明算法的可行性。该计算模型只需利用凝胶电泳寻找满足问题的解,这是目前已知的最可靠的生物操作,提高了模型可行性,降低了生物操作的难度。目前,利用折纸术来求解NP-完全问题的成果相对较少,我们提出的方法是利用生物DNA分子解决NP-完全问题的一种新的尝试。尽管SAT问题有很多丰硕成果,但基于SAT问题的重要性,新的方法总能引起读者重视。随着研究人员们更深入的研究以后,使得对于DNA折纸术,其结构的尺寸及其稳定性有了初步的改进,它作为一个新兴的DNA计算模型,在很多方面都起到了一定的推动作用,对DNA计算的发展提供了更大的帮助。根据列出的0-1整数规划问题的研究现状,提出巨磁电阻型DNA计算模型在0-1整数规划问题中的应用。本文将问题的变量编码成DNA链,在GMR型芯片表面固定DNA探针,然后将被生物素标记的待分析目标DNA链与探针进行充分杂交,通过芯片上的GMR传感器对芯片上纳米磁珠的检测,以电信号方式输出,得到问题的解,避免了荧光分析中的信号转换而引起的失真。该模型具有较高灵敏度,信号检测和分析较为简单,对信号检测设备要求较低。最后简单的介绍了本文的主要研究结果,比较了提出的模型与其他DNA计算模型的优点与不足,并交代了进一步的研究方向。图[29]表[2]参考文献[58]