DNA计算是生物计算中最受关注的一种计算，目前的DNA计算领域始于1994年Adleman先生的著名实验．本文探讨了采用分子生物技术，通过DNA计算寻找Hamilton路从而判定Hamilton图的一些算法及用DNA计算来解决染色问题． 第一，本文首先分析总结了Hamilton图的充分条件问题、研究状况.Hamilton圈问题是图论最古老的研究课题之一，是至今未解决的世界难题．特别是寻找一般图的Hamilton图的充分条件问题是NP问题． 其次，介绍了DNA计算的产生背景、研究状况、生物学基础、DNA计算解决Hamilton圈的基本原理和操作方法。DNA计算机起源于人们对并行计算的研究和追求，以传统的图灵机(Turing Machine)为原型的现代电子计算机很难从真正意义上实现并行算．于是人们将目光投向了其它领域，以求获得完全不同的计算方式和计算理念．DNA算法解决计算问题的基本思想是：以DNA碱基序列作为信息编码的载体，利用现代分子生物学技术，在试管内控制酶的作用下进行DNA的序列反应，Watson-Crick互补序列反应作为实现运算的过程．以反应前的.DNA序列作为输入的数据，反应后的DNA序列作为运算的结果．DNA计算的操作方法一般有抽取、切割、溶解、退火、合成、杂交、扩增PCR、检测、分离、电泳、磁珠分离、连接和合并等. 最后，指出DNA计算机的优点、应用前景与存在的技术问题.DNA计算机的优点是：运算速度快；低能耗；存储容量高；可以真正实现并行工作.DNA计算机的应用前景：1.解决某些NP完全问题2.数据加密解密3.智能控制4.生物化学、组合化学、医学等5.Boolean电路和数据流逻辑运算.DNA计算机的存在的技术问题：DNA计算中误差消除问题；快速操作技术问题；DNA计算系统的框架还未形成；DNA制作成本较高等． 第二，本文建立了解决简单问题的简单模型，从而推广到解决复杂问题即NP完全问题．并探讨了在推广过程中产生的伪解问题及采取的相应的去除操作．先结合Adleman的实验建立一个小规模图的DNA计算的简单模型，用凝练的语言介绍DNA计算解Hamilton图的思想方法、生物实验操作步骤，然后再扩大规模研究NP问题(Hamilton图的问题)．并对问题的复杂性作了计算复杂性讨论．介绍一种用基于可满足解空间的DNA计算方法，来解决Hamilton回路问题，该方法可以简化DNA计算过程，提高求解问题的规模．建立HPP问题的DNA计算模型的步骤包括：问题描述、算法设计、DNA计算的实现三部分．这种方法在原理上也同样适用于比较大的图．这种方法的关键是大规模的并行计算和碱基互补原则．对于解决HPP问题，Adlemarl的解决方案基于如下非确定算法： 输入：具有n个顶点的有向图G，指定顶点v<,in>和v<,out>． 第一步：在G中随机生成大量的各种各样的路径． 第二步：去掉所有不以顶点v<,in>为起点和不以顶点v<,out>为终点的路． 第三步：去掉所有没有恰含n个顶点的路． 第四步：对于这n个顶点中的每一个顶点v，去掉所有不包含顶点v的路． 输出：如果存在路，输出“是”，否则输出“否”． 实质上，此算法是在执行穷举搜索，在Adleman的算法中，DNA串的巨大规模的并行计算处理了令人讨厌的非确定性，Watson-Crick碱基互补原则用来确保构造出的边的序列就是图G中的路．DNA计算的优势是其具有强大的并行性．但是在解决组合优化中的NP-完全问题时，传统的DNA计算模型面对指数级增长的解空间却显得无能为力．据估计对于200个顶点的HPP问题，按照Adleman的方法，所需的DNA分子将超过地球的重量，为了解决“指数爆炸”问题，总结了目前国外的几种解决方法。 第三，讨论了最新的DNA计算在NP问题即点染色问题和边染色问题中的应用．用DNA计算解染色问题，其主要思想是将着色问题分解成顶点独立集问题和顶点划分问题进行解决，该算法将点(边)的DNA编码分为两部分，一部分存储点(边)和色位置的二维数据，另一部分存储色号值．先将此NP问题在多项式时间内归约到可满足性问题．对初始试管T<,0>选用粘贴模型的操作，并引入Discard表示“舍弃”操作(将试管中的溶液倒掉)，以Lipton解决SAT问题的思想为依据，给出求解图G的顶点k-着色问题的算法。然后在DNA计算的去除操作过程中采用批删除操作，从而有效地解决了此染色问题．随着社会和技术的发展，许多工程领域中的复杂巨系统不断涌现，充满着各种各样的非线性问题，形形色色棘手的完全问题处处可见，而DNA计算机有望解决当今在电子计算机上许多无法解决的问题．用DNA计算来解决此类染色问题具有重大的实际意义，在诸多领域都有很好的应用前景．